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 maximummatching if and only if G has no M-augmentingpath.}$

$\text{Proof. }$ $\Leftarrow$: Suppose M is not a maximum matching. If there is a matching M’ larger than M, we let $S:=E(M)\mathrm{△}E(M^{\prime })$. 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

Comments