Minimum-weight edge cover by matching savings ($\mathrm{OPT}={\sum }_v{c}_v-{\max }_M{\sum }_{uv\in M}(c_u+c_v-w(uv))$)

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]