Give an example of a graph for which APPROX-VERTEX-COVER always yields a suboptimal solution.
A graph with two node u,v and an edge(u,v). The optimal is either u or v. By running APPROX-VERTEX-COVER we get u and v. It is always a suboptimal solution.
Let A denote the set of edges that were picked in line 4 of APPROX-VERTEX-COVER. Prove that the set A is a maximal matching in the graph G.
It is obvious. Because in line 4, we randomly choose an edge (u,v) and delete all edges incident on either u or v. The remaining graph becomes a subproblem.
Follow @louis1992 on github to help finish this task