= Solution
First test for an <isolated vertex>, reporting infeasibility if one exists. Otherwise compute a <maximum cardinality matching> $M$ using a general-<graph> <polynomial-time algorithm>, then add one arbitrary incident <edge> for each <unmatched vertex in a matching>. The proof in (i) shows that the resulting <edge cover> has \b[minimum <cardinality> $|V|-|M|$].
The final scan takes $O(|V|+|E|)$ time with <adjacency lists>; the <maximum cardinality matching> computation is polynomial. One may obtain it from a general-<graph> <maximum-weight matching> routine with every weight equal to one.<Maximum-weight matching documentation by NetworkX>[max_weight_matching, unit weights give maximum cardinality; Notes: cubic vertex-count running time]{ref}
Back to article page
