Statement

Proof

We have shown that Vertex cover of a given size is NP-complete. So we will find a many-one reduction of Vertex cover of a given size to Minimum vertex cover problem to show it is NP-hard.

Suppose we have an undirected graph $G = (V,E)$ and a positive integer $g > 0$. If we are looking for a vertex cover of size at most $g > 0$, pass $G$ to our solution to the Minimum vertex cover problem.

This takes $O(1)$ as we are doing no manipulations.

We get back minimum cover $C$. If $\vert C \vert \leq g$ return $C$ to the Vertex cover of a given size problem, otherwise return no. This step takes $O(\vert V \vert)$ so is polynomial time in the input size.

If there is a vertex cover of size less than $g$ then the minimum vertex cover will have size less than $g$.

Equally if the minimum vertex cover has size less than $g$ then there is a vertex cover of size less than $g$.

So we have that Vertex cover of a given size has a many-one reduction to Minimum vertex cover problem. Giving that Minimum vertex cover problem is NP-hard.