= Solution
Use <minimum-weight edge cover by matching savings>. Reject inputs with an <isolated vertex>. For every <vertex> $v$, choose a cheapest incident <edge> $e_v$ and write $c_v=w(e_v)$. Define a baseline and a saving for each <edge> $uv$ by
$$
B=\sum_{v\in V}c_v,\qquad p(uv)=c_u+c_v-w(uv).
$$
Compute a <maximum-weight matching> $M$ using $p$ as its weights, allowing the empty <matching in a graph> and imposing no maximum-<cardinality> condition. Negative savings may be ignored. Return
$$
F_M=M\cup\{e_v:v\text{ is an unmatched vertex of }M\}.
$$
This is an <edge cover>. Since original weights are nonnegative, removing duplicate appearances of an <edge> cannot increase the total, and hence
$$
w(F_M)\leq w(M)+\sum_{v\text{ unmatched}}c_v=B-\sum_{e\in M}p(e).
$$
To prove optimality, take a minimum-weight <edge cover> and remove redundant <edges> until it is inclusion-minimal. Nonnegative weights ensure that its weight does not increase, so it remains optimal. As proved in (i), its components are <star graphs>. Choose one <edge> from each <star graph>, forming a <matching in a graph> $N$.
In a <star graph> with center $a$, selected leaf $b$, and other leaves $L$, this choice contributes $w(ab)+\sum_{v\in L}c_v$ to $B-p(N)$. Each other leaf $v$ has its <edge> $av$ available, so $c_v\leq w(av)$. Thus this contribution is at most the weight of that <star graph>. Summing over components yields
$$
B-p(N)\leq\operatorname{OPT}.
$$
Since $M$ maximizes saving, $p(M)\geq p(N)$, and consequently
$$
\operatorname{OPT}\leq w(F_M)\leq B-p(M)\leq B-p(N)\leq\operatorname{OPT}.
$$
All inequalities are equalities. Therefore \b[$F_M$ is a minimum-weight <edge cover>]. This proof also handles zero weights and duplicate cheapest-<edge> choices.
Finding all $c_v$ and constructing $F_M$ takes $O(|V|+|E|)$ time. A general-<graph> <maximum-weight matching> <polynomial-time algorithm> supplies the only substantial step; the documented routine runs in $O(|V|^3)$ arithmetic time. Exact rational or integer weights avoid floating-point comparisons affecting optimality.<Maximum-weight matching documentation by NetworkX>[max_weight_matching, maxcardinality=False; Notes: O(number_of_nodes \*\* 3), integer arithmetic for integer weights, and floating-point precision caveat]{ref}
Back to article page
