To solve an instance of an edge cover, we can use the maximum matching algorithm.

Edge Cover: 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 of the set [from Wikipedia].

Maximum matching: a matching or independent edge set in a graph is a set of edges without common vertices [from Wikipedia].

For example to find the min edge cover of the example below, we can:

1- Find a maximum matching.

2- Extending it greedily so that all vertices are covered.

The image below present this solution:

enter image description here

My question is why this reduction works, is there a proof for that result,? or at least an intuition!

How can be sure that the final solution is the min edge cover of the graph and there is no other edge cover with size less than the founed solution.


Every edge connects exactly two vertex, thus for $n$ vertices, the minimum edge cover uses between $n/2$ and $n$ edges. In fact every new edge you add to your subset covers either 1 new vertex, or 2 new vertices. When it is 2 new vertices, the edge is part of the maximum matching.

$k$ the number of edge needed for the cover is:

$k = n - a$

with $a$, the number of edges in the maximum matching (at most $a = n/2$).

Starting from the maximum matching, you cannot have any new edge covering 2 vertices (or a re-arrangement of edges that augment $a$). Either it would not be a "maximum matching".

The greedy part of the algorithm just collects the 1 vertex covering edges needed to complete the problem.


Suppose a maximum matching, of size r say, is removed from the graph, along with the endpoints of edges of the matching and edges incident to these endpoints. Suppose k vertices remain. These k vertices form an independent set (otherwise the graph would have had a larger matching, a contradiction)and so covering them requires k separate edges. So a minimum edge cover has size r+k.

Intuitively, you want a maximum matching because then you get to cover the most number (ie two) of distinct vertices with each edge of the cover, thereby using few edges.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.