Statement

Proof

We know the Clique of a given size problem is NP-complete, therefore it is NP-hard. We can reduce the Clique of a given size problem to Max clique problem using the straight forward Many-one reduction.

Suppose we have a graph $G$ and integer $g \geq 1$. Pass this graph $G$ to the Max clique problem. This step is $O(1)$ as we need to do no manipulation.

The solution provides $C$ a max clique. If $\vert C \vert \geq g$ then return $C$, otherwise return no. This step takes $O(\vert V \vert)$ so it is polynomial in the input size.

If the graph $G$ has a clique of size at least $g$ then its max clique is of size $\geq g$, so we return true in the case.

If the graph $G$ has a max clique of size greater than $g$ then it has an clique of size $\geq g$ by definition.