在网上学习了 Hall 定理后决定写这么个东西。
如有雷同或涉及侵权，请联系博主。
定理内容
对于一个二分图，假设其左边节点个数小于等于右边节点个数，并设左边节点个数为 \(X\)，右边为 \(Y\)。
若从左边选出任意 \(k\) 个节点，右边都有至少 \(k\) 个节点与之相连，那么该二分图的最大匹配个数恰好为 \(X\)。我们称满足这个条件的匹配为完美匹配。
为了方便，在下文中默认左边的节点数小于等于右边的节点数。
证明
考虑从必要和充分两方面证明这个定理。
1. 必要性
如果一个二分图有完美匹配，且其不满足 Hall 定理。
那么对于左边某 \(k\) 个节点，右边与之相连的点数小于 \(k\)。
而根据假设，左边这 \(k\) 个节点都匹配了右边 \(k\) 个不同的节点，那么右边与之相连的点数至少为 \(k\)。
前后两者是矛盾的，所以该假设不成立，故必要性得证。
2. 充分性
如果一个二分图满足 Hall 定理，且其没有完美匹配。
考虑分两个部分来证明它。
Part1. 若左边每个点的度数都大于等于 \(2\)。
我们在左边可以找到一个没有匹配的点 \(l_1\)。它一定会连接到一个右边的节点 \(r_1\)。
如果 \(r_1\) 没有被匹配，那么就找到了一条增广路，与假设矛盾。
否则 \(r_1\) 会匹配到一个左边的节点 \(l_2\)。那么 \(l_2\) 一定会连接到另一个右边的节点 \(r_2\)。
如果 \(r_2\) 没有被匹配，那么就找到了一条增广路，与假设矛盾。
否则……
这样会一直循环下去，而点数有限，那么必然终止，所以整体与假设矛盾。
Part2. 若左边有点的度数等于 \(1\)
有点的度数为 \(1\) 就可能出现一个问题，就是上述证明的 \(l_2\) 若度数为 \(1\)，则不会连接到另一个右边的节点 \(r_2\)。
但其实这样也是可以证明的。假设 \(l_1\) 的度数为 \(1\)，那么若 \(l_2\) 的度数也为 \(1\)，就会因为它们连接着同一个点 \(r_1\) 而不满足 Hall 定理矛盾（如果左边选择这两个点，右边只有一个点与之相连）
假设 \(l_1\) 的度数大于等于 \(2\)，而 \(l_2\) 的度数为 \(1\)。那么我们可以把这条增广路反向，这样 \(l_2\) 就变成了 \(l_1\)，再用上面的证明即可。
引申
定义二分图的 K-完美匹配 为二分图有 \(K\) 个完全不相交的完美匹配。
现在考虑该图要满足什么条件才有 K-完美匹配。
这个题是一个经典问题，有一个很经典的网络流做法，博主根据这个做法以及一些分析归纳出了下列定理：（可能是个经典定理，但是博主找不到）
对于一个二分图，如果可以通过删边的操作，使得左边的每个点的度数都为 \(K\)，且右边的每个点的度数都小于等于 \(K\)，那么一定存在 K-完美匹配。
证明
还是从必要和充分两方面证明这个引理。
1. 充分性
考虑用归纳法证明。
1. 先证明 \(K=1\) 成立。
从左边任选一个点，然后找到它相连的点，匹配。
根据前提条件，这条边是这两个点连出的唯一一条边。
这样这个问题就变成了一个条件不变规模更小的问题。
一直这么下去就可以得到一个完美匹配。
2. 假设证明了 \(K\leq x-1\) 成立，再证明 \(K=x\) 成立。
首先这个图满足 Hall 定理。因为对于左边任意 \(k\) 个点，其有的边的数目是 \(k\times x\) 条，而右边的点的度数的上限是 \(x\)，那么右边至少会有 \(k\) 个点与其相连。
把左边所有点和右边所有的度数恰好为 \(x\) 的点及它们之间的边拿出来构成一个新图，此时的这张图是右边的点数小于等于左边的点数的，那么对于右边任意 \(k\) 个点，其有的边的数目是 \(k\times x\) 条，而左边的点的度数上限是 \(x\)，那么至少左边会有 \(k\) 个点与其相连。
这样的话对于这个新图，就存在一个完美匹配。构造出这个完美匹配后，回到原图，保留新图的匹配，再用匈牙利算法形成一个原图的完美匹配。然后把这个完美匹配删掉，剩下的图恰好满足 \(K=x-1\) 的性质，而通过归纳，\(K=x-1\) 已经被证明，故充分性得证。
2. 必要性
若左边存在一个点的度数小于 \(K\)，那么显然不存在一个 K-完美匹配。不然一定存在一种删边方式使得左边的度数等于 \(K\)。
如果删边之后左边存在一个点的度数大于 \(K\)，那么 K-完美匹配 后一定会剩下一些边，那么把这些便删掉也不影响判断。
那么现在可能使得该定理必要性不存在的就只有：左边的所有点的度数为 \(K\)，且右边存在一个点的度数大于 \(K\)，且该二分图存在 K-完美匹配。
但是你会发现上述情况是不可能存在的，因为在删除 K-完美匹配 的边后，左边的点的度数就都变成了 \(0\)，而右边此时会存在至少一个点的度数大于 \(0\)（因为每一个匹配最多让一个点的度数减一），这是矛盾的。
故必要性得证。
这就能解释对于二分图的 K-完美匹配 的判定，为何可以用【 \(S\) 向左边的点连流量为 \(K\) 的边，在每个二分图上的边中左边的点向右边的点连流量为 \(1\) 的边，右边的点向 \(T\) 连流量为 \(K\) 的边，看网络流的结果中左边的点是否都满流】来判断了。