霍爾婚配定理
数学上，霍爾婚配定理（）是菲利浦·霍爾最先證明的圖論定理，又稱霍爾定理，描述二分图中，能將一側全部頂點牽線匹配到另一側的充要條件。定理另有一個等價的組合敍述，確定一族有限集合在何種充要條件下，可自每個集合各揀選一個元素，而使所選元素兩兩互異。
設 formula_1 為 formula_2 的有限子集組成的有限多重族。
formula_1 的一個是 formula_1 至 formula_2 的單射，且該單射 formula_6 將族中任意集合 formula_7 映至該集合的某元素 formula_8。換言之，formula_6 從 formula_1 中每個集合，選出一個代表元，使得不同的集合由不同元素代表（「單射」之義）。代表系又稱為「截面」或「遍歷」（）。
族 formula_1 滿足霍爾條件，意思是對每個子族 formula_12，有
用文字複述，該條件斷言對於 formula_1 的每個子族，其各集合一共擁有的不同成員數，不小於該子族的集合數。若不滿足該條件，則不存在代表系，因為在某子族 formula_15（設有 formula_16 個集合）中，各集合一共衹有少於 formula_16 個互異元素，如此由鴿巢原理，為 formula_16 個集合所選的 formula_16 個代表元之中，必有兩者相等。霍爾定理說明，前述命題的否命題也成立，即若滿足霍爾條件，則必存在代表系。
霍爾定理：一族有限集有代表系，當且僅當其滿足霍爾條件，即其任意子族皆滿足以上不等式。
證明見。
例一：考慮集族 formula_20，其中
合適的代表系有 formula_22，但並不唯一，例如 formula_23 亦可。 例二：考慮 formula_24，其中
此時，無合適的代表系。子族 formula_26 違反霍爾條件，因為該族有 formula_27 個集合，但該三個集之並為 formula_28，僅得兩個元素。
例三：同樣設 formula_24，但換成
此時，formula_31 與 formula_32 的代表必為 formula_33 或逆序，從而 formula_34 的代表須為 formula_35。所以，合適的代表系有且衹有 formula_36 或 formula_37。
定理命名為「婚配」（），是與以下例子有關。設有兩組人，一組 formula_38 男，一組 formula_38 女。每名女士心目中皆有一份名單（若干男士組成的子集），會接受名單中的男士的求婚，但會拒絕其他人。而該些男士別無所求，願意向任何女士求婚。媒人希望判斷是否存在方案，在尊重諸位女士的意願的前提下，將該兩組人撮合成 formula_38 對夫妻。
以 formula_41 表示第 formula_42 名女士願意接受的男士集合，則霍爾定理講述，存在方案使每位女士與心儀對象結婚，且無重婚，當且僅當對於任意若干位女士組成的集合 formula_43，願意與其中至少一位女士結婚的男士數 formula_44，不小於該集合的女士數 formula_45。
後一個條件為必要，否則該 formula_45 名女士根本無法找到足夠的配偶。較不明顯的是，該條件亦為充分，此即霍爾定理的肯綮。
設 formula_47 為有限二部圖，頂點集分為 formula_2、formula_49 兩部，以符號記為 formula_50。formula_2 完美匹配是圖上若干條邊組成的匹配，其兩兩無公共端點，且 formula_2 的每個頂點各有一條邊在該匹配中。
對於 formula_2 的任意子集 formula_15，設 formula_55 為 formula_15 在 formula_47 中的，即 formula_49 中與 formula_15 至少一點有連邊的全體頂點之集。霍爾定理斷言，存在 formula_2 完美匹配，当且仅当對 formula_2 的每個子集 formula_15，皆有：
換言之，與 formula_15 相鄰的頂點，不少於 formula_15 的頂點。上述不等式稱為霍爾條件。
「formula_66」：假設有匹配 formula_67，覆蓋頂點集 formula_2。欲證霍爾條件對全部 formula_69 成立。記 formula_70 為 formula_15 經 formula_67 匹配到的頂點集，其為 formula_49 的子集。由匹配的定義，必有 formula_74，同時 formula_75，因為 formula_70 的元素皆為 formula_15 的鄰舍。故 formula_78，即 formula_79。
「formula_80」：假設無 formula_2 完美匹配，欲證有某子集 formula_82 違反霍爾條件。設 formula_67 為極大匹配，換言之，若再添加任何一條邊，則不再為匹配。設 formula_84 為 formula_2 中未獲覆蓋的頂點。考慮由 formula_84 出發的全體「交錯路徑」，即圖 formula_47 中的路徑，其首邊不屬 formula_67，次邊屬於 formula_67，第三邊又不屬 formula_67，如此交錯排列。formula_84 藉該些交錯路徑，與 formula_49 中若干頂點相連，該些頂點組成的子集記為 formula_93；又與 formula_2 中若干頂點相連（此處 formula_84 亦視為與自己相連），得子集 formula_15。極長的交錯路徑不能終於 formula_49，否則其首尾皆不屬 formula_67，故為「增廣路徑」：翻轉路徑上所有邊的狀態，將不屬 formula_67 者加入 formula_67，屬 formula_67 者移走，則得到嚴格比 formula_67 多邊的匹配，此為不可能。至此，已證 formula_93 中每個頂點，皆經 formula_67 匹配到 formula_105 中某頂點。反之，formula_105 中任意一個頂點，亦有 formula_93 中某頂點與之匹配，即沿 formula_84 至 formula_109 的交錯路徑，formula_109 的前一頂點。所以，formula_67 給出 formula_105 與 formula_93 之間的一一對應，所以 formula_114。另一方面，將證明 formula_115。設 formula_116 是與某頂點 formula_117 鄰接。若邊 formula_118 在 formula_67 中，則自 formula_84 至 formula_121 的一切交錯路徑中，formula_109 皆在 formula_121 以先，故有 formula_84 至 formula_109 的交錯路徑。否則 formula_118 不屬 formula_67，但已知有 formula_84 至 formula_121 的交錯路徑，末邊屬於 formula_67，故可續以 formula_118，亦得自 formula_84 至 formula_109 的交錯路徑。證畢 formula_115，故 formula_135，違反霍爾條件。
若 formula_2 的子集 formula_15 滿足 formula_138，則定義 formula_15 為。若 formula_15 為霍爾犯，則無匹配能覆蓋 formula_15 的全部頂點。所以，也無匹配覆蓋 formula_2。霍爾定理斷言，二部圖有 formula_2 完美匹配，當且僅當其不含任何霍爾犯。以下算法驗證定理較難的方向：輸入一幅二部圖，算法或輸出一個 formula_2 完美匹配，或輸出一個霍爾犯。
該算法調用以下子程序：輸入匹配 formula_67 及未匹配的某頂點 formula_146，或輸出一條 formula_67 增廣路徑，或輸出一個霍爾犯。該子程序可以深度优先搜索實作。
以下敍述算法的步驟：
每次找到增廣路徑，都會使 formula_67 多一條邊。所以，前述算法的迴圈至多執行 formula_159 次，就會停機。每次尋找增廣路徑需時 formula_160。總時間複雜度與不加權的的福特-富爾克森算法相約。
設 formula_161，其中 formula_41 皆為有限集，不必相異。相應地，構造二部圖 formula_47，一側頂點集 formula_164 對應該 formula_38 個集合，另一側頂點集 formula_49 為該些集合之並。若 formula_41 有元素 formula_168，則在圖中連一條邊 formula_169。如此，族 formula_1 的代表系即是 formula_47 的 formula_2 完美匹配，覆蓋 formula_2 的全部頂點。所以，以集族表述的霍爾問題，容易化成圖論表述的霍爾問題。反之亦然：給定二部圖 formula_50，formula_2 完美匹配相當於族 formula_176 的代表系。
利用的，可得霍爾定理的非構造性證明。
定理有許多「非婚」應用。例如，取一疊啤牌（無鬼牌），洗勻後，派成13磴，每磴4張。由霍爾定理可證，必能從每磴揀選一張牌，使所選13張牌恰好出齊各點數（A、2、3、⋯⋯、Q、K）。更一般地，任意正則二部圖（允許重邊）皆有完美匹配。
較抽象的應用有雙邊陪集遍歷。設 formula_47 為群，formula_178 為其有限指數子群，則霍爾定理適用於證明存在集合 formula_179，既是 formula_178 各左陪集的代表系，又是各右陪集的代表系。
霍爾定理亦用於證明，若 formula_181，則任意 formula_182 皆可擴展成 formula_183 拉丁矩陣，並可重複，直至得到完整的拉丁方陣。
本定理可歸類到組合學的一列強力定理，其彼此關聯。若假設任何一條，則較易證得其他各條，但若要從頭開始，則較難證得任何一條。總括而言，該類定理各自斷言某類組合優化問題具有。該些定理包括：欲要更具體描述各定理的關係，下列各等價關係有簡單證明：
迪爾沃思定理 ⇔ 霍爾定理 ⇔ 克尼格-艾蓋瓦里定理 ⇔ 克尼格定理。
細察菲利浦·霍爾原先的證明，發現可以將結論修改成對（有限集組成的）無窮族 formula_1 仍成立。該證明直接使用佐恩引理。此外，也有較簡短的證明，用到命題邏輯的緊緻性定理：
設 formula_185。對每個 formula_186 和 formula_187，以命題 formula_188 表示「formula_189 選為 formula_41 的代表」。可以列出代表系須滿足的條件如下： 如此，代表系即等價於同時滿足以上各命題的賦值。由有限族的霍爾定理，對 formula_43 的任意有限子集 formula_198，相應的有限子族有代表系，故以上命題中，任意有限條皆可同時滿足。所以，由緊緻性定理，全部命題可同時滿足，即有整個無窮族的代表系。
以上一般情況的證明中，選擇公理（或等價命題如佐恩引理）為必須，因為給定一族無窮多個非空集（無額外條件），欲從每個集合中，選出一個代表（而無須相異），已需要選擇公理。
馬歇爾·霍爾給出下列反例，表明若允許有無窮集，則所組成的無窮族，即使滿足霍爾條件，亦不保證有代表系。
設族 formula_1 由可數多個集合 formula_200 構成。該族滿足霍爾條件，但無法選出代表系。
若妥為敍述，則的確可將霍爾定理推廣至適用於無窮集。給定二部圖，兩側頂點集為 formula_201，若由 formula_202 的子集 formula_203 出發，在圖中找到單射（意思是衹能用二部圖的邊），射向 formula_204 的子集 formula_205，則稱 formula_206，而若更甚者，圖中沒有反向的，由 formula_205 至 formula_203 的單射，則稱 formula_209。前述定義中，若忽略「在圖中」三字，則所得大小的概念等同一般基數的大小比較。無窮集的婚配定理斷言： 圖中有 formula_204 至 formula_202 的單射，當且僅當對每個 formula_212，皆有其鄰域 formula_213。
馬歇爾·霍爾也計算出給定有限族 formula_1 的代表系數目的下界，從而加強婚配定理。其敍述為： 設有一列有限集 formula_215，不必相異，但滿足霍爾條件，又設 formula_216 對 formula_217 成立。則當 formula_218 時，該族有限集至少有 formula_219 個不同的代表系，而當 formula_220 時，至少有 formula_221 個。 此處即使兩個代表系的元素一樣，衹要其次序不同，亦視為不同。例如，若 formula_222，formula_223，則 formula_224 和 formula_225 為兩個不同的代表系。
圖的分數匹配（）是對各邊賦予非負權值，使每個頂點所連各邊的權值和不超逾 formula_35。所謂 formula_2 完美的分數匹配，即是使 formula_2 中的每一頂點處，各邊權之和恰為 formula_35。對於二部圖 formula_230，下列各項等價：假如霍爾條件不成立，則原定理僅斷言不存在完美匹配，但並未說明匹配最大可以多大。欲知此事，需要考慮。對於二部圖 formula_50，formula_47 關於 formula_2 的虧度（）是 formula_248 的最大值，其中 formula_15 可取 formula_2 的任意子集。虧度越大，則圖離霍爾條件越遠。
用霍爾定理可證，若二部圖的虧度為 formula_251，則有大小為 formula_252 的匹配。（考慮在 formula_49 側添加 formula_251 個輔助點，與 formula_2 所有頂點連邊。新圖將滿足霍爾條件。）