A graph is called *matching-covered* if every edge is containd in a perfect matching. (Such graphs are also sometimes called "elementary", e.g. in Chapter 4 of "Matching Theory" by Lovasz & Plummer). It is well-known that for bipartite graphs this is equivalent to the existence of [ear decompositions](http://en.wikipedia.org/wiki/Ear_decomposition).


What I'd like to know is whether the problem of **counting the perfect matchings** - which is very difficult in general, even for bipartite graphs, being equivalent to the permanent etc. - becomes easier when restricted to bipartite matching-covered graphs.


For example, it seems to me that the number of matchings ought to be somehow readable off the ear-decomposition but I don't quite see how.



Counting matchings in a bipartite matching-covered graph
Yes, it is still just as hard. Given an arbitrary bipartite graph, in polynomial time you can remove every edge that is not in a perfect matching (test one edge at a time), thus reducing the problem to a matching-covered graph.


