Reduce Vertex Cover with size k to Vertex Cover with size n/2 Disclaimer: This is a homework question.

I would like to reduce vertex cover problem to the following problem:

$$L = \{G \mid G\text{ has a vertex cover of size } |V(G)|/2\}\,.$$

I have divided the problem into three parts:


$k = n/2$: This case is trivial.
$k &gt; n/2$: Yes in vertex cover problem does not necessarily mean yes in $L$.
$k &lt; n/2$: No in vertex cover problem does not necessarily mean no in $L$.


I know that I need to change graph $G$ into $G'$ somehow to map results of VC to $L$.

Any advice on how to do so is appreciated.
For $k&lt;n/2$, add an isolated complete graph with $n-2k+2$ vertices (note it takes at least $m=n-2k+1$ vertices to cover this complete graph). Now there is a vertex cover of size $(n+(n-2k+2))/2=n-k+1$ in the new graph iff there is a vertex cover of size $(n-k+1)-m=k$ in the old graph.

For $k&gt;n/2$, add $2k-n$ isolated vertices. Now there is a vertex cover of size $(n+(2k-n))/2=k$ in the new graph iff there is a vertex cover of size $k$ in the old graph.