Project
- This is the class note of Extremal Combinatorics, whose chapter 12 was typeset by me.
- A hard exercise on Diestel(ex1, chp2) whose proof I had to find on Internet.
\(\text{Theorem(Berge 1957) A matching M in a graph G is a maximum matching if and only if G has no M-augmenting path.}\)
\(\text{Proof. }\) \(\Leftarrow\): Suppose M is not a maximum matching. If there is a matching M’ larger than M, we let \(S:=E(M)\triangle E(M')\). Let H be the graph formed by the edges in S and their endpoints.
Since both M and M’ are matchings, every vertex of H has degree at most 2. So H is a collection of disjoint paths and cycles. Every cycle and path must be M-alternating so every cycle must be even, for if a component is not M-alternating then there would be two adjacent M-edges. Since M’ is larger than M, H must contain more M’-edges than M-edges. Therefore there must be a component of H that contains more M’-edges than M-edges, which must be a path starting and ending with an M’-edge, say P. It cannot be a cycle as all cycles contain the same number of M and M’ edges. So P is an M-alternating path whose endpoints are M-unmatched. Thus P is an M-augmenting path, contradicting to the maximality of M.
\(\Rightarrow\) is trivial. QED