Contents

Edge cover

Definition[edit]

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).

Aminimum 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[edit]

• 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).

Algorithms[edit]

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.^[1][2] 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.^[1]

Looking at the image it already becomes obvious why, for a given minimum edge cover ${\displaystyle C}$ and maximum matching ${\displaystyle M}$, letting ${\displaystyle c}$ and ${\displaystyle m}$ be the number of edges in ${\displaystyle C}$ and ${\displaystyle M}$ respectively, we have:^[3] ${\displaystyle |V|=c+m}$. Indeed, ${\displaystyle C}$ contains a maximum matching, so the edges of ${\displaystyle C}$ can be decomposed between the ${\displaystyle m}$ edges of a maximum matching, covering ${\displaystyle 2m}$ vertices, and the ${\displaystyle c-m}$ other edges that each cover one other vertex. Thus, as ${\displaystyle C}$ covers all of the ${\displaystyle |V|}$ vertices, we have ${\displaystyle |V|=2m+(c-m)}$ giving the desired equality.

See also[edit]

• Vertex cover
• Set cover – the edge cover problem is a special case of the set cover problem: the elements of the universe are vertices, and each subset covers exactly two elements.

Notes[edit]

References[edit]

• Weisstein, Eric W. "Edge Cover". MathWorld.
• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5.