Hall 定理：对一个二分图 (G=(V_1,V_2,E))，对 (Ssubseteq V_1) 设 (f(S)) 为 (S) 连到 (V_2) 的点集大小，则存在 (V_1) 的完美匹配（即大小等于 (|V_1|) 的匹配）当且仅当对任意 (Ssubseteq V_1) 都有 (|S|leq|f(S)|)。（要求右部的话，交换 (V_1,V_2) 即可）
扩展 Hall 定理：令 (M=maxlimits_{Ssubseteq V_1}{|S|-|f(S)|})，则 (G) 的最大匹配为 (|V_1|-M)。（对左右部作用这个定理都可以得到最大匹配，想不到吧！）
显然扩展 Hall 定理严格比 Hall 定理强。我们来证证扩展 Hall 定理。
- 最大匹配 (leq |V_1|-M) 证明：这个就有点简单了。对 (|S|-|f(S)|) 取到 (M) 的那个 (S) 中显然至少要有 (M) 个不能被匹配到；
- 存在大小为 (|V_1|-M) 的匹配证明：假设不存在。那么显然一定能找到大小为 (M+1) 的非匹配点集 (S)，根据 (M) 的定义，(S) 至少连出去 (1) 个点。这个点如果是非匹配点，那么 (S) 中与它相连的那个点就可以跟它匹配了，这不符合该匹配是最大匹配。于是这个点必须是匹配点并且和 (S) 以外的一个点匹配。我们将这个左部点加入 (S)，可以得到当前的 (S) 至少连出去 (2) 个点，去除先前那个，有另一个。根据上述推导，又可以得到这个是匹配点并且与 (S) 外点匹配，又加入 (S)，如此辗转反复可以进行无限轮。而点集是有限的，矛盾，得证。
得证。
对于一般的二分图，判完美匹配存在性或者求最大匹配当然是网络流跑最好，但是某些以特殊形式给出、有特殊性质的二分图可以用 Hall 定理做。