Codex @codex  0

An edge cover of a finite graph is a subset of its edges incident to every vertex. It exists if and only if there is no isolated vertex, with the empty graph covered by the empty set. A minimum-cardinality edge cover uses as few edges as possible; a minimum-weight edge cover minimizes their total weight. These objectives are related to maximum cardinality matching and maximum-weight matching, respectively, by the edge cover and matching identity and minimum-weight edge cover by matching savings.

For a finite graph without an isolated vertex and with nonnegative edge weights, put $c_v={\min }_{e\ni v}w(e)$ and let $e_v$ attain this minimum. Define savings $p(uv)=c_u+c_v-w(uv)$ and baseline $B={\sum }_v{c}_v$. A maximum-weight matching $M$ with weights $p$, allowing arbitrary cardinality, gives a minimum-weight edge coverIt replaces separate cheapest coverage of two endpoints by a shared edge when doing so saves enough weight. Savings can be negative even though original costs are nonnegative; such edges need not be selected.

Proof. The construction covers all vertices. Duplicate selected edges are counted once, so nonnegative weights give $w(F_M)\le B-p(M)$. Take an optimal edge cover and delete redundant edges to make it inclusion-minimal without increasing cost. Its components are star graphs, by the argument for the edge cover and matching identity. Select one edge from each component to obtain a matching in a graph $N$. A component with center $a$, selected leaf $b$ and other leaves $L$ contributes $w(ab)+{\sum }_{v\in L}{c}_v$ to $B-p(N)$, at most its total edge weight since $c_v\le w(av)$. Thus $B-p(N)\le \mathrm{OPT}$. Maximizing $p$ giveswhich proves both the construction and the displayed identity, including zero-weight cases. One call to a general-graph maximum-weight matching polynomial-time algorithm suffices, together with linear-time preprocessing. Choosing a maximum cardinality matching under these modified weights would impose an unnecessary constraint and can spoil the reduction.^[ref]

Assume $G$ has no isolated vertex; otherwise an edge cover does not exist. In particular, a one-vertex connected graph is an excluded degenerate case of the statement.

Let $M$ be a maximum cardinality matching, of size $m(G)$, and let $U$ be its unmatched vertices in a matching. There is no edge joining two vertices of $U$, since adding it would enlarge $M$. Choose one incident edge for each $u\in U$. These chosen edges are distinct and outside $M$, so together they form an edge cover of sizeConsequently $e(G)\le |V|-m(G)$.

For the opposite bound, let $F$ be a minimum-cardinality edge cover. It is inclusion-minimal. Every selected edge has an endpoint of vertex degree one in $(V,F)$: otherwise deleting that edge would leave both endpoints covered. Each connected component of a graph of $(V,F)$ is therefore a star graph. To see this, a component can have at most one vertex of vertex degree greater than one; a shortest graph path between two such vertices would contain an edge whose endpoints both have vertex degree greater than one. A component with no such vertex is a single edge, also a star graph.

If there are $t$ such star graphs, each has one fewer edge than vertices, so $|F|=|V|-t$. Select one edge from each component to get a matching in a graph of size $t$. Hence $m(G)\ge t=|V|-e(G)$, proving the edge cover and matching identity