ホールの定理

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

2部グラフ $G=(V^{+},V^{-};A)\,$ において, 左側点集合 構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle V^{+}\,}
 に関する完全マッチングが存在するための必要十分条件は次のように書ける: 

 構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle |U^{+}|\leq |\{v\in V^{-}\mid \ u\in U^{+},(u,v)\in A\}|,\forall U^{+}\subseteq V^{+}.\,}

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