# 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