形式陈述

Kőnig 二分图定理断言：对每个有限二分图 $G$$G$，最大匹配大小等于最小顶点覆盖大小，

$$ \nu(G)=\tau(G). $$$$\nu (G)=\tau (G).$$

一般图中总有 $\nu(G)\le\tau(G)$$\nu (G)\le \tau (G)$；二分性使该下界可达到。构造性证明从最大匹配 $M$$M$ 出发：从左部未匹配顶点沿“非匹配边向右、匹配边向左”的交替路搜索。若可达左顶点集为 $Z_L$$Z_L$、可达右顶点集为 $Z_R$$Z_R$，则

$$ (L\setminus Z_L)\cup Z_R $$$$(L\setminus Z_L)\cup Z_R$$

是大小 $|M|$$|M|$ 的顶点覆盖。该定理等价于二分图匹配线性规划的整数性，也推出 Hall 定理。

直觉

匹配给出覆盖的不可突破下界；交替路搜索从“无法再增广”中读出一个恰好同样大的覆盖，形成最小—最大证书对。

例子与边界

路径 $P_4$$P_4$ 的最大匹配和最小顶点覆盖大小都为二。三角形不是二分图：最大匹配为一，最小顶点覆盖为二，说明结论不能推广到任意图。构造中必须从某一侧的未匹配顶点出发，并按交替方向搜索；若最大匹配已经饱和左侧，则可达集为空，覆盖就是整个左侧，其大小等于匹配大小。定理比较的是基数，不声称最大匹配与最小覆盖对象唯一。带权二分图顶点覆盖有相应线性规划对偶版本，但公式需要权重。

推论与应用

Kőnig 定理给出二分图最小顶点覆盖算法，并连接任务分配、矩阵非零项覆盖、网络流和线性规划对偶。

参考资料

• Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017，Ch. 2, König theorem and alternating paths。
• Douglas B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001，Ch. 3, bipartite matching and vertex-cover duality。