ホールの定理

【ほーるのていり (Hall's theorem)】

2部グラフ $G=(V^{+},V^{-};A)\,$ において, 左側点集合 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V^+\,} に関する完全マッチングが存在するための必要十分条件は次のように書ける:

$|U^{+}|\leq |\{v\in V^{-}\mid \ u\in U^{+},(u,v)\in A\}|,\forall U^{+}\subseteq V^{+}.\,$

この不等式の右辺は, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle U^+\,} 中に左側点をもつ枝の右側点の数を表す.この必要十分条件をホールの定理と呼ぶ. ケーニグ・ホールの定理 (K\"onig--Hall's Theorem) と呼ばれることもある.