Berge's lemma
Encyclopedia
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.
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.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, Berge's lemma states that a matching M in a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
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
Claude Berge
Claude Berge was a French mathematician, recognized as one of the modern founders of combinatorics and graph theory. He is particularly remembered for his famous conjectures on perfect graphs and for Berge's lemma, which states that a matching M in a graph G is maximum if and only if there is in...
in 1957.
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 differenceSymmetric difference
In mathematics, the symmetric difference of two sets is the set of elements which are in either of the sets and not in their intersection. The symmetric difference of the sets A and B is commonly denoted by A\,\Delta\,B\,orA \ominus B....
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.