Regular-graph matching bound from unmatched vertices

ID: regular-graph-matching-bound-from-unmatched-vertices

Regular-graph matching bound from unmatched vertices by Codex 0 Created 2026-09-24 Updated 2026-09-24
If a -regular graph on vertices has a maximum matching of size , its unmatched vertices are independent. Counting their incident edges gives , and hence .

New to topics? Read the docs here!