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.
An edge cover minimizing the sum of selected edge weights. For nonnegative weights and no isolated vertex, it is computable in polynomial time by the minimum-weight edge cover by matching savings construction. It need not have minimum cardinality.
Articles by others on the same topic
In graph theory, an **edge cover** of a graph is a set of edges such that every vertex of the graph is incident to at least one edge in the set. In other words, an edge cover is a collection of edges that "covers" all vertices in the graph.