Kőnig 二分图定理

任意顶点覆盖都必须碰到匹配中的每条互不相邻边，所以覆盖大小至少是匹配大小。二分结构保证这个显然下界总能达到：从未匹配左点出发沿交替路搜索，可把“可达左点的补集 + 可达右点”组成同样大小的覆盖。一般图中的奇圈会破坏这种精确配平。

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

在完全二分图 $K_{2,3}$ 中，匹配至多覆盖左侧两个顶点，所以最大匹配大小为 $2$；左侧整个二元集合本身就是大小为 $2$ 的顶点覆盖。任何单点都遗漏另一左点发出的边，因此最小覆盖也恰为 $2$。这给出等号的直接证书，而最大匹配与最小覆盖仍可各有多种选择。

二分图公理库二分图Bipartite graph顶点可分成两个独立侧、且每条边都跨越两侧的有限简单无向图。上的最大匹配与最小顶点覆盖公理库顶点覆盖Vertex cover与图中每条边至少一个端点相交、从而覆盖全部边的顶点子集。由 Kőnig 定理相等。它可由 Hall 定理或网络流推导，也解释二分匹配线性规划为何具有整数最优解。任务分配、矩阵非零项的最少行列覆盖、最少监控点与Dilworth 定理公理库Dilworth 定理Dilworth's theorem有限偏序集的最大反链大小等于覆盖全部元素所需的最少链数。的匹配证明都利用这组原—对偶结构。