# Vertex cover of a given size is NP

Last edited: 2026-01-28

# 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 an 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 $|C| \leq g$, this takes $O(|C|)$.
  • Check for every edge $(u,v) \in E$ that $u \in C$ or $v \in C$, that takes $O(|E|)$. Therefore checking a solution takes polynomial time in the input size.

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