Statement

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 $G = (V,E)$, positive integer $g > 0$, and supposed solution $S$ to the Clique of a given size problem. It takes $O(\vert E \vert + \vert V \vert)$ to check this solution. We have to do two steps:

• Check $\vert S \vert \geq g$.
• Check for all $(u,v) \in E$ for all $u,v \in S$. The first step takes $O(\vert V \vert)$ and the second $O(\vert V \vert^2)$.

Therefore this problem is in NP.