Statement

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 $G = (V,E)$ if we are provided with a purposed solution $C$ to the problem there are two steps to checking it:

• Check that $\vert C \vert \geq g$, this takes $O(\vert V \vert)$.
• Check for every edge $(u,v) \in E$ that $u \in S$ or $v \in S$, that takes $O(\vert E \vert \cdot \vert V \vert)$. Therefore checking a solution takes polynomial time in the input size.

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