边覆盖

边覆盖（edge cover）是一组边，使每个顶点都至少与其中一条边关联。它选择边来照顾全部顶点，区别于选择顶点以覆盖全部边的顶点覆盖。有限无向简单图中，只有没有孤立顶点时才存在边覆盖；存在时最少边数记为 $\rho (G)$。

例如，顶点为 $a,b,c,d,e$，边为 $ab,ac,bc,cd,de$。选择 $F=\{ab,ac,de\}$ 后，$a$ 接着两条所选边，$b,c,d,e$ 各接着一条，故全部顶点均被覆盖。边之间允许公共端点；若要求所选边两两不接触，得到的是匹配。

先选匹配ab、de，再给未覆盖顶点c补上边ac，得到三边覆盖。

存在条件与最初的下界

精确定义是 $F\subseteq E$ 且对每个 $v\in V$，存在 $e\in F$ 以 $v$ 为端点。若有孤立顶点，它没有任何可选关联边，因此边覆盖不存在；反过来，无孤立顶点时选全部边便给出一个边覆盖。所以这一条件既必要又充分。

一条边最多覆盖两个顶点，所以 $n$ 点图若有边覆盖，必满足 $\rho (G)\ge \lceil n/2\rceil$。等号未必达到：星图 $K_{1,4}$ 的四片叶子各只有自己的那条边，全部四条都必须选，而 $\lceil 5/2\rceil =3$。要得到精确值，需要知道有多少顶点能用互不相接的边成对覆盖。

最大匹配决定最小边覆盖

定理。 对无孤立顶点的有限无向简单图，若最大匹配大小为 $\nu (G)$，则 $$\rho (G)=n-\nu (G).$$

上界证明。 取最大匹配 $M$，它的 $\nu$ 条边覆盖 $2\nu$ 个顶点，剩下 $n-2\nu$ 个未匹配顶点。任意两个未匹配顶点不能相邻，否则可将它们之间的边加入 $M$，得到更大匹配。每个未匹配点因无孤立点而至少有一个邻居，这个邻居必已匹配。为每个未匹配点任选一条关联边加入；这些新增边彼此不同，因为一条边不可能连接两个未匹配点。共选择 $$\nu +(n-2\nu )=n-\nu$$ 条边，且所有顶点都被覆盖，故 $\rho \le n-\nu$。

下界证明。 任取一个边覆盖 $F$，考察图 $(V,F)$ 的 $c$ 个连通分量。每个分量至少含两个顶点，因为边覆盖不留孤立点。一个含 $n_i$ 个顶点的连通分量至少有 $n_i-1$ 条边，求和得 $\mathrm{\#}F\ge n-c$。从每个分量任取一条边，不同分量的边互无公共端点，构成大小 $c$ 的匹配。因此 $c\le \nu$，于是 $$\mathrm{\#}F\ge n-c\ge n-\nu .$$ 所有边覆盖都受此下界限制，与上界相合，定理得证。连通图至少有“顶点数减一”条边，可由逐个接入新顶点或取一棵生成树证明。

五顶点主例与星图变式

主例中 $\{ab,de\}$ 是大小二的匹配。五个顶点不可能支持三条互不相接的边，所以最大匹配恰为二；定理给出 $\rho =5-2=3$。未匹配顶点 $c$ 可用 $ac$、$bc$ 或 $cd$ 中任一条补上，得到不同的最小边覆盖。

变式。 五顶点星图的最大匹配大小为一，因为所有边都通过中心。定理给出 $\rho =5-1=4$，与逐片叶子检查一致。若误把“每条边可覆盖两点”的粗下界三当成答案，就会遗漏至少一片只有单一邻边的叶子。

再向主例添加孤立顶点 $f$，顶点数变六而匹配数仍为二，数值 $n-\nu =4$ 仍可写下，但不等于任何最小边覆盖，因为边覆盖根本不存在。这说明定理中的无孤立顶点条件不能省略。空顶点图可另约定空边集是边覆盖、$\rho =\nu =0$，与公式相容。

极小覆盖和其他覆盖概念

一个边覆盖若删去任一所选边后都失去覆盖性质，称为极小边覆盖；它不一定边数最少。在四顶点路径 $a-b-c-d$ 中，全部三条边并非极小，因为删掉中间边仍有 $ab,cd$ 覆盖四点。对于更复杂图，判别极小性只检查能否删一条，判别最小性要比较所有候选，二者不可混淆。

最小边覆盖通常不是匹配：主例需要三条边，而五点图最多只能有两条互不相接的边；至少两条所选边要共享端点。只有存在完美匹配时，才可用 $n/2$ 条匹配边同时达到最小边覆盖。若边带不同费用，最小费用边覆盖又改变优化目标，不能只由最大匹配的边数直接读出最优费用。