Proof of Tutte's theorem via an edge-maximal counterexample

Proof

For a graph $H$ on $V$ and $U \subseteq V$, write $o(H - U)$ for the number of odd connected components of $H - U$. Say that $H$ satisfies Tutte's condition if $o(H - U) \le \abs{U}$ for all $U \subseteq V$. Let $G$ be a finite graph with vertex set $V$.

The condition is necessary.

1. Let $M$ be a perfect matching of $G$, and let $U \subseteq V$. Let $K$ be an odd component of $G - U$.
2. The edges of $M$ inside $K$ cover an even number of vertices of $K$. As $\abs{K}$ is odd, some vertex $x_K \in K$ is matched to a vertex $y_K \notin K$.
3. There are no edges between different components of $G - U$, so $y_K \in U$.
4. Distinct odd components give distinct vertices $x_K$. Since $M$ is a matching, they also give distinct $y_K$. So $K \mapsto y_K$ is injective, and $o(G - U) \le \abs{U}$.

The condition is sufficient: setup.

5. Suppose that $G$ satisfies Tutte's condition but has no perfect matching. We derive a contradiction.
6. For $U = \varnothing$, the condition gives $o(G) = 0$. So every component of $G$ is even, and $\abs{V}$ is even.
7. Among all graphs on $V$ that contain every edge of $G$ and have no perfect matching, choose one, $G^*$, with the most edges. Then $G^* + uv$ has a perfect matching for any two nonadjacent vertices $u \ne v$ of $G^*$.
8. The graph $G^*$ satisfies Tutte's condition. Let $U \subseteq V$. Each component of $G^* - U$ is a union of components of $G - U$, since $G$ is a subgraph of $G^*$.
9. A union of even sets is even, so each odd component of $G^* - U$ contains an odd component of $G - U$. These are distinct for distinct components. So $o(G^* - U) \le o(G - U) \le \abs{U}$.
10. Let $S$ be the set of vertices of $G^*$ adjacent to all other vertices.

Case 1: every component of $G^* - S$ is a complete graph.

11. Let $K_1, \dots, K_k$ be the odd components of $G^* - S$. By Step 8, $k \le \abs{S}$. Choose distinct $s_1, \dots, s_k \in S$ and vertices $x_i \in K_i$.
12. Match $x_i$ with $s_i$; this is an edge, since $s_i \in S$. The set $K_i \setminus \set{x_i}$ is even and complete, so pair up its vertices by edges.
13. Pair up the vertices of each even component in the same way.
14. Let $S' = S \setminus \set{s_1, \dots, s_k}$. Modulo $2$, $\abs{V} = \abs{S} + \sum_{\text{components}} \abs{K} \equiv \abs{S} + k$. As $\abs{V}$ is even, $\abs{S'} = \abs{S} - k$ is even.
15. Any two vertices of $S$ are adjacent, so pair up the vertices of $S'$ by edges.
16. Steps 12 to 15 give a perfect matching of $G^*$. This contradicts Step 7.

Case 2: some component $K$ of $G^* - S$ is not complete.

17. Choose nonadjacent vertices of $K$ and a shortest path in $K$ between them. Let $a, b, c$ be its first three vertices. Then $ab$ and $bc$ are edges and $a, c$ are not adjacent, by minimality of the path.
18. Since $b \in K$, $b \notin S$. So there is a vertex $d \ne b$ not adjacent to $b$. Then $d \ne a, c$.
19. By Step 7, $G^* + ac$ has a perfect matching $M_1$, and $G^* + bd$ has a perfect matching $M_2$. Then $ac \in M_1$ and $bd \in M_2$, since $G^*$ has no perfect matching.
20. Also $bd \notin M_1$ and $ac \notin M_2$, since these are not edges of $G^* + ac$ and $G^* + bd$ respectively.
21. Let $D = M_1 \mathbin{\triangle} M_2$ be the symmetric difference. Each vertex lies on one edge of $M_1$ and one of $M_2$. So it lies on $0$ or $2$ edges of $D$, one from each matching.
22. Hence $D$ is a disjoint union of cycles whose edges alternate between $M_1$ and $M_2$. By Step 20, $bd \in D$. Let $C$ be the cycle of $D$ through $bd$.
23. At each vertex of $C$, both its $M_1$-edge and its $M_2$-edge lie on $C$. So edges of $M_1$ or $M_2$ not on $C$ have no end on $C$.
24. Case 2a: $ac \notin C$. Let $M = (M_2 \setminus C) \cup (M_1 \cap C)$. The edges $M_1 \cap C$ cover each vertex of $C$ once, and $M_2 \setminus C$ covers each other vertex once, by Step 23.
25. So $M$ is a perfect matching. It avoids $bd$, which is on $C$ and not in $M_1$, and it avoids $ac$, which is not on $C$ and not in $M_2$. So $M$ is a perfect matching of $G^*$, a contradiction.
26. Case 2b: $ac \in C$. Walk along $C$ from $b$ through $d$, and stop at the first vertex $u \in \set{a, c}$. This exists, since $a, c$ lie on $C$ and $b, d \notin \set{a, c}$. Let $P$ be the part of $C$ from $d$ to $u$.
27. The path $P$ does not contain $ac$, since we stop on first reaching an end of $ac$. So $P$ reaches $u$ along the other $C$-edge at $u$, which is the $M_2$-edge of $u$.
28. The first edge of $P$ is the $M_1$-edge of $d$, as the $M_2$-edge of $d$ is $bd$. So the edges of $P$ alternate, starting in $M_1$ and ending in $M_2$.
29. The edge $ub$ is an edge of $G^*$ by Step 17. Let $C'$ be the cycle formed by $bd$, $P$ and $ub$. Its edges in order are $bd \in M_2$, then $P$ alternating from $M_1$ to $M_2$, then $ub$.
30. Let $N$ consist of $ub$ and the $M_1$-edges of $P$. These are every second edge of $C'$, so $N$ covers each vertex of $C'$ exactly once. No edge of $N$ is $ac$ or $bd$.
31. Each vertex of $C'$ has its $M_2$-edge on $C'$: for $b$ this is $bd$, and for the other vertices it lies on $P$. So the edges of $M_2$ not on $C'$ have no end on $C'$.
32. Let $M = (M_2 \setminus C') \cup N$. By Steps 30 and 31, $M$ is a perfect matching of $G^*$, since it avoids $bd$. This contradicts Step 7.
33. All cases lead to a contradiction. So $G$ has a perfect matching whenever it satisfies Tutte's condition.