最大マッチング最小被覆定理

【さいだいまっちんぐさいしょうひふくていり (maximum-matching minimum-cover theorem)】

2部グラフ 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G = (V, A) \,} において, 最大マッチングの枝数と最小被覆の点数は等しい, すなわち

$\max\{|M|\mid M\subseteq A$は $G\,$ のマッチング $\}\,$

$\ \ \ \ \ =\min\{|U|\mid U\subseteq V\,$ は $G\,$ の被覆 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \} \,}

という定理. ケーニグ(K\"onig)の定理, またはケーニグ・エゲルヴァーリ(K\"onig--Egerv\'ary)の定理とも呼ばれる.