Since the complement of a vertex cover is an independent set, you might be tempted to think that the approximation discussed in class also approximates independent set. In particular, consider the following algorithm for independent set:

- Run the 2-approximation for vertex cover discussed in class, let the output be S.
- Let I := V(G) \setminus S.
- If I = \emptyset, then let v \in V(G) be an arbitrary vertex; set I := \{v\}.

Let:

- p denote the size of a largest independent set in G
- q denote the size of the set obtained by taking the complement of the output of the 2-approximation discussed in class.
- r denote \max(q,1)

Note that r is the size of the independent set output by the algorithm above.

Come up with a graph where p can be a factor of cn larger than r for some constant c.