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:
My question is why this reduction works, is there a proof for that result? or at least an intuition to help me undestand!
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 founded solution.