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

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.

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).