= Solution
We construct an <injection> from the <unmatched vertices in a matching> to the <leaves of a rooted tree>. Start a downward <graph path> at each unmatched <vertex> $u$. If the current <vertex> is a <leaf of a rooted tree>, stop. Otherwise choose any child $v$. The current <vertex> is either the unmatched starting point or a <vertex> already matched to its own parent.
In either case, $v$ cannot be unmatched: the <proper matching in a rooted tree> condition would require its parent to be matched to one of $v$'s <siblings in a rooted tree>, whereas that parent is either unmatched or already matched upward. Nor can $v$ be matched to its parent. Its matching partner must therefore be one of its own children, say $w$. Extend the <graph path> by the two <edges> to $v$ and then to $w$, and continue from $w$.
Every extension descends two levels, so finiteness guarantees termination at a <leaf of a rooted tree>. Every visited <vertex> except the starting point is matched. The constructed <graph paths> for different unmatched starting points are disjoint: if two downward <graph paths> in a <tree> meet, one starting point must lie on the other path, which would put a second unmatched <vertex> after the first. That is impossible. Hence their terminal <leaves of a rooted tree> are distinct, proving
$$
\boxed{|U(M)|\leq|L(T)|.}
$$
Only the properness condition for unmatched non-root <vertices> was used. If the root is unmatched and the convention exempts it because it has no parent, the same construction starts there and still works. Thus the root convention does not affect the claimed inequality. This proves the <unmatched-vertex bound for a proper tree matching> without requiring $M$ to have maximum size.
Back to article page
