Berge's theorem

A matching, denoted in blue, is shown to not be a maximum cardinality matching because of the presence of an augmenting path, with endpoints at the yellow vertices.

In graph theory, Berge's theorem states that a matching M in a graph G is maximum (contains the largest possible number of edges) if and only if there is no augmenting path (a path that starts and ends on free (unmatched) vertices, and alternates between edges in and not in the matching) with M.

It was proven by French mathematician Claude Berge in 1957 (though already observed by Petersen in 1891 and Kőnig in 1931).