Berge's theorem

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. (M'' - ') ∪ (' - M). '''' will consist of connected components that are one of the following: • An isolated vertex. • An even cycle whose edges alternate between M and ''''. • 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 ( contains exactly those edges of G that appear in exactly one 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 (as observed by the earlier lemma). 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 (m1, n1, m2, n2, ...), where mi ∈ M and ni ∉ M, interchanging them would make all ni part of the new matching and make all m''i 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 (whether M or ) 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. == References ==