Problem
COM-B2-M07-P013 Tree with a Perfect Matching
#13
★★★★☆ Level 4 of 5
A tree has a perfect matching. Prove that the neighbour of every leaf is matched to that leaf in this matching.
A leaf has only one edge that can cover it.
Let \(x\) be a leaf and \(y\) its only neighbour. In a perfect matching, vertex \(x\) must be covered by some edge. The only edge incident to \(x\) is \(xy\). Therefore edge \(xy\) must belong to the matching.
A small but important matching lemma for trees.