Give an example of a graph G with at least 10 vertices such that the greedy 2-approximation algorithm for VERTEX-COVER given below is guaranteed to produce

a suboptimal vertex cover.

Algorithm (G) Input: A graph G output: A small vertex cover C for G C 0 while Gstill has edges do select an edge e (v, w) of G add vertices v and w to C for each edge f incident to v or w do remove f from G return C Algorithm 18.6: A 2-app roximation algorithm for VERTEx-CoVER