Vertex cover of a given size is NP

Statement

Lemma

Vertex cover of a given size is NP.

Proof

First note that this problem is of the correct form to be a search problem. Either there is a vertex cover of the required size and we return it or we say no such cover exists.

For a undirected graph if we are provided with a purposed solution to the problem there are two steps to checking it:

• Check that , this takes .
• Check for every edge that or , that takes . Therefore checking a solution takes polynomial time in the input size.

This gives that the Vertex cover of a given size is in NP.