Perfect matching in a tree

$\begingroup$

Prove that in a tree there is at most $1$ perfect matching

If the number of vertices is even$\implies$ number of edges odd, not divisible by $2$, so no perfect matching

For the other case can you apply induction using $2$ leaves ?

$\endgroup$ 1

1 Answer

$\begingroup$

Applying induction by removing a leaf is the right idea. If $x$ is a leaf, and the edge meeting $x$ is $xy$, then any perfect matching for $T$ must consist of $xy$ together with a perfect matching of $T-\{x,y\}$. Now $T-\{x,y\}$ isn't necessarily a tree, but all of its components are trees.

$\endgroup$ 2

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy