Remember all of the following steps when showing that a problem D is NPcomplete: 1. Show that D is in NP by briefly explaining how to quickly verify a solution to it. 2. Choose another problem Q that is known to be NP-hard (one that we showed in class) and explain how you convert an instance of that problem into an instance of D (this is to show that D is NP-hard). 3. Explain why a yes-instance of Q gets turned into a yes-instance of D. 4. Explain why a no-instance of Q gets turned into a no-instance of D.

Consider the following problem 2-CLIQUE, and prove that it is NP-complete: Given a graph G and a number k, does G contain at least two subsets of nodes of size k, each of which is a clique (all nodes in that subset are connected to every other node in that subset)(Hint: use a similar technique to the DOUBLE-SAT proof from class)