I'm trying to understand this proof to prove that there is at most one perfect matching in a tree.
Let M, M' be perfect matchings in the tree T = (V, E) and consider the
graph on V with edge set M ∪ M' .Since M and M' both cover all the
vertices, every component of this new graph is either a single edge
(common to both M and M' ) or a cycle. Since T is a tree, there can be
no cycle, so we conclude that M = M'.
The only thing I have troubles to visualize is why if the component of the new graph is not a common edge then it should be a cycle.
Thanks
Best Answer
I assume you are dealing with finite graphs. In this case, the following may help you understand the argument a little bit better although what I am about to write is not 'mathematically sound'.
Consider any component of the new graph and let $v_0$ be some vertex in that component. If that component consist only of a single edge, there is nothing left to prove as $M$ and $M'$ coincide on this component.
If, however, the component is more than a single edge, we do the following: By definition of $M$ and $M'$, $v_0$ is connected to some $v_1$ by an edge in $M$ (which is not in $M'$ since the component is not just a single edge). There exists exactly one edge in $M'$ (which in turn cannot be in $M$) connecting $v_1$ to some vertex $v_2$. We can do this little game to construct an infinitely long path using alternating edges from $M$ and $M'$. Since the graph is finite, an infinite path has to be a cycle.
If this is still unclear or you have any questions, leave a comment.