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?