[TECH] A Graph with θ(log(n)) approximation ratio for greedy vertex cover

We know that the greedy algorithm (which picks the vertex with next highest degree) to solve the vertex cover problem is not optimal. However we have 2-Approximation algorithm for the vertex cover problem (based on a integer linear programming formulation). Actually it was not very straight forward to for me prove that the greedy algorithm has an approximation ratio greater than 2. However after some thinking the following construction indeed proves that the greedy algorithms approximation ratio is > 2. In fact we can easily see (from the figure) that the greedy algorithm will first pick the node with highest degree i.e n (the magenta). Then it deletes all the edges adjacent on the magenta node and continues and clearly the greedy algorithm will have all the nodes in the blue bounding box. However its clear that if we choose the nodes in the oval region we get a minimum vertex cover of size n. The size of greedy vertex cover is n/2 + n/3 + n/4 .... n/n ≈ θ(nlog(n)) (for large n) and hence the approximation ratio for this graph is θ(log(n)).