Maximum matching contains one edge that contains a leaf of a tree.

Question

I wanted to show the following using Berges Lemma (https://en.wikipedia.org/wiki/Berge%27s_lemma): Let $T=(V,E)$ be a tree with $n:=|V| \geq 3$. Then any maximum matching $M_{max}$ contains at least one edge $E$ that contains one of the leafs of $T$.

Since $T$ is a tree it has at least two leafs $l_1,l_2$ and since $n \geq 3$ there is a path $P$ connecting $l_1$ to $l_2$ such that $|P| \geq 3$. If $M$ would not contain any edge $E$ with either $l_1 \in E$ or $l_2 \in E$, then $P$ would almost be an augmented path, in contradiction to Berge's Lemma. All I need is that $P$ is alternating, but I don't know whether it is possible to construct $P$ in this way.

Edit: After looking I found that something similar has been used in the proof of the tree theorem by Adam Lowrance in $\alpha^{'}(G)\geq\frac{n}{1+\Delta(G)}$. However, he seems to use a different definition of augmented path than what is used in the wikipedia of Berges Lemma.

Answer 1

The straightforward way to prove this claim is to just see what happens when we search for an augmenting path, starting at any unmatched vertex. (The starting vertex may or may not be a leaf; it doesn't matter. However, we may assume that some unmatched vertex to start from does exist: otherwise, $M_\max$ would be a perfect matching and cover every leaf.)

We will just alternate the following two steps:

1. From the current position, walk along an edge that's not part of $M_\max$.
2. From the current position, walk along an edge that is part of $M_\max$.

We will repeat these two steps until the step we're trying to do is impossible. Note that when we start at an unmatched vertex, the first step should always be possible: when $n \ge 2$, every vertex has at least one edge, and if it's unmatched, then that edge is not part of $M_\max$.

How can we get stuck? There are two options:

1. We get stuck on step 1: we went to the current vertex along an edge that is part of $M_\max$, but now there are no edges out of it that are not part of $M_\max$. Then our current vertex must be a leaf that's covered by the matching, and we have what we wanted.
2. We get stuck on step 2: we went to the current vertex along an edge that is not part of $M_\max$, but now there are no edges out of it that are part of $M_\max$. Then the current vertex is also unmatched, and the path we walked is an $M_\max$-augmenting path, which is a contradiction to Berge's lemma.

Crucially, because the graph is a tree, we must get stuck: there are no cycles, so we can't keep walking forever.