Augmenting Path Theorem of Matchings

Last updated Nov 7, 2022

Suppose $G = (V, E)$ is an Undirected Graph and $M$ is a Matching on $G$. Then $M$ is a Maximum Matching on $G$ If and Only If there is no $M$-augmenting path.

TODO - See Cook - Combinatorial Optimization page 129 for details.

• Cook - Combinatorial Optimization - Ch 5, Section 5.1, page 129
• Berge - Two Theorems in Graph Theory(1957) - original source