I wanted to prove that a tree $T$ has a perfect matching if and only if $T-v$ $(v \in V)$ has exactly one odd component for all $v$ which are vertices of the graph.
(An odd component is a component with an odd number of vertices)
Kindly help!
[Math] Perfect matching of a tree
graph theory
Best Answer
HINT: One direction is fairly easy. Suppose that $T$ has a perfect matching. Show that when you remove a vertex $v$, the only odd component is the one containing the vertex matched with $v$. In the other direction, suppose that removing any vertex $v$ of $T$ gives you exactly one odd component, $C_v$. Let $u_v$ be the vertex of $C_v$ adjacent to $v$. Can you show that matching $v$ with $u_v$ gives you a perfect matching of $T$? You’ll want to show that $u_{u_v}=v$ for each vertex $v$ of $T$.