In graph theory, Berge's lemma 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.^[1]

[edit] References