霍尔婚配定理

设 ${\displaystyle S}$  为 ${\displaystyle X}$  的有限子集^{[注 2]}组成的有限^{[注 3]}多重^{[注 4]}族。

${\displaystyle S}$  的一个代表系（英语：Transversal (combinatorics)）是 ${\displaystyle S}$  至 ${\displaystyle X}$  的单射，且该单射 ${\displaystyle f}$  将族中任意集合 ${\displaystyle s\in S}$  映至该集合的某元素 ${\displaystyle f(s)}$ 。换言之，${\displaystyle f}$  从 ${\displaystyle S}$  中每个集合，选出一个代表元，使得不同的集合由不同元素代表（“单射”之义）。代表系又称为“截面”或“遍历”（transversal）。

族 ${\displaystyle S}$  满足霍尔条件，意思是对每个子族 ${\displaystyle W\subseteq S}$ ，有

${\displaystyle |W|\leq \left|\bigcup _{A\in W}A\right|.}$ 

用文字复述，该条件断言对于 ${\displaystyle S}$  的每个子族，其各集合一共拥有的不同成员数，不小于该子族的集合数。若不满足该条件，则不存在代表系，因为在某子族 ${\displaystyle W}$ （设有 ${\displaystyle k}$  个集合）中，各集合一共衹有少于 ${\displaystyle k}$  个互异元素，如此由鸽巢原理，为 ${\displaystyle k}$  个集合所选的 ${\displaystyle k}$  个代表元之中，必有两者相等。霍尔定理说明，前述命题的否命题也成立，即若满足霍尔条件，则必存在代表系。

霍尔定理：一族有限集有代表系，当且仅当其满足霍尔条件，即其任意子族皆满足以上不等式。

证明见§ 图论表述。

例

例一：考虑集族 ${\displaystyle S=\{A_{1},A_{2},A_{3}\}}$ ，其中

${\displaystyle {\begin{aligned}A_{1}&=\{1,2,3\},\\A_{2}&=\{1,4,5\},\\A_{3}&=\{3,5\}.\end{aligned}}}$ 

合适的代表系有 ${\displaystyle (1,4,5)}$ ，但并不唯一，例如 ${\displaystyle (2,1,3)}$  亦可。

例二：考虑 ${\displaystyle S=\{A_{1},A_{2},A_{3},A_{4}\}}$ ，其中

${\displaystyle {\begin{aligned}A_{1}&=\{2,3,4,5\},\\A_{2}&=\{4,5\},\\A_{3}&=\{5\},\\A_{4}&=\{4\}.\end{aligned}}}$ 

此时，无合适的代表系。子族 ${\displaystyle W=\{A_{2},A_{3},A_{4}\}}$  违反霍尔条件，因为该族有 ${\displaystyle |W|=3}$  个集合，但该三个集之并为 ${\displaystyle A_{2}\cup A_{3}\cup A_{4}=\{4,5\}}$ ，仅得两个元素。

例三：同样设 ${\displaystyle S=\{A_{1},A_{2},A_{3},A_{4}\}}$ ，但换成

${\displaystyle {\begin{aligned}A_{1}&=\{1,2,3\},\\A_{2}&=\{2,4\},\\A_{3}&=\{1,2,4\},\\A_{4}&=\{2,4\}.\end{aligned}}}$ 

此时，${\displaystyle A_{2}}$  与 ${\displaystyle A_{4}}$  的代表必为 ${\displaystyle 2,4}$  或逆序，从而 ${\displaystyle A_{3}}$  的代表须为 ${\displaystyle 1}$ 。所以，合适的代表系有且衹有 ${\displaystyle (3,2,1,4)}$  或 ${\displaystyle (3,4,1,2)}$ 。

命名

定理命名为“婚配”（marriage），是与以下例子有关。设有两组人，一组 ${\displaystyle n}$  男，一组 ${\displaystyle n}$  女。每名女士心目中皆有一份名单（若干男士组成的子集），会接受名单中的男士的求婚，但会拒绝其他人。而该些男士别无所求，愿意向任何女士求婚。媒人希望判断是否存在方案，在尊重诸位女士的意愿的前提下，将该两组人撮合成 ${\displaystyle n}$  对夫妻^{[注 5]}。

以 ${\displaystyle A_{i}}$  表示第 ${\displaystyle i}$  名女士愿意接受的男士集合，则霍尔定理讲述，存在方案使每位女士与心仪对象结婚，且无重婚，当且仅当对于任意若干位女士组成的集合 ${\displaystyle I}$ ，愿意与其中至少一位女士结婚的男士数 ${\displaystyle \left|\bigcup _{i\in I}A_{i}\right|}$ ，不小于该集合的女士数 ${\displaystyle |I|}$ 。

后一个条件为必要，否则该 ${\displaystyle |I|}$  名女士根本无法找到足够的配偶。较不明显的是，该条件亦为充分，此即霍尔定理的肯綮。

设 ${\displaystyle G}$  为有限二部图，顶点集分为 ${\displaystyle X}$ 、${\displaystyle Y}$  两部，以符号记为 ${\displaystyle G=(X\sqcup Y,E)}$ 。${\displaystyle X}$  完美匹配是图上若干条边组成的匹配，其两两无公共端点，且 ${\displaystyle X}$  的每个顶点各有一条边在该匹配中。

对于 ${\displaystyle X}$  的任意子集 ${\displaystyle W}$ ，设 ${\displaystyle N_{G}(W)}$  为 ${\displaystyle W}$  在 ${\displaystyle G}$  中的邻域（英语：Neighbourhood (graph theory)），即 ${\displaystyle Y}$  中与 ${\displaystyle W}$  至少一点有连边的全体顶点之集。霍尔定理断言，存在 ${\displaystyle X}$  完美匹配，当且仅当对 ${\displaystyle X}$  的每个子集 ${\displaystyle W}$ ，皆有：

${\displaystyle |W|\leq |N_{G}(W)|.}$ 

换言之，与 ${\displaystyle W}$  相邻的顶点，不少于 ${\displaystyle W}$  的顶点。上述不等式称为霍尔条件。

证明

“${\displaystyle \Longrightarrow }$ ”：假设有匹配 ${\displaystyle M}$ ，覆盖顶点集 ${\displaystyle X}$ 。欲证霍尔条件对全部 ${\displaystyle W\subseteq X}$  成立。记 ${\displaystyle M(W)}$  为 ${\displaystyle W}$  经 ${\displaystyle M}$  匹配到的顶点集，其为 ${\displaystyle Y}$  的子集。由匹配的定义，必有 ${\displaystyle |M(W)|=|W|}$ ，同时 ${\displaystyle M(W)\subseteq N_{G}(W)}$ ，因为 ${\displaystyle M(W)}$  的元素皆为 ${\displaystyle W}$  的邻舍。故 ${\displaystyle |N_{G}(W)|\geq |M(W)|}$ ，即 ${\displaystyle |N_{G}(W)|\geq |W|}$ 。

“${\displaystyle \Longleftarrow }$ ”：假设无 ${\displaystyle X}$  完美匹配，欲证有某子集 ${\displaystyle W\subseteq X}$  违反霍尔条件。设 ${\displaystyle M}$  为极大匹配，换言之，若再添加任何一条边，则不再为匹配。设 ${\displaystyle u}$  为 ${\displaystyle X}$  中未获覆盖的顶点。考虑由 ${\displaystyle u}$  出发的全体“交错路径”，即图 ${\displaystyle G}$  中的路径，其首边不属 ${\displaystyle M}$ ，次边属于 ${\displaystyle M}$ ，第三边又不属 ${\displaystyle M}$ ，如此交错排列。${\displaystyle u}$  藉该些交错路径，与 ${\displaystyle Y}$  中若干顶点相连，该些顶点组成的子集记为 ${\displaystyle Z}$ ；又与 ${\displaystyle X}$  中若干顶点相连（此处 ${\displaystyle u}$  亦视为与自己相连），得子集 ${\displaystyle W}$ 。极长^{[注 6]}的交错路径不能终于 ${\displaystyle Y}$ ，否则其首尾皆不属 ${\displaystyle M}$ ，故为“增广路径”：翻转路径上所有边的状态，将不属 ${\displaystyle M}$  者加入 ${\displaystyle M}$ ，属 ${\displaystyle M}$  者移走，则得到严格比 ${\displaystyle M}$  多边的匹配，此为不可能。至此，已证 ${\displaystyle Z}$  中每个顶点，皆经 ${\displaystyle M}$  匹配到 ${\displaystyle W\setminus \{u\}}$  中某顶点。反之，${\displaystyle W\setminus \{u\}}$  中任意一个顶点，亦有 ${\displaystyle Z}$  中某顶点与之匹配，即沿 ${\displaystyle u}$  至 ${\displaystyle v}$  的交错路径，${\displaystyle v}$  的前一顶点。所以，${\displaystyle M}$  给出 ${\displaystyle W\setminus \{u\}}$  与 ${\displaystyle Z}$  之间的一一对应，所以 ${\displaystyle |W|=|Z|+1}$ 。另一方面，将证明 ${\displaystyle N_{G}(W)\subseteq Z}$ 。设 ${\displaystyle v\in N_{G}(W)}$  是与某顶点 ${\displaystyle w\in W}$  邻接。若边 ${\displaystyle wv}$  在 ${\displaystyle M}$  中，则自 ${\displaystyle u}$  至 ${\displaystyle w}$  的一切交错路径中，${\displaystyle v}$  皆在 ${\displaystyle w}$  以先，故有 ${\displaystyle u}$  至 ${\displaystyle v}$  的交错路径。否则 ${\displaystyle wv}$  不属 ${\displaystyle M}$ ，但已知有 ${\displaystyle u}$  至 ${\displaystyle w}$  的交错路径，末边属于 ${\displaystyle M}$ ，故可续以 ${\displaystyle wv}$ ，亦得自 ${\displaystyle u}$  至 ${\displaystyle v}$  的交错路径。证毕 ${\displaystyle N_{G}(W)\subseteq Z}$ ，故 ${\displaystyle \left|N_{G}(W)\right|\leq |Z|=|W|-1<|W|}$ ，违反霍尔条件。

算法

若 ${\displaystyle X}$  的子集 ${\displaystyle W}$  满足 ${\displaystyle |N_{G}(W)|<|W|}$ ，则定义 ${\displaystyle W}$  为霍尔犯（英语：Hall violator）。若 ${\displaystyle W}$  为霍尔犯，则无匹配能覆盖 ${\displaystyle W}$  的全部顶点。所以，也无匹配覆盖 ${\displaystyle X}$ 。霍尔定理断言，二部图有 ${\displaystyle X}$  完美匹配，当且仅当其不含任何霍尔犯。以下算法验证定理较难的方向：输入一幅二部图，算法或输出一个 ${\displaystyle X}$  完美匹配，或输出一个霍尔犯。

该算法调用以下子程序：输入匹配 ${\displaystyle M}$  及未匹配的某顶点 ${\displaystyle x_{0}\in X}$ ，或输出一条 ${\displaystyle M}$  增广路径，或输出一个霍尔犯。该子程序可以深度优先搜索实作。

以下叙述算法的步骤：

1. 初始时，设 ${\displaystyle M}$  为空集，未选定任何边。（其后会加边入 ${\displaystyle M}$ 。）
2. 检查：${\displaystyle M}$  确为 ${\displaystyle G}$  的匹配。
3. 若 ${\displaystyle M}$  已覆盖 ${\displaystyle X}$ ，则为所求的 ${\displaystyle X}$  完美匹配，输出并结束程序。
4. 否则，找到未匹配的顶点 ${\displaystyle x_{0}\in X\setminus V(M)}$ 。
5. 调用寻找增广路径的子程序，视乎情况：
   1. 若找到霍尔犯，则输出并结束。
   2. 若找到 ${\displaystyle M}$  增广路径，则将该路径上各边的状态翻转，使 ${\displaystyle M}$  的边数增加一。返回第2步。

每次找到增广路径，都会使 ${\displaystyle M}$  多一条边。所以，前述算法的循环至多执行 ${\displaystyle |X|}$  次，就会停机。每次寻找增广路径需时 ${\displaystyle {\mathcal {O}}(|E|)}$ 。总时间复杂度与不加权的最大匹配问题（英语：maximum cardinality matching）的福特-富尔克森算法相约。

两种表述等价

设 ${\displaystyle S=(A_{1},A_{2},\ldots ,A_{n})}$ ，其中 ${\displaystyle A_{i}}$  皆为有限集，不必相异。相应地，构造二部图 ${\displaystyle G}$ ，一侧顶点集 ${\displaystyle X=\{v_{1},\ldots ,v_{n}\}}$  对应该 ${\displaystyle n}$  个集合，另一侧顶点集 ${\displaystyle Y}$  为该些集合之并。若 ${\displaystyle A_{i}}$  有元素 ${\displaystyle y\in Y}$ ，则在图中连一条边 ${\displaystyle v_{i}y}$ 。如此，族 ${\displaystyle S}$  的代表系即是 ${\displaystyle G}$  的 ${\displaystyle X}$  完美匹配，覆盖 ${\displaystyle X}$  的全部顶点。所以，以集族表述的霍尔问题，容易化成图论表述的霍尔问题。反之亦然：给定二部图 ${\displaystyle G=(X\sqcup Y,E)}$ ，${\displaystyle X}$  完美匹配相当于邻域（英语：Neighbourhood (graph theory)）族 ${\displaystyle \{\Gamma (x):x\in X\}}$  的代表系。

其他证明

利用拓扑组合学（英语：Topological combinatorics）的斯佩纳引理（英语：Sperner's lemma），可得霍尔定理的非构造性证明。^{[5]:Thm.4.1,4.2}

定理有许多“非婚”应用。例如，取一叠啤牌（无鬼牌），洗匀后，派成13磴，每磴4张。由霍尔定理可证，必能从每磴拣选一张牌，使所选13张牌恰好出齐各点数（A、2、3、⋯⋯、Q、K）。更一般地，任意正则二部图（允许重边）皆有完美匹配。^[6]:2

较抽象的应用有双边陪集遍历。设 ${\displaystyle G}$  为群，${\displaystyle H}$  为其有限指数子群，则霍尔定理适用于证明存在集合 ${\displaystyle T}$ ，既是 ${\displaystyle H}$  各左陪集的代表系，又是各右陪集的代表系。^[7]

霍尔定理亦用于证明，若 ${\displaystyle r<n}$ ，则任意 ${\displaystyle r\times n}$  拉丁矩阵（英语：Latin rectangle）皆可扩展成 ${\displaystyle (r+1)\times n}$  拉丁矩阵，并可重复，直至得到完整的拉丁方阵。^[8]

本定理可归类到组合学的一列强力定理，其彼此关联。若假设任何一条，则较易证得其他各条，但若要从头开始，则较难证得任何一条。总括而言，该类定理各自断言某类组合优化问题具有强对偶性（英语：Strong duality）。该些定理包括：

• 克尼格定理（英语：Kőnig's theorem (graph theory)）：二部图的最大匹配，与最小顶点覆盖（英语：Vertex cover）等大。
  • 克尼格-艾盖瓦里定理（英语：König–Egerváry theorem）（1931年），得名自克尼格·代奈什（英语：Dénes Kőnig）、艾盖瓦里·耶内（英语：Jenő Egerváry）两位匈牙利数学家，是克尼格定理的加权推广。^{[注 7]}
• 门格尔定理（1927年）：边最小割的大小，等于任意在所有顶点对之间可以找到的无公共边的路径的最大数量。结论换成顶点最小割与无公共（中间）顶点的路径仍成立。
• 最大流最小割定理（福特-富尔克森算法）：任意网络流中，最大流的值等于最小割。
• 伯克霍夫-冯纽曼定理（英语：Birkhoff–Von Neumann theorem）（1946年）：一个方阵为双随机（英语：Doubly stochastic matrix）^{[注 8]}，当且仅当其为置换方阵的凸组合。
• 迪尔沃思定理（英语：Dilworth's theorem）：覆盖某偏序集所需的不交链数，与该集的最大反链等大。

欲要更具体^[9][10]描述各定理的关系，下列各等价关系有简单证明：

迪尔沃思定理 ⇔ 霍尔定理 ⇔ 克尼格-艾盖瓦里定理 ⇔ 克尼格定理。

无穷族

马歇尔·霍尔（英语：Marshall Hall (mathematician)）细察菲利浦·霍尔^{[注 9]}原先的证明，发现可以将结论修改成对（有限集组成的）无穷族 ${\displaystyle S}$  仍成立。^[11]该证明直接使用佐恩引理。此外，也有较简短的证明，用到命题逻辑的紧致性定理：^[12]

设 ${\displaystyle S=\{A_{i}:i\in I\}}$ 。对每个 ${\displaystyle i\in I}$  和 ${\displaystyle a\in A_{i}}$ ，以命题 ${\displaystyle p_{a,i}}$  表示“${\displaystyle a}$  选为 ${\displaystyle A_{i}}$  的代表”。可以列出代表系须满足的条件如下：

• 对应每个 ${\displaystyle i\in I}$ ，各有一条命题断言恰有一个 ${\displaystyle a\in A_{i}}$  使 ${\displaystyle p_{a,i}}$  为真^{[注 10]}；
• 对应每对互异的 ${\displaystyle i,j\in I}$  和 ${\displaystyle a\in A_{i}\cap A_{j}}$ ，各有一条命题为 ${\displaystyle \neg (p_{a,i}\wedge p_{a,j})}$ 。

如此，代表系即等价于同时满足以上各命题的赋值。由有限族的霍尔定理，对 ${\displaystyle I}$  的任意有限子集 ${\displaystyle J}$ ，相应的有限子族有代表系，故以上命题中，任意有限条皆可同时满足。所以，由紧致性定理，全部命题可同时满足，即有整个无穷族的代表系。

以上一般情况的证明中，选择公理（或等价命题如佐恩引理）为必须，因为给定一族无穷多个非空集（无额外条件），欲从每个集合中，选出一个代表（而无须相异），已需要选择公理。

无穷集

马歇尔·霍尔给出下列反例，表明若允许有无穷集，则所组成的无穷族，即使满足霍尔条件，亦不保证有代表系。

设族 ${\displaystyle S}$  由可数多个集合 ${\displaystyle A_{0}=\{1,2,3,\ldots \},\ A_{1}=\{1\},\ A_{2}=\{2\},\ \ldots ,\ A_{i}=\{i\},\ \ldots }$  构成。该族满足霍尔条件，但无法选出代表系。^[11]

若妥为叙述，则的确可将霍尔定理推广至适用于无穷集。给定二部图，两侧顶点集为 ${\displaystyle A,B}$ ，若由 ${\displaystyle B}$  的子集 ${\displaystyle C}$  出发，在图中找到单射（意思是衹能用二部图的边），射向 ${\displaystyle A}$  的子集 ${\displaystyle D}$ ，则称 ${\displaystyle C\leq D}$ ，而若更甚者，图中没有反向的，由 ${\displaystyle D}$  至 ${\displaystyle C}$  的单射，则称 ${\displaystyle C<D}$ 。前述定义中，若忽略“在图中”三字，则所得大小的概念等同一般基数的大小比较。无穷集的婚配定理断言：^[13]

图中有 ${\displaystyle A}$  至 ${\displaystyle B}$  的单射，当且仅当对每个 ${\displaystyle D\subseteq A}$ ，皆有其邻域 ${\displaystyle N(D)\nless D}$ 。

代表系的数目

马歇尔·霍尔也计算出给定有限族 ${\displaystyle S}$  的代表系数目的下界，从而加强婚配定理。其叙述为：^[14]

设有一列有限集 ${\displaystyle (A_{1},A_{2},\ldots ,A_{n})}$ ，不必相异，但满足霍尔条件，又设 ${\displaystyle |A_{i}|\geq r}$  对 ${\displaystyle i=1,\ldots ,n}$  成立。则当 ${\displaystyle r\leq n}$  时，该族有限集至少有 ${\displaystyle r!}$  个不同的代表系，而当 ${\displaystyle r>n}$  时，至少有 ${\displaystyle r(r-1)\cdots (r-n+1)}$  个。

此处即使两个代表系的元素一样，衹要其次序不同，亦视为不同。例如，若 ${\displaystyle A_{1}=\{1,2,3\}}$ ，${\displaystyle A_{2}=\{1,2,5\}}$ ，则 ${\displaystyle (1,2)}$  和 ${\displaystyle (2,1)}$  为两个不同的代表系。

分数匹配

图的分数匹配（fractional matching）是对各边赋予非负权值，使每个顶点所连各边的权值和不超逾 ${\displaystyle 1}$ 。所谓 ${\displaystyle X}$  完美的分数匹配，即是使 ${\displaystyle X}$  中的每一顶点处，各边权之和恰为 ${\displaystyle 1}$ 。对于二部图 ${\displaystyle G=(X\sqcup Y,E)}$ ，下列各项等价：^[15]

• ${\displaystyle G}$  有 ${\displaystyle X}$  完美匹配。
• ${\displaystyle G}$  有 ${\displaystyle X}$  完美分数匹配。（此为前项的直接推论。给定一个 ${\displaystyle X}$  完美匹配，将该匹配所选的边赋权 ${\displaystyle 1}$ ，其余边赋 ${\displaystyle 0}$ ，则得到 ${\displaystyle X}$  完美分数匹配。）
• ${\displaystyle G}$  满足霍尔条件。（若有前项的分数匹配，则对于 ${\displaystyle X}$  的每个子集 ${\displaystyle W}$ ，其所连各边之和恰为 ${\displaystyle |W|}$ ，故至少要与对面的 ${\displaystyle |W|}$  个顶点相连，因为对面每个顶点所连的边值和不超过 ${\displaystyle 1}$ 。）

亏缺

假如霍尔条件不成立，则原定理仅断言不存在完美匹配，但并未说明匹配最大可以多大。欲知此事，需要考虑图的亏度（英语：Deficiency (graph theory)）。对于二部图 ${\displaystyle G=(X\sqcup Y,E)}$ ，${\displaystyle G}$  关于 ${\displaystyle X}$  的亏度（deficiency）是 ${\displaystyle |W|-|N_{G}(W)|}$  的最大值，其中 ${\displaystyle W}$  可取 ${\displaystyle X}$  的任意子集。亏度越大，则图离霍尔条件越远。

用霍尔定理可证，若二部图的亏度为 ${\displaystyle d}$ ，则有大小为 ${\displaystyle |X|-d}$  的匹配。（考虑在 ${\displaystyle Y}$  侧添加 ${\displaystyle d}$  个辅助点，与 ${\displaystyle X}$  所有顶点连边。新图将满足霍尔条件。）

非二部图

• 若推广至一般的图（不必为二部图），则其上有完美匹配的充要条件，由塔特定理描述。
• 若推广至各类二部超图（英语：bipartite hypergraph）（二部图的超图版本），则相应有各种霍尔式定理（英语：Hall-type theorems for hypergraphs）。

• Brualdi, Richard A., Introductory Combinatorics [入门组合学], Upper Saddle River, NJ: Prentice-Hall/Pearson, 2010, ISBN 978-0-13-602040-0 （英语） 
• Cameron, Peter J., Combinatorics: Topics, Techniques, Algorithms [组合学：问题、技巧、算法], Cambridge: Cambridge University Press, 1994, ISBN 978-0-521-45761-3 （英语） 
• Dongchen, Jiang; Nipkow, Tobias, Hall's Marriage Theorem [霍尔婚配定理], The Archive of Formal Proofs, 2010 [2021-12-15], ISSN 2150-914X, （原始内容存档于2016-03-19） （英语）. 经电脑验证的证明。 
• Hall, Jr., Marshall, Combinatorial Theory [组合理论] 2nd, New York: John Wiley & Sons, 1986, ISBN 978-0-471-09138-7 （英语） 
• Hall, Philip, On Representatives of Subsets [论子集的代表元], J. London Math. Soc., 1935, 10 (1): 26–30, doi:10.1112/jlms/s1-10.37.26 （英语） 
• Halmos, Paul R.; Vaughan, Herbert E., The marriage problem [婚配问题], American Journal of Mathematics（英语：American Journal of Mathematics）, 1950, 72 (1): 214–215, JSTOR 2372148, MR 0033330, doi:10.2307/2372148 （英语） 
• Reichmeider, P.F., The Equivalence of Some Combinatorial Matching Theorems [若干组合匹配问题之等价], Polygonal Publishing House, 1984, ISBN 978-0-936428-09-3 （英语） 
• Roberts, Fred S.; Tesman, Barry, Applied Combinatorics [应用组合学] 2nd, Boca Raton: CRC Press, 2009, ISBN 978-1-4200-9982-9 （英语） 
• van Lint, J. H.; Wilson, R.M., A Course in Combinatorics [组合学教程], Cambridge: Cambridge University Press, 1992, ISBN 978-0-521-42260-4 （英语） 

• Cut-the-knot站，Marriage Theorem （页面存档备份，存于互联网档案馆）
• Cut-the-knot站，Marriage Theorem and Algorithm （页面存档备份，存于互联网档案馆）
• Lucky的笔记Hall's marriage theorem explained intuitively （页面存档备份，存于互联网档案馆）.

本条目含有来自PlanetMath《proof of Hall's marriage theorem》的内容，版权遵守知识共享协议：署名-相同方式共享协议。