# networkx.algorithms.covering.min_edge_cover¶

min_edge_cover(G, matching_algorithm=None)[source]

Returns a set of edges which constitutes the minimum edge cover of the graph.

A smallest edge cover can be found in polynomial time by finding a maximum matching and extending it greedily so that all nodes are covered.

Parameters
Returns

min_cover – It contains all the edges of minimum edge cover in form of tuples. It contains both the edges (u, v) and (v, u) for given nodes u and v among the edges of minimum edge cover.

Return type

set

Notes

An edge cover of a graph is a set of edges such that every node of the graph is incident to at least one edge of the set. The minimum edge cover is an edge covering of smallest cardinality.

Due to its implementation, the worst-case running time of this algorithm is bounded by the worst-case running time of the function matching_algorithm.

Minimum edge cover for bipartite graph can also be found using the function present in networkx.algorithms.bipartite.covering