# 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 straightforward 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 $|C| \geq g$, then return $C$, otherwise return no. This step takes $O(|V|)$ 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 clique of size at least $g$, then its max clique is of size $\geq g$ by definition.