Edge cover

Formally, an edge cover of a graph is a set of edges such that each vertex in is incident with at least one edge in . The set is said to cover the vertices of . The following figure shows examples of edge coverings in two graphs (the set is marked with red). : A minimum edge covering is an edge covering of smallest possible size. The edge covering number is the size of a minimum edge covering. The following figure shows examples of minimum edge coverings (again, the set 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 in which every vertex is incident with exactly one edge in . 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 has edge covering number . == Algorithms ==

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 C and maximum matching M, letting c and m be the number of edges in C and M respectively, we have: |V| = c + m. Indeed, C contains a maximum matching, so the edges of C can be decomposed between the m edges of a maximum matching, covering 2m vertices, and the c-m other edges that each cover one other vertex. Thus, as C covers all of the |V| vertices, we have |V| = 2m + (c-m) giving the desired equality. == See also ==