The SPARSE SUBGRAPH problem is defined as follows:

Input: where G is a graph and p, q ? Z.

Question: Does G have p vertices such that there are at most q edges between them? Prove that this problem is NP-hard by giving a polynomial-time reduction of INDEP-SET (known to be NP-hard) to SPARSE SUBGRAPH.

Hint. Any independent set of size k can be viewed as a sparse subgraph consisting of k vertices with no edges between them