Berge's theorem


In graph theory, Berge's theorem states that a matching M in a graph G is maximum if and only if there is no augmenting path with M.
It was proven by French mathematician Claude Berge in 1957.

Proof

To prove Berge's theorem, we first need a lemma. Take a graph G and let M and ' be two matchings in G. Let ' be the resultant graph from taking the symmetric difference of M and '; i.e. ∪. ' will consist of connected components that are one of the following:
  1. An isolated vertex.
  2. An even cycle whose edges alternate between M and '.
  3. A path whose edges alternate between M and ', with distinct endpoints.
The lemma can be proven by observing that each vertex in ' can be incident to at most 2 edges: one from M and one from '. Graphs where every vertex has degree less than or equal to 2 must consist of either isolated vertices, cycles, and paths. Furthermore, each path and cycle in ' must alternate between M and '. In order for a cycle to do this, it must have an equal number of edges from M and ', and therefore be of even length.
Let us now prove the contrapositive of Berge's theorem: 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 ' that is larger than M — just take ' to be the symmetric difference of P and M. Hence, the reverse direction follows.
For the forward direction, let ' be a matching in G larger than M. Consider D, the symmetric difference of M and '. Observe that D consists of paths and even cycles. Since ' is larger than M, D contains a component that has more edges from ' than M. Such a component is a path in G that starts and ends with an edge from ', so it is an augmenting path.

Corollaries

Corollary 1

Let M be a maximum matching and consider an alternating chain such that the edges in the path alternates between being and not being in M. If the alternating chain is a cycle or a path of even length starting on an unmatched vertex, then a new maximum matching can be found by interchanging the edges found in M and not in M. For example, if the alternating chain is, where mi ∈ M and ni ∉ M, interchanging them would make all ni part of the new matching and make all mi not part of the matching.

Corollary 2

An edge is considered "free" if it belongs to a maximum matching but does not belong to all maximum matchings. An edge e is free if and only if, in an arbitrary maximum matching M, edge e belongs to an even alternating path starting at an unmatched vertex or to an alternating cycle. By the first corollary, if edge e is part of such an alternating chain, then a new maximum matching, ', must exist and e would exist either in M or ', and therefore be free. Conversely, if edge e is free, then e is in some maximum matching M but not in '. Since e is not part of both M and ', it must still exist after taking the symmetric difference of M and '. The symmetric difference of M and ' results in a graph consisting of isolated vertices, even alternating cycles, and alternating paths. Suppose to the contrary that e belongs to some odd-length path component. But then one of M and ' must have one fewer edge than the other in this component, meaning that the component as a whole is an augmenting path with respect to that matching. By the original lemma, then, that matching cannot be a maximum matching, which contradicts the assumption that both M and ' are maximum. So, since e cannot belong to any odd-length path component, it must either be in an alternating cycle or an even-length alternating path.