[Math] every tree $T$ has at most one perfect matching, alternative proof

alternative-proofcombinatoricsgraph theory

I have two questions:

I need to know if the following approach (by induction) is correct. The ones I saw use induction on the components of $T$ with a leaf removed, I did something a little different. In particular the proof seems to imply a condition for the existence of such a perfect matching, hence my second question: is this also true?

We do induction on the number of vertices $n$

Base cases are clear.

Consider a tree $T$ with $|T|=n$.
Take a maximum path $P$ (maximum:= of maximal length) in $T$ ending in a leaf $v$ adjacent to a unique vertex $u$. Note that by maximality all neighbours of $u$ except one (call it $w$) must be leafs. Consider now the graph $T':= T\backslash (N(u) \backslash w)$ (edited) where $N(u)$ is the neighbourhood of $u$. Note that $T'$ is still connected , hence a tree with fewer vertices then $T$. By induction $T'$ has at most one perfect matching. Now if no perfect matching of $T'$ exists then $T$ has no perfect matching (follows from a quick verification). Else if a unique perfect matching of $T'$ exists (and here is the condition i mentioned at the begining), then this perfect matching can be only extended iff $u$ is adjacent only to $v$ and $w$. This can be done (uniquely) by just adding $(u,v)$ to the perfect matching of $T'$. end.

So the condition is: if a perfect matching exists, any maximal path in $T$ ending in $(v,u)$, where $v$ is a leaf, must satisfy deg$(u)=2$ (or $1$ in case $|T|=2$).

Best Answer

First, maximal path means something different than a path of maximum length. A maximal path is a path that can not be extended by adding edges to either the front or the end of the path.

Consider now the graph $T' := T \setminus (N(u) \cup w)$ where $N(u)$ is the neighborhood of $u$. Note that $T'$ is still connected, hence a tree with fewer vertices than $T$.

Isn't $w$ already in the neighborhood of $u$? Do you mean perhaps $T \setminus (N(u) \setminus \{w\})$? Because if not $T'$ need not be connected.

As an aside, if you are proving this for a class assignment, I would imagine that you would need to prove many of the intermediate claims that you write. They are correct though other than the comments above.

So for your condition on paths of maximum length. It is true (with the correct terms). To see this, suppose not. So for some path, $P=x-\cdots -t-u-v$, of maximum length, there is a vertex $s \neq t, v$ adjacent to $P$. There are two cases: $s$ is a leaf and so there can not be a perfect matching because there are two degree 1 vertices adjacent to the same vertex; or $s$ is not a leaf. If $s$ is not a leaf, then there is an edge from $s$ to some vertex $y \neq u$. If $y$ was in the earlier path, then we would have a cycle (contradiction) and if $y$ was not in the earlier path, then $x - \cdots - t - u - s - y$ would be a longer path.