Hall 婚配定理（Hall's marriage theorem）
/ HAWL /
想像一個小鎮，一側的每個人都有一份另一側、他們願意結婚的對象名單，而我們想讓第一側的每個人都成婚，各自配到自己名單裡的一個不同伴侶。什麼時候辦得到？Hall 婚配定理給出精確且出奇簡單的條件：當且僅當沒有任何一群人集體上太挑。
形式上，取一個左側為 L、右側為 R 的二分圖；我們尋求一個飽和 L 的匹配（讓每個左頂點都被匹配）。對 L 的任一子集 A，令 N(A) 為與 A 中至少一個頂點相鄰的右頂點集合——即 A 的合併選項池。Hall 條件是：對 L 的每個子集 A，|N(A)| >= |A|。定理說，恰當此式成立時，存在飽和左側的匹配。「僅當」方向顯然——若某 A 的鄰居比成員少，這些成員就無法全配到不同伴侶。「當」方向是深刻的部分，可由最大流最小割（或由 Konig 定理）乾淨地得出：若不存在這樣的匹配，最大匹配會漏掉某個左頂點，而追蹤最小割會產出一個違反的集合 A，使 |N(A)| < |A|，與條件矛盾。
Hall 定理是匹配理論的基石，也是極小極大／可行性憑證的優美範例：要嘛存在完整匹配，要嘛存在單一個「不足集」A 證明它不可能，兩者之間別無其他。它支撐起從組合學（相異代表系統、拉丁方）到排程的諸多結果。兩個誠實的提醒。其一，條件須對每個子集 A 成立，而這樣的子集呈指數多——所以 Hall 定理是一種刻畫，而非快速檢驗；你實際上是用流演算法找出或駁回匹配，再由 Hall 解釋緣由。其二，|N(A)| >= |A| 保證你能匹配整個 L，而非整個 R；要同時飽和兩側（完美匹配）還需要 |L| = |R|。
左 {a, b, c}，每個都只與右頂點 {x} 相鄰。取 A = {a, b, c}：N(A) = {x}，故 |N(A)| = 1 < 3 = |A|。Hall 條件失敗，而確實沒有匹配能把三者各配到不同伴侶——它們都想要那唯一的頂點 x。不足集 A 就是不可能性的憑證。
一個鄰居比成員少的子集 A，是不存在飽和左側匹配的見證。
Hall 條件跑遍所有 2^|L| 個子集，故它刻畫了可行性卻本身不是高效檢驗——用流／匹配演算法來判定，再用 Hall 來解釋。且它只保證飽和 L，而非兩側都完美匹配。