The SPARSE SUBGRAPH problem is defined as follows:

Input: hG, p, qi 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).