Suppose we find the minimum vertex cover of a graph by repeatedly choosing the vertex with the highest degree and delete all edges incident on that vertex, until there are no edges left. How can one construct a graph such that the approximation ratio is unbounded ?
My attempt : we need to construct a graph that we know the size of the minimum vertex cover. If we contruct a bipartite graph $ G $ with $A$ having $n$ vertices and $B$ have $n * f(n)$ vertices. Assume that if the algorithm has to choose among equal-degree nodes, then it always picks the nodes in $B$ first. Then we should add edges in a way that at any step in the algorithm, no nodes in $A$ has degree strictly greater than degree of any node in $B$. Then the algorithm will select of the nodes in $B$, so the approximation ratio will equal $f(n)$ so it is unbounded.
Is this the right direction? I'm having difficulty with how to add edges.