Lesson 8

First consider \(T=\varnothing\). Since \(k \equiv |V(G)| \pmod 2\), the graph \(H\) has an even number of vertices. Also, \(H\) is connected because \(k>0\). Thus \(o(H)=0\).

Now let \(T \subseteq V(H)\) be nonempty. We need to prove that \(o(H-T)\le |T|\).

If \(T\) does not contain all vertices of \(W\), then \(H-T\) has a vertex from \(W\). This vertex is adjacent to all other remaining vertices, so \(H-T\) is connected. Hence \(o(H-T)\le 1 \le |T|\).

Now suppose \(T=W \cup S\), where \(S \subseteq V(G)\). Then \[o(H-T)=o(G-S) \le k+|S|=|T| \ ,\] by the definition of \(k\).

So \(H\) satisfies Tutte's condition and therefore has a perfect matching \(N\). After deleting from \(N\) all edges incident to vertices of \(W\), we get a matching in \(G\) that covers at least \(|V(H)|-2k=|V(G)|-k\) vertices of \(G\). Therefore \[\alpha'(G) \ge \frac{|V(G)|-k}{2}\ ,\] which is the same as \(\operatorname{def}(G)\le k\). This completes the proof of Berge's formula.

Equivalently, the maximum size of a matching is \[\alpha'(G)=\frac{|V(G)|-\operatorname{def}(G)}{2}=\frac{|V(G)|-\max_{S\subseteq V(G)}(o(G-S)-|S|)}{2}\ .\]