Proving every tree has at most one perfect matching

Solution 1:

First, why the claim is true. Take any vertex. If it's matches to the same vertex in both perfect matching, then it had degree zero on the symmetric difference. Otherwise it has degree two.

Second, after removing all isolated vertices in the symmetric difference, all vertices have degree two. Take any such vertex and follow its two edges. What you get is a growing path that eventually closed to a cycle since the graph is finite.

Since trees have no cycles, this implies that any two perfect matching are equal, by consisting their symmetric difference.

A different proof is by induction. The idea is that every leaf must be matched to its unique neighbor.

Solution 2:

Let $M$ and $M_0$ be perfect matchings in a tree. Form the symmetric difference of the edge sets, $M \bigtriangleup M_0$. Since the matchings are perfect, each vertex has degree $0$ or $2$ in the symmetric difference, so every component is an isolated vertex or a cycle. Since the tree has no cycle, every vertex must have degree $0$ in the symmetric difference, which means that the two matchings are the same.