# Degree Reduction in Max Cut and Vertex Cover

I have been reading Alimonti and Kann's paper "Some APX-Completeness results for cubic graphs" and I don't understand why the degree-reduction gadgets for Max Cut and Min Vertex Cover have to be different.

Here are the two gadgets in question. The Min Vertex Cover gadget simply divides a degree $n$ node $v$ into a chain of nodes $v_1,u,v_2$, where $v_1$ and $v_2$ share the edges of $v$, increasing the Min Vertex Cover by 1 in the process. The Max Cut gadget on the other hand is rather more complicated and involves cycles. What I don't understand is why the simple Min Vertex Cover gadget can't be used for Max Cut?

Consider a degree 4 vertex $v$ in Max Cut. If you unfold the vertex as $v_1,u,v_2$ (as in the Min Vertex Cover example) you are adding 2 edges to the graph, both of which can be cut by placing $u$ on the opposite side of the cut to $v_1$ and $v_2$, so wouldn't the Max Cut just increase by 2? I'm probably missing something but I don't know what it is.

• Have you tried proving that this gadget works for Max Cut? Jun 16, 2016 at 13:46