# Prove that any tree contains a matching of size |InternalNodes|/2 [closed]

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

• What are internal nodes? Nodes whose degree is larger than 1? Aug 4 '19 at 7:49
• What have you tried? Where did you get stuck? Aug 4 '19 at 7:50
• Have you tried induction? Aug 4 '19 at 7:50
• 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? Aug 4 '19 at 9:27
• Hint : prove by induction that there exists a matching where all internal nodes are covered. 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.