1
$\begingroup$

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

$\endgroup$
5
  • $\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
0
$\begingroup$

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.

$\endgroup$

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