Berge Lemma

Berge's lemma states that the matching M in the graph G is the largest (contains the greatest possible number of edges) if and only if there is no extending path (a path that starts and ends on free, that is, those that do not belong to matching, vertices and alternately travels along edges belonging and not belonging to matching) in M.

The lemma was proved by the French mathematician Claudi Berge in 1957 (although it was already discussed by Petersen in 1891 and Koenig in 1931).

Content

1 Proof
2 Consequences
- 2.1 Corollary 1
- 2.2 Corollary 2
3 notes
4 Literature

Proof

To prove Berge's lemma, we first need another lemma . Take the graph G and let M and M ′ be two matching in G. Let G ′ be the result of taking the symmetric difference M and M ′ . I.e $(M\setminus M')\cup (M'\setminus M)$ ${\ displaystyle (M \ setminus M ') \ cup (M' \ setminus M)}$ . G ′ will consist of components that belong to the following groups:

Isolated top .
An even cycle whose edges alternately belong to M and M.
A path with different end points, whose edges alternately belong to M and M.

The lemma can be proved if we notice that any vertex from G ′ can be incident to at most two edges — one from M and one from M ′ . Graphs in which any vertex has degree not exceeding 2 must consist of isolated vertices , loops, and paths . Moreover, every path and cycle in G must be contained in M and M in turn. In order for the cycle to behave this way, it must have an equal number of edges from M and M , and therefore an even length.

Now we can prove the Berge lemma by contradiction - the graph G has matching more than M if and only if G has an extending path. It is clear that the extending path P of the graph G can be used to obtain a matching M ′ that is larger than the matching M - just take the symmetric path difference P and M as M ′ ( M ′ consists exactly of the edges of G that appear exactly once in the path P , or in the matching M ). The proof follows in the opposite direction.

For the proof in the forward direction, we assume that M is a matching of the graph G greater than the matching M. Consider the symmetric difference M and M as D. Note that D consists of paths and even cycles (as was noted in an earlier lemma ). Since M is greater than M , D contains a component that has more edges from M than from M. Such a component is a path in G that starts and ends with an edge from M , so that it is an extension.

Consequences

Corollary 1

Let M be the largest matching, and consider an alternating chain such that edges in the path alternate between belonging and not belonging to M. If the alternating chain is a cycle or a path of even length, then a new largest matching M ′ can be found by exchanging edges between M and not from M. For example, if an alternating chain is $(m_{1},n_{1},m_{2},n_{2},\dots )$ ${\ displaystyle (m_ {1}, n_ {1}, m_ {2}, n_ {2}, \ dots)}$ where $m_{i}\in M$ ${\ displaystyle m_ {i} \ in M}$ , but $n_{i}\notin M$ ${\ displaystyle n_ {i} \ notin M}$ . The exchange of these edges will make all n _i part of the new matching, and all m _i will not be included in the matching.

Corollary 2

An edge is considered “free” if it belongs to the largest matching, but not to all the largest matching. An edge e is free if and only if, in an arbitrary greatest matching M, the edge e belongs to an even alternating path that starts at an uncovered vertex or belongs to an alternating cycle . By the first corollary, if an edge e is part of such an alternating chain, then there must exist a new largest matching M ′ and e will belong to either M or M ′ , and therefore be free. In the opposite direction, if the edge e is free, then e is in some greatest matching M , but not in M ′ . Since the edge e does not belong simultaneously to M and M , it must be present in the symmetric difference of M and M. The symmetric difference M and M ′ gives a graph consisting of isolated vertices, even alternating cycles, and alternating paths of even length. Suppose this is not so and e belongs to some path of odd length. But then one of the matching M or M ′ should have fewer edges in this component, which means that this component as a whole is an expanding way for this matching. By the original lemma, then this matching ( M or M ′ ) cannot be the largest, which contradicts the assumption that both matching M and M ′ are the largest. Thus, since e cannot belong to any component of the path of odd length, it must either lie in the cycle of even length, or on an alternating path of even length.

Notes

Literature

Claude Berge. Two theorems in graph theory // Proceedings of the National Academy of Sciences of the United States of America . - 1957. - September 15 ( t. 43 , issue 9 ). - S. 842–844 . - DOI : 10.1073 / pnas . 43.9.842 .
Douglas B. West. Introduction to Graph Theory. - 2nd. - Pearson Education, Inc., 2001. - S. 109-110. - ISBN 81-7808-830-4 .
Claude Berge. Graphs and Hypergraphs. - North-Holland Publishing Company, 1973. - S. 122–125. - ISBN 0-444-10399-6 .