ホールの結婚定理

必要性は、$X$ を飽和するマッチングが各 $W \subseteq X$ を $N(W)$ の中へ単射に写すことから直ちに従う。十分性は $|X|$ に関する帰納法による：すべての空でない真部分集合 $W \subset X$ について $|N(W)| \ge |W|+1$ であれば、任意の $x \in X$ を任意の $y \in N(\{x\})$ と組にし、ホールの条件が保たれる $G - \{x,y\}$ に帰納法を適用する。そうでなければ $|N(W)| = |W|$ となる空でない真部分集合 $W$ が存在するので、帰納法により $W$ を $N(W)$ にマッチングさせ、さらに $G - (W \cup N(W))$ において $X \setminus W$ がホールの条件を満たすことを確かめて、残りの頂点も帰納法によりマッチングさせる。