How to determine the relation between the size of a maximum matching and a maximum independent set in a tree?

Question

Let T be a tree, M a maximum matching, and $\alpha(T) = k$. Find a relation between $|M|$, $|V(T)|$ and $k$.

---

After drawing many small trees I always find $|M| = |V(T)| - k$, but I have no idea how to proof that this is indeed the relation.

Answer 1

By Kőnig's theorem, $|M|$ is also equal to $\beta(T)$: the size of a minimum vertex cover of $T$. (This is true more generally in any bipartite graph).

It's true that $\alpha(G) + \beta(G) = |V(G)|$ in any graph $G$. In fact, more is true:

• an independent set includes at most one endpoint of each edge, and
• a vertex cover includes at least one endpoint of each edge,

so the complement of any independent set is a vertex cover, and vice versa.

Putting these together, if $G$ is a bipartite graph with maximum matching $M$, we have $\alpha(G)+ |M| = |V(G)|$.