Given a graph G = (V(G), E(G)), consider the following strategy for finding a minimum vertex cover in a graph. 

Step 0: Start with S =∅. 

Step 1: Find a vertex v of maximum degree (one that has the greatest number of incident edges). Add this vertex to S. 

Step 2: Delete v and all its incident edges from G. If G is now edgeless, stop. Otherwise, repeat Steps 1 and 2. Either show that this strategy always finds a minimum vertex cover for G or find a graph for which it fails to do so.