形式陈述

设 $G=(L\dot\cup R,E)$$G=(L\dot{\cup }R,E)$ 为有限二分图。存在一个饱和 $L$$L$ 中每个顶点的匹配，当且仅当对所有子集 $S\subseteq L$$S\subseteq L$，

$$ |N(S)|\ge|S|, $$$$|N(S)|\ge |S|,$$

其中

$$ N(S)=\{r\in R:\exists \ell\in S, \ \ell r\in E\}. $$$$N(S)=\{r\in R:\mathrm{\exists }\ell \in S,\ell r\in E\}.$$

必要性来自匹配把 $S$$S$ 的不同顶点送到 $N(S)$$N(S)$ 中不同顶点；充分性可由归纳、增广路或最大流最小割证明。

直觉

任意一群左侧对象想各自得到不同伙伴，它们共同可选择的右侧对象至少要和人数一样多。Hall 条件不仅检查单个顶点，还检查所有可能发生竞争的群体。

例子与边界

若三个学生的可选导师总共只有两位，则取这三个学生为 $S$$S$ 即违反条件。只检查每个左顶点度数至少 $1$$1$ 不足够，因为多人可能只有同一个邻居。定理保证饱和指定的 $L$$L$ 侧；只有当 $|L|=|R|$$|L|=|R|$ 时，这样的匹配才同时完美饱和两侧。

推论与应用

Hall 定理刻画二分图完全代表系、任务分配与组合设计中的可行性。它的“缺口”推广导出最大匹配大小公式，并与 König 定理、网络流和拟阵横截结构相连。

参考资料

• Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017，§2.1。
• Douglas B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001，§3.1。