Statement

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 $G = (V,E)$ and $g > 0$ a positive integer. If we are looking for an independent set of size $g$, we will pass $G^C$ the complement graph and $g$ to the Clique of a given size problem.

Calculating the complement graph takes $O(\vert V \vert^2)$, therefore this reduction is in polynomial time.

Then if a clique $S$ is returned in $G^C$ then we return this as our independent set in $G$.

This takes $O(1)$ 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.