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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.