Hall 定理证明
Descripition
设一个二分图两部分点为 \((x,y)\)，\(x\le y\)，如果 \(x\) 的任意大小为 \(k\) 的子集连向 \(y\) 中的点集大小不小于 \(k\)，则存在完美匹配。
Proof
必要性：显然。
充分性：\(n=1\) 时显然成立，若 \(x<n\) 时都成立，那么一个子集 \(S\)（大小小于 \(n\)），它对应的点集为 \(N(S)\)，此时有两种情况：
- 如果存在 \(|S|=|N(S)|\)，此时可以直接删去 \(S\) 和 \(N(S)\)，如果剩下有一个集合 \(T\) 不再满足条件，那么 \(T\cup S\) 在初始时就不满足条件，与假设相悖，此时 \(\text{Hall}\) 定理成立。
- 如果所有子集都满足 \(|S|<|N(S)|\)，此时随便找到一个点 \(x\)，删去它和一个它的匹配点，因为只删去一个，所以剩下的所有子集满足 \(|S|\le |N(S)|\)，此时 \(\text{Hall}\) 定理成立。
综上所述，\(\text{Hall}\) 定理成立。