Matchings in a tree

Question

Let $T$ be a tree.

Suppose that $T$ doesn’t have a perfect matching and let $M$ be a matching of $T$, $|M| = k$. Prove that there exists a matching of the same cardinality $k$ which exposes at least a pendant vertex of $T$.

My idea:

If $T$ has not a perfect matching it means that $\exists x$ in $V(T)$ and $x$ is exposed. I don't know how to use this in symmetric difference to find another matching $M_1$, $|M_1|=k$ which exposes at least a pendant vertex of $T$.

Answer 1

First, here are some general ideas. In any graph, not just a tree, given a matching $M$ that is not perfect, we can try to find an augmenting path to improve the matching.

This is a path $v_0 v_1 v_2 \dots v_{2k+1}$ with the property that $v_1v_2, v_3 v_4, \dots, v_{2k-1} v_{2k}$ are edges of $M$, and $v_0$ and $v_{2k+1}$ are exposed. By deleting those $k$ edges of $M$, and adding the $k+1$ edges $v_0v_1, v_2v_3, \dots, v_{2k} v_{2k+1}$ instead, we get a bigger matching.

How might we find an augmenting path? Here is a procedure that may or may not work:

1. Start with any exposed vertex $v_0$.
2. Having found a vertex $v_{2i}$, if it has any exposed neighbor, let $v_{2i+1}$ be that neighbor, and stop.
3. Otherwise, if $v_{2i}$ has any neighbors whatsoever we haven't seen yet, let $v_{2i+1}$ be one of them, let $v_{2i+2}$ be the vertex it is matched to, and continue from $v_{2i+2}$.
4. Otherwise, if all of $v_{2i}$'s neighbors are already in the path, we give up. (Fancier algorithms do more here, but we don't need anything fancy for this problem.)

---

So let's say that $M$ is a matching in a tree $T$, and it leaves at least one vertex exposed. What can happen if we perform the procedure above on $T$?

• It could succeed in finding a bigger matching $M'$ with $|M'|=|M|+1$. We get the new matching we want by deleting an edge from $M'$.
• It could fail, stopping at a vertex $v_{2i}$ whose neighbors are all already on the path.

I claim that in the second case, $v_{2i}$ is a pendant vertex (prove this!) and we can use the path $v_0 v_1 v_2 \dots v_{2i}$ to make a new matching, of the same size as $M$, that leaves $v_{2i}$ exposed.

Answer 2

HINT: If $M$ exposes some pendant vertex, we’re done, so suppose that $M$ covers every pendant vertex. Root $T$ at a non-pendant vertex $v$, so that the pendant vertices are the leaves of $T$. From each leaf there is a unique path to $v$, and every vertex of $T$ is on at least one of those paths, so there is a leaf $u$ such that the path $P$ from $u$ to $v$ contains an exposed vertex. Let $w$ be the first exposed vertex that we encounter when travelling $P$ from $u$ to $v$.

If the edges of $P$, listed in order starting at $u$, are $e_1,e_2,\ldots,e_n$, show that the odd-numbered edges of $P$ are in $M$, and the even-numbered edges are not in $M$. Conclude that $n$ is even. Show that if you form $M_1$ by deleting from $M$ the odd-numbered edges of $P$ and adding the even-numbered edges, $M_1$ will be a matching that exposes $u$ and has the same cardinality as $M$.