Hall定理
图论中一个比较有趣的定理。
前置知识
二分图的完美匹配：即最大匹配数=$\min(|X|,|Y|)$
定理
若一个二分图 $G={ X+Y,E }(|X|\leq |Y|)$ 存在完美匹配，则任取一个 $X$ 中的子集 $W$，都会有 $|W|\leq |N_g(W)|$。
证明
必要性
若该二分图存在完美匹配，且不满足上述条件：
则必然存在一个 $X$ 中的子集 $W$，使得 $W> N_g(W)$。那么 $W$ 中的点就无法全部匹配了。
充分性
若该二分图满足上述条件，且不存在完美匹配：
先进行最大匹配。
然后选择 $X$ 中一个未匹配的点 $x_1$，
由该条件可得，必然存在至少一个点 $y_1$ 与 $x_1$有连边。
又因为这是在最大匹配中，$y_1$ 必须另外一个在 $X$ 中的点 $x_2$ 配对（否则就不是最大匹配了）。
又由该条件得到：${ x_1,x_2 }$ 必然存在至少两个点 ${ y_1,y_2}$ 与其相连，即必然存在至少一个点 $y_2$ 与 $x_2$有连边。
又因为这是在最大匹配中，$y_2 $ 必须另外一个在 $X$ 中的点 $x_3$ 配对（否则就不是最大匹配了）。
…
这样下来就找到了一条增广路，与最大匹配矛盾。
仅有这个定理还不够，因为没理由直接枚举全部 $X$ 的子集吧。
因此——
一些结论
结论1
若 $X$ 中每个点连的边都是 $|Y|$ 上连续的一段，设 $[ l,r ]$ 为 $|Y|$ 上一段连续的点的集合，$f([l,r])$ 表示只与 $[l,r]$ 中的点连边的 $X$ 点的集合。那么：
$$\forall 1\leq l\leq r\leq |Y|,|f([l,r])|\leq |[l,r]|\Leftrightarrow \forall W\subseteq X,|W|\leq |N_g(W)|$$
证明挺显然的。
结论2
一个二分图的最大匹配数 = $|X|-\max(|W|-|N_g(W)|)$
不怎么会证。。。