= 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$.
Back to article page
