I just started reading Vazirani's book "Approximation Algorithms". It is legally available online here.
On page 5 (23 in the pdf), it says that the following decision problems are in NP:
- Is the size of the minimum vertex cover in $G$ at most $k$?
- Is the size of the maximum matching in $G$ at least $l$?
I can't see why this is true. If, say, the first problem is in NP, then each valid instance (graph) has a Yes certificate which proves that the graph has a minimum vertex cover of size at most $k$.
But, how can one deduce from a certificate something regarding the size of the minimum vertex cover?