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