Proper matching in a rooted tree

A matching in a graph on a rooted tree has the sibling-support condition if every unmatched non-root vertex has its parent matched to one of its siblings in a rooted tree. This is the properness condition used here. The root has no parent, so either exempt an unmatched root or require it to be matched in a nontrivial instance; the unmatched-vertex bound for a proper tree matching holds under either convention. Properness is stronger than being maximal: on the path $r-a-b-c$ rooted at $r$, selecting only $ab$ gives a maximal matching in a graph, but unmatched $c$ has parent $b$ matched upward rather than to a sibling of $c$.

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.