Clique of a given size problem is in NP

Statement

Lemma

Clique of a given size problem is in NP.

Proof

This problem is in the form of a search problem as either you provide a clique of the required size or you say no such set exists.

For a undirected graph , positive integer , and supposed solution to the Clique of a given size problem. It takes to check this solution. We have to do two steps:

• Check .
• Check for all for all . The first step takes and the second .

Therefore this problem is in NP.