Proper matching in a rooted tree

ID: 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 rooted at , selecting only gives a maximal matching in a graph, but unmatched has parent matched upward rather than to a sibling of .

New to topics? Read the docs here!