Konig 定理（Konig's theorem）
/ KUR-nig /
在二分圖中，兩個自然的量朝相反方向拉扯。匹配是一組沒有共用端點的邊——你想要愈多愈好。頂點覆蓋是一組碰到每條邊的頂點——你想要愈少愈好。Konig 定理是個醒目的陳述：在任何二分圖中，這兩個最佳值相等：最大的匹配與最小的頂點覆蓋大小恰好相同。
形式上，二分圖中匹配的最大邊數等於頂點覆蓋的最小頂點數。一個方向容易：匹配的每條邊都需要自己的覆蓋頂點，故任何覆蓋至少和任何匹配一樣大，得 最小覆蓋 >= 最大匹配。反向（等號）才是重點，而最乾淨的證明走流。把最大二分圖匹配以單位容量建模成最大流；最大流最小割定理給出一個容量等於匹配大小的最小割，而把該割對照到二分結構上讀出來，就得到一個恰為該大小的頂點覆蓋。於是 最小頂點覆蓋 <= 最大匹配，兩者相會。因此 Konig 定理是匹配網路上最大流最小割的組合面貌。
Konig 定理之所以重要，是因為它是一個你能計算並利用的極小極大對偶：在二分圖中找一個最大匹配，同時就交給你一個最小頂點覆蓋（且由取補，得一個最大獨立集），全在多項式時間內。這很特別——最小頂點覆蓋在一般圖中是 NP 困難，而二分情形是少數可解的之一，正是因為這個定理。它也連到 Hall 定理：Konig 的等號正是讓 Hall 條件既必要又充分的原因。要記住的提醒：Konig 定理只對二分圖成立；在有奇環的圖中等號可能失效。
左 {a, b}、右 {x, y}，邊 a-x、a-y、b-x。最大匹配大小為 2（例如 a-y 與 b-x）。也存在大小為 2 的頂點覆蓋：{a, x} 碰到全部三條邊。沒有單一頂點能覆蓋所有邊，故 最小覆蓋 = 2 = 最大匹配，正如 Konig 所保證。
在二分圖中最大匹配與最小頂點覆蓋重合——一次多項式計算同時得到兩者。
Konig 的等號是二分圖特有的。最小頂點覆蓋在一般圖中是 NP 困難；匹配等於覆蓋的對偶正是讓二分情形容易的原因，而一旦出現奇環它就失效。