How can i prove that any tree contains a matching of size |InternalNodes|/2? Thanks in advance

  • $\begingroup$ What are internal nodes? Nodes whose degree is larger than 1? $\endgroup$ Aug 4 '19 at 7:49
  • $\begingroup$ What have you tried? Where did you get stuck? $\endgroup$ Aug 4 '19 at 7:50
  • $\begingroup$ Have you tried induction? $\endgroup$ Aug 4 '19 at 7:50
  • $\begingroup$ internal node is a node that is not a leaf. I don't event know where to start. You suggest to prove it by induction? $\endgroup$
    – user108220
    Aug 4 '19 at 9:27
  • $\begingroup$ Hint : prove by induction that there exists a matching where all internal nodes are covered. $\endgroup$
    – Tassle
    Aug 4 '19 at 11:41

You can prove the following stronger claim by induction:

Given a rooted tree containing more than one vertex, there is a matching which covers all non-leaf nodes.

The proof is quite simple – we match the root to an arbitrary child, remove the edge, and recurse on the remaining rooted trees. Each remaining tree in which the root is a non-leaf in the original tree will contain more than one vertex, and so the induction hypothesis applies.

I'll let you come up with the details.


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