# Prove that Vertex Cover belongs to NP

How to prove that the problem VERTEX-COVER belongs to $NP$?

The problem VC is defined as follow:

INSTANCE: Graph $G = (V,E)$ and an integer $k$

PREDICATE: Is there a subset $V_1 \in V$ s.t $\mid V_1 \mid \leq k$ and $\forall (u,v) \in E$ $u \in V_1$ or $v \in V_1$ ?

My approach:

I know that the class $NP$ can be defined as the class of all problems that can be solved using non-deterministic algorithms that runs in polynomial time.

Therefore, i can guess if $\mid V_1 \mid \leq k$ then test for each node in $E$ if $u$ or $v$ belongs to $V_1$. In this case return $TRUE$, otherwise $FALSE$.

• For which $V_1$ do you guess whether $|V_1| \leq k$? – Yuval Filmus Nov 4 '17 at 15:25
• For all $V_j$ i think – Jack Nov 4 '17 at 16:00
• There are exponentially many potential $V_1$s. You want a (nondeterministic) polynomial time algorithm. – Yuval Filmus Nov 4 '17 at 16:01
• So what about using a "Guess function" that do this task ? – Jack Nov 4 '17 at 16:06
• The question asks you to spell out how this would work. – Yuval Filmus Nov 4 '17 at 16:07