ホールの定理

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

2部グラフ $G = (V^+, V^-; A)\,$ において, 左側点集合 $V^+\,$ に関する完全マッチングが存在するための必要十分条件は次のように書ける:

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

この不等式の右辺は, $U^+\,$ 中に左側点をもつ枝の右側点の数を表す.この必要十分条件をホールの定理と呼ぶ. ケーニグ・ホールの定理 (K\"onig--Hall's Theorem) と呼ばれることもある.