Berge's lemma
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 (though already observed by Petersen in 1891 and Kőnig in 1931).
[edit] Proof
Let us prove the contrapositive: G has a matching larger than M if and only if G has an augmenting path. Clearly, an augmenting path P of G can be used to produce a matching M′ that is larger than M — just take M′ to be the symmetric difference of P and M (M′ contains exactly those edges of G that appear in exactly one of P and M). Hence, the backward direction follows.
For the forward direction, let M′ be a matching in G larger than M. Consider D, the symmetric difference of M and M′. Observe that D consists of paths and even cycles (each vertex of D has degree at most two and edges belonging to some path or cycle must alternate between M and M′). Since M′ is larger than M, D contains a component that has more edges from M′ than M. Such a component is a path in G that starts and ends with an edge from M′, so it is an augmenting path.
[edit] References
- Berge, Claude (September 15, 1957), "Two theorems in graph theory", Proceedings of the National Academy of Sciences of the United States of America 43 (9): 842–844, http://www.pnas.org/content/43/9/842.full.pdf.
- West, Douglas B. (2001), Introduction to Graph Theory (2nd ed.), Pearson Education, Inc., p. 109, ISBN 81-7808-830-4.
