graph theorytrees
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?
It’s true that the subgraph $H$ has at least one edge, but that does not by itself imply that it has no isolated vertex. In the graph shown below we have the perfect matchings $M_1=\{14,25,36\}$ and $M_2=\{14,26,35\}$, which generate the subgraph graph $H$ with the same six vertices whose edge set is $\{25,26,35,36\}$; this $H$ has two isolated vertices, $1$ and $2$.
(In fact this $H$ has two instances of alternative (i) and one of alternative (ii).) Thus, you still need to rule out (i) as well as (iii) for a tree $T$.
Suppose that $H$ has an isolated vertex $v$. Then every edge of $T$ incident at $v$ must belong to both matchings or to neither matching. There must be an edge of $M_1$ incident at $v$; call it $vw$. Then $vw$ must also be in $M_2$, and no other edge of $M_1$ or $M_2$ can be incident at $v$, or for that matter at $w$.
Now remove from $T$ the vertices $v$ and $w$ and all edges incident to either of them. What’s left will be a forest $F$, and each tree in that forest will have fewer vertices than $T$. Moreover, $M_1\setminus\{vw\}$ and $M_2\setminus\{vw\}$ are distinct perfect matchings of $F$, so they must differ on at least one of the trees of $F$. This suggests that we should try a proof by induction on the number of vertices: if we already had the result for trees with fewer vertices than $T$, we’d have a contradiction at this point, showing that $H$ cannot have an isolated vertex.
Now try to take the same approach to (iii); suppose that $H$ has such a path, and consider what happens if you remove from $T$ that path and all edges of $T$ incident at its endpoints.
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.
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.