Proving that the number of leaves in a tree >= number of unmatched vertices

Question

Consider a rooted tree $T$. A matching in $T$ is said to be proper if for every unmatched vertex $v$ it holds that the parent of $v$ is matched to one of the siblings of $v$. It is known that every tree admits a maximum-size matching that is proper.

Consider a rooted tree $T$ over a set of vertices $V$ and a proper matching $M$ in $T$; we can think of $M$ as a collection of edges. Let $L(T)$ be the set of leaves of $T$, and let $U(M)$ be the set of vertices not matched by $M$ (i.e., $U(M) = \{v ∈ V | v \notin e \space \forall e ∈ M\}$). Prove that $|L(T)| ≥ |U(M)|$.

My attempt:

The set of internal nodes in $T$ form a valid vertex cover. The size of any vertex cover >= the size of any matching.

$=> |V| - |internal \space nodes| <= |V| - |M|$

$=> |L(T)| <= |V| - |M|$

I can prove that $|M| <=$ number of nodes being matched in the matching, and I guess I've to relate that to being less than $L(T)$ but I haven't figured out a way to do this.

Answer 1

Prove it by induction. It is true for trees with |V|<=3. Suppose that it is true for trees with |V|=n-1 and we want to prove it for a tree T with |V|=n.

If there exist a leaf v which is unmatched then by removing v, we have a tree T' and a proper matching M' where L(T')=L(T)-1, U(M')=U(M)-1 and L(T')>=U(M'). Then, L(T)>=U(M).

Else, all of vertices in F={v| v is a leaf} are matched by matching M. This means that all of leaves have no sibling which be a leaf. Hence, by removing a leaf v and its parent, we have a Tree T_v on a subset of V-{v, Parent of v, all subtrees on siblings of v} and some trees T'_v on siblings of v.

If we remove all of vertices in F and their parents, we have: V = Union of the removed vertices and the trees T_v for all vertices v in F. Note that, it is possible that T_v be equal to T_u for u and v in F. Then, by deleting similar trees, suppose that we have different trees T_v.

Then, let M_v be the matching on T_v. Based on induction, we have L(T_v) >= U(M_v). Moreover,

we have L(T) >= SUM(L(T_v)) (for each leaf in T_v we have at least a leaf in T)

and we have SUM(U(M_v)) = U(M)

and this concludes that L(T)>=U(M).