# Prove that the greedy algorithm for the minimum edge cover problem is 2-approximation

As said, I had to prove that the greedy algorithm:

1. Initialize $$C = ∅$$
2. Look for an un-covered vertex and add one of its edges to $$C$$
3. Repeat 2 while there's uncovered vertices

Is a 2-approximation algorithm.

My take was:

Let's say that $$OPT$$ (the optimal solution) takes $$k$$ edges, we should prove that $$ALG$$ takes at most $$2k$$ edges.

Let's assume by contradiction that $$C=2k+1$$. That means that $$ALG$$ covers at least $$2k+1$$ vertices, because each edge chosen by $$ALG$$ covers at least one vertex. We get that $$OPT$$ covers at most $$2k$$ vertices but $$ALG$$ covers at least $$2k+1$$ which is a contradiction $$⇒ C ≤ 2k$$

Now that we proved that if $$OPT=k$$ we get that $$ALG ≤2k$$ we can easily show that $$\frac{ALG} {OPT}≤ 2$$

Is my proof correct?

No. Your proof would be "correct" for any constant, not only $$2$$ (which is a clear big red alert!).
Let $$OPT$$ be the optimal solution, and $$ALG$$ the solution from this algorithm. Notice that each edge in $$OPT$$ connects two vertices, and thus each such edge must contribute to the covering with at most 2 vertices. Hence, the number of vertices in the graph is at most $$2k$$ where $$k$$ is the number of edges in $$OPT$$. Since your algorithm will take an edge for every node at the worst case, the number of edges in $$ALG$$ must be at most $$2k$$. Hence, $$|ALG|\le 2\cdot |OPT|$$, which means that the algorithm is indeed a 2-approximation of the problem.