<p>This fact can be found in</p>

<p>Godsil, C. D. (1985), "Inverses of trees", <em>Combinatorica</em> 5 (1): 33–39, <a href="https://doi.org/10.1007/BF02579440" rel="nofollow noreferrer">doi:10.1007/BF02579440</a></p>

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

<p>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 <a href="https://en.wikipedia.org/wiki/Half_graph" rel="nofollow noreferrer">half graph</a> that have perfect matchings, and for no other bipartite graphs.</p>

CC BY-SA 3.0
2018-04-06T09:13:23.233Z
Thank you. This is invaluable information. I did not know (or even think about yet) what other bipartite graphs had unique matching.
stardust
CC BY-SA 3.0
2018-04-06T01:22:21.800Z
2018-04-06T01:30:27.637Z
2018-04-06T01:30:27.637Z
David Eppstein
<p>If the graph is acyclic, which implies that it is also bipartite, then the perfect matching is unique by the following algorithm: </p>

<p>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. </p>

<p>This is probably folklore knowledge which would mean that there is no citable source. </p>

CC BY-SA 3.0
2018-04-05T14:14:48.350Z
2018-04-05T14:14:48.350Z
Christian Komusiewicz
<p>Given a balanced bipartite graph that satisfies Hall's theorem (is non singular) then it shown that it has at least one perfect matching.</p>

<p>My question is if the balanced bipartite graph is also <strong>acyclic</strong> then is the perfect matching <strong>unique</strong>?</p>

<p>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.</p>

CC BY-SA 3.0
2018-04-05T17:13:05.930Z
Follows directly from the fact the the symmetric difference between the set of edges of two perfect matchings is a collection of disjoint cycles.
Kristoffer Arnsfelt Hansen
<graph-theory><graph-algorithms><co.combinatorics><matching><bipartite-graphs>
Is perfect matching for bipartite graph with no cycles unique?
stardust
# Is perfect matching for bipartite graph with no cycles unique?

(Asked by: username_0 on 2018-04-05)

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.

**Tags:** graph-theory, graph-algorithms, co.combinatorics, matching, bipartite-graphs
> **Comments:**
> **username_1**: Follows directly from the fact the the symmetric difference between the set of edges of two perfect matchings is a collection of disjoint cycles.  

---

## 2 answers

### Answer by username_2 on 2018-04-06. Score: 3 | Accepted answer

This fact can be found in

Godsil, C. D. (1985), "Inverses of trees", *Combinatorica* 5 (1): 33–39, [doi:10.1007/BF02579440](https://doi.org/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](https://en.wikipedia.org/wiki/Half_graph) that have perfect matchings, and for no other bipartite graphs.

> **Comments:**
> **username_0**: Thank you. This is invaluable information. I did not know (or even think about yet) what other bipartite graphs had unique matching.  

---

### Answer by username_3 on 2018-04-05. Score: 4

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.


---

