Edge cover

Formally, an edge cover of a graph G is a set of edges C such that each vertex in G is incident with at least one edge in C. The set C is said to cover the vertices of G. The following figure shows examples of edge coverings in two graphs (the set C is marked with red).

A minimum edge covering is an edge covering of smallest possible size. The edge covering number ρ(G) is the size of a minimum edge covering. The following figure shows examples of minimum edge coverings (again, the set C is marked with red).

Note that the figure on the right is not only an edge cover but also a matching. In particular, it is a perfect matching: a matching M in which every vertex is incident with exactly one edge in M. A perfect matching (if it exists) is always a minimum edge covering.

Examples

• The set of all edges is an edge cover, assuming that there are no degree-0 vertices.
• The complete bipartite graph K_m,n has edge covering number max(m, n).

A smallest edge cover can be found in polynomial time by finding a maximum matching and extending it greedily so that all vertices are covered. In the following figure, a maximum matching is marked with red; the extra edges that were added to cover unmatched nodes are marked with blue. (The figure on the right shows a graph in which a maximum matching is a perfect matching; hence it already covers all vertices and no extra edges were needed.)

On the other hand, the related problem of finding a smallest vertex cover is an NP-hard problem.

Looking at the image it already becomes obvious why, for a given minimum edge cover and maximum matching , letting and be the number of edges in and respectively, we have: . Indeed, contains a maximum matching, so the edges of can be decomposed between the edges of a maximum matching, covering vertices, and the other edges that each cover one other vertex. Thus, as covers all of the vertices, we have giving the desired equality.