# Prove Vertex-Cover of maximum degree 3 is NPC

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?

• You can change the vertex cover property as long as it's in a controlled way. Jun 2 '15 at 13:21

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.

• does that work for if we try to reduce a vertex of degree 3 ?
– Perl
Apr 1 at 4:51
• Vertex cover is easy for graphs of maximum degree 2. Apr 1 at 4:52
• I meant for graphs of maximum degree 3
– Perl
Apr 1 at 4:53
• This shows that you can reduce the maximum degree to 3. Apr 1 at 4:54