= Unmatched-vertex bound for a proper tree matching
{title2=$|U(M)|\leq|L(T)|$}
For a <proper matching in a rooted tree>, the number of <unmatched vertices in a matching> does not exceed the number of <leaves of a rooted tree>. From each unmatched <vertex>, build a downward path: at an internal current node that is unmatched or matched upward, every child must be matched downward to one of its own children, or properness would fail. Follow a child and its matching partner, then repeat. The path terminates at a leaf and contains no other unmatched <vertex>. Two such downward paths cannot meet, since then one unmatched starting point would lie on the other's path. Their distinct endpoints give the required <injection>. No maximum-size assumption is needed.
Back to article page
