Use following Theorem to show that every tree has at most one perfect matching.
Theorem: Let $M_1$ and $M_2$ be matching in graph $G$. Then each component of the spanning subgraph $H$ of $G$, with $E(H)=(M_1 -M_2) \cup (M_2 -M_1)$, is one of following type
i) an Isolated vertex
ii) An even cycle whose edges are alternately in $M_1$ and in $M_2$
iii) a nontrivial path who edges are alternately in $M_1$ and in $M_2$ and such that each end vertex of the path is either $M_1$- unmatched or $M_2$-unmatched but not both
It look like I need to prove this by contradiction. So assume that a tree $T$ has two perfect matching, namely $M_1$ and $M_2$. I will some how show that this will contradict to the above theorem.
So let $H$ be a spanning subgraph with $E(H)=(M_1 -M_2) \cup (M_2 -M_1)$, this shows that $H$ contain at least one edges, thus $H$ can't be an isolated vertex, hence i) is false in this case
Second, $T$ is a tree, so $H$ can't be a cycle, thus ii) is also false
I'm trying to finad a way to argue that iii) must also false, but I haven't got any luck. Any help would be greatly appreciated.
Best Answer
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.