咕了INF天的基础图论知识。
“衡量一个选手是什么层级的标准是他不会的东西是什么层次的，而不是他会的最难的东西是什么层次。”
——GJS

定义两个二分图的集合为x,y。
为方便，令|x|<=|y|(x的大小比y小)。
完全匹配：指最大匹配数为min(|x|,|y|) 也就是x或y集合其中一个集合所有点都被匹配了。
设二分图中点数较x,且大小为n。
若二分图G存在完美匹配，则取任意正整数1<=k<=n，均满足我从X集合选出k个不同的点，那么它们连向的y集合的点个数不小于k。

必要性

假如一个二分图G存在完美匹配，且不满足Hall定理。
那么对于某k个点，它们连向的都不足k个点，不可能有完美匹配。

充分性

假如一个二分图G不存在完美匹配，且满足Hall定理。
x中至少有一个点连着不在最大匹配的边，从那里开始一直走下去，总能找到一条增广路，说明该匹配不是最大匹配。

推论1

若x中的点至少关联t条边，y中的点至多关联t条边，则存在完美匹配。(t>0)
证明：x中任意k个点都至少与y中的k个不同的点相邻（因为边数限制），可以类似Hall定理证明出来。

推论2

设一个点集S连向的点的数量为F(S)。
则二分图的最大匹配数为∣x∣−max⁡S∈x(∣S∣−F(S))|x|-\max _ {S \in x} (|S|-F(S))
证明：上式显然是答案上界，答案不够的话考虑在最大匹配中选出不在最大匹配的max⁡S∈x(∣S∣−F(S))+1\max _ {S \in x} (|S|-F(S))+1个点开始增广，也一定能够找到增广路。