# Why minimum vertex cover problem is in NP

I am referring to the definition of the minimum vertex cover problem from the book Approximation Algorithms by Vijay V. Vazirani (page 23):

Is the size of the minimum vertex cover in $$G$$ at most $$k$$?

and right after this definition, the author states that this problem is in NP.

My question: What would be a yes certificate?

Indeed, our non-deterministic algorithm could guess a subset of vertices, denoted by $$V’$$, and we can verify if $$V’$$ is a vertex cover of some cardinality in polynomial time, but how could we possibly show that $$V’$$ is minimum in polynomial time?