Minimum vertex cover problem is NP-hard

Statement

Lemma

Minimum vertex cover problem is NP-hard.

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 and a positive integer . If we are looking for a vertex cover of size at most , pass to our solution to the Minimum vertex cover problem.

This takes as we are doing no manipulations.

We get back minimum cover . If return to the Vertex cover of a given size problem, otherwise return no. This step takes so is polynomial time in the input size.

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

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

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.