设二分图 $G=\lang V_1,V_2,E\rang,|V_1|\le|V_2|$，则 $G$ 中存在 $V_1$ 到 $V_2$ 的完美匹配当且仅当对于任意的 $S\subseteq V_1$，均有 $|S|\le|N(S)|$，其中 $N(S)=\Cup_{v_i\in S}N(V_i)$，是 $S$ 的邻域。

必要性显然，我们来证明充分性，对 $|V_1|$（记为 $n$）进行归纳：

首先当 $n=1$ 时显然成立。

我们假设我们已经证明了 $n<k$ 时成立，现在考虑 $n=k$ 的情况。

• 如果存在 $S \subset V_1,|S|<n$，满足 $|S|=|N(S)|$，则 $S$ 本身存完美匹配。

发现删去 $S$ 之后并不影响Hall定理条件是否成立，于是变成了原问题的子问题，

根据归纳假设，如果存在 $|S|=|N(S)|$，那么Hall定理成立。

• 如果 $V_1$ 所有子集的 $|N(S)|$ 均大于 $|S|$，那么我们找到一个点 $u$ 并找到 $(u,v)\in E$，

删去 $u\in V_1,v\in V_2,(u,*),(*,v)\in E$。

这时剩下的二分图的每一个子集都依旧满足 $|N(S)|\ge |S|$，变成了原问题的子问题，

根据归纳假设，Hall定理在此情况下也成立。

综上，Hall定理的充分性成立。

补充Hall定理的一个推论：

二分图最大匹配大小（定义沿用Hall定理部分）等于：

$|V_1|-\max\{|S|-|N(S)|\}(S\subseteq V_1)$。