Simple example: 2-approximation for vertex cover I am having trouble finding an example for the following algorithm to prove that it calculates a 2-approximation:


  Repeatedly select a vertex $v$ of highest degree, add one of its edges $(v,w)$ to the cover, and remove all edges incident to $v$ or $w$.


Please give me insights on how to pick an example.
Hint:


Prove the stronger claim that if $M$ is any matching, then any vertex cover must contain at least $|M|$ vertices.
Conversely, if $M$ is any maximal matching (a matching which cannot be extended), then the $2|M|$ vertices in $M$ form a vertex cover.
Show that the greedy algorithm that you describe constructs a maximal matching.
Conclude that your algorithm (modified so that it outputs a set of vertices rather than a set of edges) is a 2-approximation for minimum vertex cover.
Consider the complete bipartite graph $K_{n,n}$. What is its minimum vertex cover? What vertex cover does your algorithm produce?