Variant of an approximation algorithm for vertex cover

Question

Here is an approximation algorithm that finds vertex cover of a graph.

 C = {}
 E' = {Edge set}
 while E' =/ 0
   Let (u,v) be an arbitrarily edge of E'
    C = C U {u,v}
    remove E' incident on u and v.
return C

A variant: what if instead of removing edges incident on both $u$ and $v$, we removed only $u$. Would this affect the optimal vertex cover? If so, how?

I somehow feel the optimal vertex cover remains the same whereas only the number of steps to remove the edges would increase increasing time and space complexity. Am I right?

Answer 1

Consider a star consisting of a center $x$ connected to the vertices $y_1,\ldots,y_n$. Your modified algorithm could act as follows:

1. Choose the edge $(x,y_1)$; add $x,y_1$ to the vertex cover; remove all edges incident to $y_1$.
2. Choose the edge $(x,y_2)$; add $x,y_2$ to the vertex cover; remove all edges incident to $y_2$.
3. ...

I'll let you take it from here.