Prove Vertex-Cover of maximum degree 3 is NPC

Question

This is a homework question. I need to prove that the following language is in NP Complete:

3-VERTEX-COVER = $\{\langle G,k\rangle \mid$ G is an undirected graph, each vertex in $G$ has at most $3$ incident edges, and there is a vertex cover of size $k$ in $G\}$

Showing that it is in NP is easy. Now, to show that it is in NPC I thought about showing a reduction from Vertex-Cover. But I can't seem to think of what to do with a graph I get as <G,k> which is in Vertex-Cover, to make each vertex degree at most 3 without changing the vertex-cover property. Any hints?

Answer 1

Hint: Here is how to handle vertices of degree 4 (taken from Alimonti and Kann).

Let $v$ be a vertex of degree $4$, with neighbors $x_1,x_2,x_3,x_4$. Replace $v$ with a path $v_1-w-v_2$ and connect $x_1,x_2$ to $v_1$ and $x_3,x_4$ to $v_2$ (arbitrarily). A vertex cover in the original graph containing $v$ corresponds to a vertex cover in the new graph containing $v_1,v_2$. A vertex cover in the original graph not containing $v$ corresponds to a vertex cover in the new graph containing $w$. In total, we get that the original graph has a vertex cover of size $k$ iff the new graph has a vertex cover of size $k+1$.

The same idea works for vertices of higher degree.