Tutte's Theorem

Let $G$ be a Graph and $S$ a Subgraph of $G$. Let the number of Odd components in $G-S$ be denoted $S'$, and $\vert S\vert$ the number of Vertices of $S$. The condition $\vert S\vert\geq S'$ for every Subset of Vertices is Necessary and Sufficient for $G$ to have a 1-Factor.

See also Factor (Graph)

References

Honsberger, R. ``Lovász' Proof of a Theorem of Tutte.'' Ch. 14 in Mathematical Gems II. Washington, DC: Math. Assoc. Amer., pp. 147-157, 1976.

Tutte, W. T. ``The Factorization of Linear Graphs.'' J. London Math. Soc. 22, 107-111, 1947.