Hall 定理
描述
一个二分图存在完美匹配（每个左部点都匹配了一个右部点）当且仅当，对于任意左部点构成的集合 \(W\)，它的邻域 \(N_G(W)\) 总是比它本身大。
必要性显然。
充分性证明：反证法。找到一个未匹配的点，走增广路即可。
推论：二分图的最大匹配为 \(|X|-(|W|-|N_G(W)|)\) 的最大值，\(X\) 为左部。
在右部加 \(\max(|W|-|N_G(W)|)\) 个连向所有左部点的点，转化为 Hall 定理。
应用
对于一般二分图，用这个定理的复杂度显然难以接受。这个定理一般用于一些特殊二分图的最大匹配计算。