As said, I had to prove that the greedy algorithm:
- Initialize $C = ∅$
- Look for an un-covered vertex and add one of its edges to $C$
- 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?