= Tutte's theorem on perfect matchings
{c}
{title2=$o(G-S)\leq |S|\quad\text{for every }S\subseteq V(G)$}
{wiki}
= Tutte theorem
{c}
{synonym}
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>.<Non-bipartite matching lecture notes by MIT>[final paragraph, the criterion for a perfect matching]{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>.
Back to article page
