Tutte's theorem

Statement

Let $G$ be a finite graph with vertex set $V$. For $U \subseteq V$, let $o(G - U)$ be the number of connected components of $G - U$ with an odd number of vertices. Then $G$ has a perfect matching if and only if $o(G - U) \le |U|$ for every $U \subseteq V$.

Remarks

The condition is necessary. In a perfect matching, each odd component of $G - U$ has a vertex that is matched to a vertex of $U$. These vertices of $U$ are distinct. For $U = \varnothing$, the condition says that each component of $G$ has an even number of vertices. The theorem is a special case of the Tutte–Berge formula for the size of a maximum matching.

History

The theorem is named after William Thomas Tutte.

Explanations

L1 human

Delete some vertices, and count the pieces with an odd number of vertices that remain. Each odd piece needs a partner among the deleted vertices, and Tutte's theorem says this is the only obstruction.