问题及解答

定理. 设 $M$ 是图 $G$ 的匹配, $K$ 是覆盖, 则:

(1) $|M|\leqslant |K|$;

(2) 若 $|M|=|K|$, 则 $M$ 是最大匹配, $K$ 是最小覆盖.

(1) 不妨假设 $M$ 是图 $G$ 的最大匹配. 对于 $M$ 中每条边取一个顶点, 构成集合 $K_M$. 这个 $K_M$ 不一定是图 $G$ 的覆盖. 因为可能 $M$ 不是图 $G$ 的完美匹配. 也即是说, 可能存在某些点, 它们并不是 $M$-饱和的. 将这些点构成的集合记为 $K_c$.

则 $K_M\cup K_c$ 是图 $G$ 的一个覆盖. 如果去掉其中一些孤立的点(即在图 $G$ 中与 $M$ 中的边不相关的点), 那么最终得到的是最小覆盖 $K$.

从而 $|M|\leqslant |K|$.

(2) 假设等号成立, $|M|=|K|$. 则由上面的证明, 可知 $M$ 一定是最大匹配, $K$ 是最小覆盖.