Hall’s marriage theorem
定理内容
这个定理是说，对于任意一个二分图$G=\{ X+Y,E\}$，都有：
$\forall W \subset X, |W|\le |N_G(W)| \Longleftrightarrow |M|=|X|$
其中，$N_G(W)$表示$Y$中与$W$中的点相邻的点的集合，$M$表示最大匹配。
证明
（来自wikipedia）：
必要性：如果存在一个$W\subset X$满足$|W|>|N_G(W)|$，那么由于$W$中的每一个点都必须和$N_G(W)$中的点匹配，每个点又至多和一个点匹配，所以一定不存在完备匹配。
充分性：证明其充分性，只需要证明不存在一个张二分图$G(X+Y,E)$，$G$不存在完备匹配并且满足$\forall W\subset X, |W|\le |N_G(W)|$。考虑某个不在最大匹配中的点$u$，找出一条从它出发的交错路，记交错路上在$X$中的集合中的点组成的集合为$W$，记交错路上在$Y$集合的点组成的集合为$Z$。显然交错路是以一个$X$中的点结尾的，否则这就是一条增广路，与$u$不在最大匹配中矛盾。所以，$|W| = |Z|+1$，并且$W$中除了$u$以外的任意一个点，在$Z$中都有它的匹配。并且，$W$中没有点与$Y$中不在最大匹配中的点相邻，因为如果有的话，就可以继续增广，与$u$不在最大匹配中矛盾。所以$Z=N_G(W)$，所以$|W|>|N_G(W)|$。充分性得证。
一个推论
推论内容
二分图的最大匹配$|M|=|X|-\max\{|W|-|N_G(W)|\}$。
推论证明
记$|W|-|N_G(W)|$取到最大值的$W$为$W_0$。
1）证明$|M|\le |X| - \max \{ |W| - |N_G(W)|\} $
$W_0$中至少有$|W_0|-|N_G(W_0)|$个点不能在最大匹配中，得证。
2）证明$|M|\ge |X| - \max \{ |W| - |N_G(W)| \} $
考虑新建$|W_0|-|N_G(W_0)|$个点，这些点都属于$Y$集合，与$X$中的每个点之间都有边相连，记此时的图为$G’$。$G’$显然满足$\forall W\subset X,|W|\le |N_G(W)|$，所以$G’$存在完备匹配。把新加入的点和它们在$X$中对应的点去掉，就得到了$G$的一个大小为$|X|- (|W_0|-|N_G(W_0)|$的匹配。所以$|M|\ge |X| - \max \{ |W| - |N_G(W)| \}$。
3）综上所述，我们有$|M| = |X| - \max \{|W| - |N_G(W)|\}$
练习题
arc076F Exhausted?
agc037D Sort a grid