Exercise 5 (2 pts). The DENSE 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 least q edges between them?

Prove that this problem is NP-hard by giving a polynomial-time reduction of CLIQUE (known to be NP-hard) to DENSE SUBGRAPH. Hint. If a set of k vertices is a clique, how many edges are there between these k vertices?