Clique of a given size problem is NP-complete

Statement

Lemma

Clique of a given size problem is NP-Complete.

Proof

We have already shown that Clique of a given size problem is in NP.

We will show that Independent set of a given size has a many-one reduction to Clique of a given size problem.

Suppose we have an undirected graph and a positive integer. If we are looking for an independent set of size , we will pass the complement graph and to the Clique of a given size problem.

Calculating the complement graph takes , therefore this reduction is in polynomial time.

Then if a clique is returned in then we return this as our independent set in .

This takes as we are doing no transformations to the output.

As Cliques in G are independent sets in the complement we have a solution to the Independent set of a given size if and only if we have a solution to the Clique of a given size problem.

This gives Clique of a given size problem is NP-hard making it NP-complete.