Lesson 7

Theorem (Berge, 1958). For every graph \(G\), \[\operatorname{def}(G)=\max_{S\subseteq V(G)}(o(G-S)-|S|) \ .\]

Before the proof, let us see the formula on a small example. In the graph below, deleting the central vertex \(c\) leaves three odd components: three five-vertex lobes.

For \(S=\{c\}\) we get \[o(G-S)-|S|=3-1=2 \ .\] Thus at least two vertices must remain uncovered, so \(\alpha'(G)\le (16-2)/2=7\). The colored edges show a matching of size \(7\). Hence the bound is tight here, and the maximum matching has exactly seven edges.

Let \(M\) be a maximum matching, and fix any set \(S \subseteq V(G)\). In each odd component of \(G-S\), either one vertex is not covered by \(M\), or some vertex is matched by \(M\) to a vertex of \(S\). Since different such components need different vertices of \(S\), at least \(o(G-S)-|S|\) vertices remain uncovered. Therefore \[\operatorname{def}(G) \ge o(G-S)-|S|\] for every \(S\), and hence \[\operatorname{def}(G) \ge \max_{S\subseteq V(G)}(o(G-S)-|S|) \ .\]

Now prove the opposite inequality. Let \[k=\max_{S\subseteq V(G)}(o(G-S)-|S|) \ .\] For every \(S \subseteq V(G)\), the number \(o(G-S)-|S|\) has the same parity as \(|V(G)|\). Indeed, modulo \(2\), the number of odd components of \(G-S\) is equal to \(|V(G-S)|=|V(G)|-|S|\), and subtracting \(|S|\) leaves the parity of \(|V(G)|\). Hence \(k \equiv |V(G)| \pmod 2\).

If \(k=0\), then Tutte's theorem gives a perfect matching, and there is nothing to prove.

Assume \(k>0\). Add a set \(W\) of \(k\) new vertices, and connect every vertex of \(W\) to every other vertex of the new graph. Call the resulting graph \(H\). We claim that \(H\) satisfies Tutte's condition.