Tutte's theorem on perfect matchings ($o(G-S)\le |S|\text{for every }S\subseteq V(G)$)

A finite graph has a perfect matching if and only if the displayed inequalities hold, where $o(H)$ counts the connected components of a graph $H$ with an odd integer number of vertices. The theorem is associated with William Thomas Tutte.^[ref]

Necessity has a direct counting proof: each such component of $G-S$ must send at least one edge of a perfect matching to $S$, and different components must use different vertices of $S$. The sufficiency direction is the substantive content of the theorem. The criterion is useful because vertex degree and parity estimates can prove existence without constructing the perfect matching, as in the perfect matching theorem for a cubic graph with at most two bridges.