Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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.
