Lesson 5

Let us finish the proof of Tutte's theorem.

By the lemma, \(G^{\star}-U\) is a disjoint union of complete graphs. Apply Tutte's condition to the set \(U\). Then the number of odd components of \(G^{\star}-U\) is at most \(|U|\).

In every even complete component, choose a perfect matching inside the component. In every odd complete component, choose a matching that covers all vertices except one, and match this remaining vertex to a distinct vertex of \(U\). This is possible because there are at most \(|U|\) odd components.

After that, some vertices of \(U\) may remain unused. Their number is even: the whole graph has an even number of vertices, and all other vertices have already been covered. Since all vertices of \(U\) are adjacent to each other, we can pair the remaining vertices of \(U\) arbitrarily. Thus \(G^{\star}\) has a perfect matching.