问题

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

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

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