# 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$, we pass $G$ to our solution for the Minimum vertex cover problem .

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

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

If there is a vertex cover of size at most $g$, then the minimum vertex cover will have size at most $g$.

Conversely, if the minimum vertex cover has size at most $g$, then there is a vertex cover of size at most $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 .