Kőnig 二分图定理

匹配提供覆盖大小的下界：每条互不相交的匹配边都需要一个独立的“守卫”。二分结构则让交替搜索找出恰好这么多守卫，覆盖所有边。

这同时给出最优性证书。若展示一个大小为 $k$ 的匹配和一个大小也为 $k$ 的覆盖，就无需重跑优化算法：匹配不可能更大，覆盖也不可能更小，两者同时最优。

在路径 $P_4$ 上，边为 $12,23,34$，匹配 $\{12,34\}$ 与覆盖 $\{2,3\}$ 大小都为 $2$。若只选中间边 $23$，得到的匹配虽然不能直接再加一条边，却不是最大匹配。这说明证明中的“最大”不能换成“极大”。

在 $K_{2,3}$ 中，左侧只有两个顶点，故匹配大小至多为 $2$；任选两个不同右点与它们配对即可达到上界。整个左侧本身是大小为 $2$ 的覆盖，而任何单点都漏掉另一左点的边。这里最大匹配有多种，但最小覆盖恰是左侧二元集，不能由匹配不唯一推断覆盖也不唯一。

同一交替搜索的匹配与覆盖 ​

取左侧 $L=\{a,b,c,d\}$、右侧 $R=\{1,2,3,4\}$，边为 $a1,a2,b1,c2,d3,d4$。匹配 $M=\{a1,c2,d3\}$ 留下左点 $b$；交替搜索沿 $b\to 1\to a\to 2\to c$ 到达 $Z_L=\{a,b,c\}$、$Z_R=\{1,2\}$，无法到达任何未匹配右点。因此构造给出

逐边核验：$a1,b1$ 由 $1$ 覆盖，$a2,c2$ 由 $2$ 覆盖，$d3,d4$ 由 $d$ 覆盖。$|M|=|C|=3$，所以这份匹配与覆盖同时最优。若补回边 $c3$，原覆盖漏掉这条新边；长增广路可以得到 $\{b1,a2,c3,d4\}$，此时最小覆盖可取整个 $L$，大小为四。输入只改一条边，旧证书也必须重新核验。

三角形的最大匹配大小为 $1$，最小顶点覆盖大小为 $2$，所以二分性不能去掉。反过来，某个图碰巧满足 $\nu =\tau$，也不代表它一定是二分图。

若最大匹配饱和全部左点，搜索没有起始点，$Z_L=Z_R=\varnothing$，于是覆盖就是 $L$。定理比较对象大小，不要求匹配或覆盖唯一；带权版本还需另行规定权重、容量及对应对偶问题。

给出一份匹配 $M$ 与顶点集合 $C$ 后，独立检查器先核对边编号与顶点范围，确认匹配端点互异，再扫描每条输入边，要求至少一端在 $C$；最后比较 $|M|=|C|$。接受就证明双方最优，依据只是任意图都有的匹配下界。二分性用于保证这种同值证书总能产生，不是这条检查逻辑可靠性的必要条件。

显式输入有 $n$ 个顶点、$m$ 条编号边时，证书用 $O(n)$ 个机器字，检查时间为 $O(n+m)$，端点和覆盖标记用 $O(n)$ 空间。产生证书则先支付最大匹配的求解成本，再加一次 $O(n+m)$ 交替搜索。流归约课程公理库经由网络流的二分图匹配Bipartite matching via maximum flow用单位容量流求二分图匹配，并从终态搜索同时提取 Hall 障碍、等值割和最小顶点覆盖。把同一结果译为值三的流与割，并给出完整产生成本。全单位网络中的任意最小割未必直接对应覆盖，那里使用的是终态可达割。

把零一矩阵的行、列分别作为二分图两侧，非零项作为边，匹配就是互不同行也不同列的一组非零项，顶点覆盖就是覆盖所有非零项的一组行与列。定理因此等价于：这种独立非零项的最大个数，等于所需行列的最少条数。

结合Hall 定理公理库Hall 婚配定理Hall's marriage theorem有限二分图存在饱和一侧的匹配，当且仅当每个该侧顶点子集的邻集至少同样大。，左侧能否全被匹配还可用邻集容量刻画。Dilworth 定理公理库Dilworth 定理Dilworth's theorem有限偏序集的最大反链大小等于覆盖全部元素所需的最少链数。的匹配证明则把偏序链分解转为二分图问题。

二分图匹配与覆盖线性规划具有整数最优解，线性规划对偶性提供另一条证明路线。无权等式是这一整数性结构的体现；不能只凭某个图的一次数值相等就断言其整个多面体具有整数性。