Vertex cover of a given size is NP-complete

Statement

Lemma

Vertex cover of a given size is NP-complete.

Proof

As Vertex cover of a given size is NP we only need to show the problem is NP-hard.

We will show that the Independent set of a given size has a many-one reduction to the Vertex cover of a given size.

Suppose we have a undirected graph and a positive integer and we are looking for a independent set of size .

Provide and to the Vertex cover of a given size problem. This takes as we are doing no manipulation to the graph.

If we are provided a vertex cover of size at most return the set as the solution to the Independent set of a given size problem. This takes to run so is polynomial time in the input size. (Here so is of the correct size.)

If there is a solution to the Independent set of a given size with the size of at least then the compliment is a vertex cover of size at most from Vertex cover if and only if the complement is an independent set.

Similarly if there is a solution to the Vertex cover of a given size with size of at most then the compliment is a independent set of size at least from Vertex cover if and only if the complement is an independent set.

Therefore as Independent set of a given size is NP-complete we have Vertex cover of a given size is NP-hard, which from above gives us it is NP-complete.