Given a balanced bipartite graph that satisfies Hall's theorem (is non singular) then it shown that it has at least one perfect matching.

My question is if the balanced bipartite graph is also acyclic then is the perfect matching unique?

If so (I am almost certain it is), can you point me to a cite-able source? I was not able to such a document.

  • 3
    $\begingroup$ Follows directly from the fact the the symmetric difference between the set of edges of two perfect matchings is a collection of disjoint cycles. $\endgroup$ – Kristoffer Arnsfelt Hansen Apr 5 '18 at 17:13

This fact can be found in

Godsil, C. D. (1985), "Inverses of trees", Combinatorica 5 (1): 33–39, doi:10.1007/BF02579440

(without proof, near the bottom of the first page): "noting that a tree with a perfect matching has just one perfect matching".

The same paper provides a more general characterization of the bipartite graphs with a unique perfect matching: this is true for the subgraphs of the half graph that have perfect matchings, and for no other bipartite graphs.

  • $\begingroup$ Thank you. This is invaluable information. I did not know (or even think about yet) what other bipartite graphs had unique matching. $\endgroup$ – stardust Apr 6 '18 at 9:13

If the graph is acyclic, which implies that it is also bipartite, then the perfect matching is unique by the following algorithm:

While the graph is not empty, pick a leaf vertex $u$ (which exists because the graph is acyclic) add the edge between $u$ and its unique neighbor $v$ to the matching and then remove $u$ and $v$. If at some point graphs without incident edges are produced, then there is no perfect matching.

This is probably folklore knowledge which would mean that there is no citable source.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.