Independent set of a given size is in NP

Statement

Lemma

Independent set of a given size is in NP.

Proof

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

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

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

Therefore this problem is in NP.