Max clique problem is NP-hard

Statement

Lemma

Max clique problem is NP-hard.

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 and integer . Pass this graph to the Max clique problem. This step is as we need to do no manipulation.

The solution provides a max clique. If then return , otherwise return no. This step takes so it is polynomial in the input size.

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

If the graph has a max clique of size greater than then it has an clique of size by definition.