Proving every tree has at most one perfect matching

23.1k Views Asked by At

In trying to prove that every tree, T, has at most one perfect matching, I came across this idea:

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.

Why is this true? Why is it true that since each vertex is either of degree $0$ or of degree $2$, then all components are either isolated or a cycle?

2

There are 2 best solutions below

0
On BEST ANSWER

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.

2
On

Since every tree of two or more vertices is two chromatic. Tree with even no of vertices will have the perfect matching as all the vertices with same color can be grouped together and a matching can be established between two groups. But any tree with odd no of vertex will have no perfect matching for obvious reason. Hence proved.