Hall 婚配定理

每位需求者有候选并不够，多人可能竞争同一小批资源。Hall 条件检查所有人群的联合候选容量：任何一组都不能出现人数多于候选数的缺口。

证明进一步把失败变成证据。若最大匹配仍留下一个需求者，交替搜索就找出具体的短缺集合 $S$，而不是只说“尝试了很多分配都失败”。有限二分图中，所有这种容量缺口都消失，就足以保证完整分配。

取 $L=\{a,b,c\}$，且 $N(a)=N(b)=\{1,2\}$、$N(c)=\{2,3\}$。三个单点的邻集大小都是 $2$；二点集合 $\{a,b\}$ 的邻集大小为 $2$，另两个二点集合的邻集大小为 $3$；全体的邻集大小为 $3$。连同空集，所有八个子集均满足条件。匹配 $a1,b2,c3$ 给出直接证书。

若把 $N(c)$ 也改成 $\{1,2\}$，每个人仍有两个候选，但 $S=L$ 满足 $|N(S)|=2<3$，不可能全部匹配。总候选数足够也未必充分：即使右侧保留没人能选的顶点 $3$，也不会改变这个障碍。

总量足够却无法全部分配 ​

与流归约公理库经由网络流的二分图匹配Bipartite matching via maximum flow用单位容量流求二分图匹配，并从终态搜索同时提取 Hall 障碍、等值割和最小顶点覆盖。共用四对四输入：左侧为 $a,b,c,d$，右侧为 $1,2,3,4$，边为 $a1,a2,b1,c2,c3,d3,d4$。匹配 $b1,a2,c3,d4$ 饱和左侧，因而同时证明所有左子集满足 Hall 条件，无须枚举十六个子集。

只删去 $c3$，仍有 $N(L)=\{1,2,3,4\}$，也没有孤立点，但 $A=\{a,b,c\}$ 的完整邻集仅为 $B=\{1,2\}$。从匹配 $M_0=\{a1,c2,d3\}$ 的未匹配左点 $b$ 出发，搜索顺序为 $b,1,a,2,c$，恰好找出这个障碍。$A$ 中至多匹配两点，加上 $d$ 也至多三点，而 $M_0$ 已达到三点。右点 $4$ 空闲并不能修补候选关系缺失造成的短缺。

若在未删边的图中提交同一个否定证书，扫描全部邻边会发现 $c3$，得到 $N(A)=\{1,2,3\}$；缺额消失，检查器应拒绝。这给出了一个可复算的正例、反例及错误证书的识别过程。

只有当 $|L|=|R|$ 时，饱和 $L$ 的匹配才同时饱和两侧，成为完美匹配。定理也不涉及双方偏好顺序，因此“婚配”这个名称不能与稳定婚姻问题混淆。有限性是本页范围；无限系统需要额外假设与相应版本。

给定集合族 $(A_i{)}_{i\in I}$，其中索引集 $I$ 有限，且每个成员 $A_i$ 也是有限集，把左侧设为索引 $i$、右侧设为所有元素，连边条件为 $x\in A_i$，便得到互异代表系判定：每组集合的并集大小至少等于该组集合个数。索引不同但内容相同的集合仍需占据不同左顶点。

对于 $d$-正则二分图且 $d>0$，从 $S\subseteq L$ 发出的边有 $d|S|$ 条，而邻集最多接收 $d|N(S)|$ 条，所以 Hall 条件成立；两侧大小也由总边数相等推出相同，因此存在完美匹配。

最大缺额等于无法匹配的左点数 ​

令 $p=|L|$、$k=\nu (G)$。对任意 $S\subseteq L$，匹配至多把其中 $|N(S)|$ 个点送到不同邻居，所以至少留下 $|S|-|N(S)|$ 个左点；由此每个子集的缺额都不超过 $p-k$。

取最大匹配，从全部未匹配左点组成的集合 $Q$ 出发作交替搜索，记可达两侧为 $A,B$。与上面单根证明相同，$B=N(A)$，且 $B$ 中每个点已匹配。匹配边在 $B$ 与 $A\setminus Q$ 之间给出双射，因此 $|A|-|B|=|Q|=p-k$，达到此前上界。于是

空集保证最大缺额非负；若已饱和左侧，搜索根为空，取 $A=\varnothing$ 即达到缺额零。公式的指数多个候选集不要求算法枚举它们：找到最大匹配后，一次交替搜索便产生达到最大缺额的集合。

在有编号边表和邻接表下，搜索与障碍检查都只需 $O(n+m)$ 时间，包含孤立点；否定证书只须给出 $A$，检查器自行扫描得到完整邻集并比较基数。若另给上界集合 $B$，检查 $N(A)\subseteq B$ 及 $|B|<|A|$ 也足够，但声称二者相等还须排除多余点。

任务分配、有限代表系与拉丁方构造常使用这种容量判据。Kőnig 定理公理库Kőnig 二分图定理Kőnig's theorem for bipartite graphs二分图中最大匹配大小等于最小顶点覆盖大小。则把最大匹配大小转成最小顶点覆盖大小，提供另一种最优性证书；算法无需穷举所有 $S$，增广路搜索就能构造匹配或给出违例集合。