Lesson 3

Theorem (Tutte, 1947). A graph \(G\) has a perfect matching if and only if \[o(G-S) \le |S|\] for every set \(S \subseteq V(G)\).

We have already proved the necessity of the condition.

Now assume that the condition holds, but \(G\) has no perfect matching. Add edges to \(G\) as long as this does not create a perfect matching. We get a maximal supergraph \(G^{\star}\) on the same vertex set, still without a perfect matching.

Adding edges cannot increase the number of odd components after deleting any set of vertices. Therefore \(G^{\star}\) also satisfies Tutte's condition. Also, \(|V(G^{\star})|\) is even, since \(o(G^{\star}) \le 0\).

Let \[U=\{u \in V(G^{\star}) \colon d_{G^\star}(u)=|V(G^{\star})|-1\}\] be the set of vertices adjacent to all other vertices. We will use the following lemma.