Reducing Vertex Cover to Half Vertex Cover I need to reduce Vertex Cover to Half Vertex Cover using a Karp reduction:

Vertex Cover: Given a graph $G = (V,E)$ and an integer $k$, is there a subset of $V$ of size $k$ which intersects all edges?

Half Vertex Cover: Given a graph $G = (V,E)$ and an integer $k$, is there a subset of $V$ of size $k$ which intersects exactly half the edges?

I will be happy if you can tell me how to do that and why the reduction works (both directions of the proof).
Let special vertex cover be the special case of vertex cover in which $|V| = 2k+1$. We later reduce vertex cover to special vertex cover.

Now suppose we're given an instance $G = (V,E),k$ of special vertex cover. Construct an instance $G',k$ of half vertex cover by attaching $|E|$ new edges to each vertex in $V$.

The total number of edges in the new graph is $|E|(|V| + 1)$. A vertex cover of size $k$ in the original graph covers this many edges in the new graph:
$$
|E|(1+k) = |E|\left(1 + \frac{|V|-1}{2}\right) = |E| \frac{|V| + 1}{2},
$$
exactly half the edges. Conversely, consider any $k$ vertices of the new graph, which cover exactly half of the edges. If they cover $m$ of the original edges then they cover at most $m + k|E|$ edges of $G'$, where $m \leq |E|$. The calculation above shows that $m = |E|$, that is, all edges of $G$ are covered.

It remains to reduce vertex cover to its special case. If $|V| = 2k+1$ then there is nothing to do.

If $|V| &lt; 2k+1$, then we add $\delta := 2k+1 - |V|$ many paths of length 2 edges. The new graph $G'=(V',E')$ has a vertex cover of size $k' = k + \delta$ iff the original graph had a vertex cover of size $k$. Note that
$$
|V'|-2k' = (|V| + 3\delta) - 2(k+\delta) = |V| - 2k + \delta = 1.
$$

Similarly, if $|V| &gt; 2k+1$ then we add $\delta := |V| - (2k+1)$ many triangles. The new graph $G'=(V',E')$ has a vertex cover of size $k' = k + 2\delta$ iff the original graph had a vertex cover of size $k$. Note that
$$
|V'|-2k' = (|V| + 3\delta) - 2(k+2\delta) = |V| - 2k - \delta = 1.
$$