reduction from MAX-CUT to MAX-3-CUT

Question

MAX-3-CUT gets a graph and a number $k$, and determines whether three sets of vertices can be found within that graph, where at least $k$ edges are in the cut. We define the cut as all edges $(u,v)$ where $u$ and $v$ are in a different set.

MAX-CUT also gets a graph and a number $k$, and does the same but by dividing it to two sets of vertices.

It is known that MAX-CUT is NP complete and I'm trying to show that MAX-3-CUT is also NP Complete by reducing from MAX-CUT.

What I've done so far:

1. Showing that MAX-3-CUT in NP is easy using a verifier.

2. I think the reduction should be, given $\langle G=(V,E),k \rangle$ return $\langle G',k+|V| \rangle$, where $G'=(V'=V+{w}, E'=E+\{(w,v) : v \in V\})$.

3. Proof of correctness: doing so, It's easy to show that if $\langle G,K \rangle$ is in MAX-CUT then $\langle G',k+|V| \rangle$ is in MAX-3-CUT by setting the third group to be $\{w\}$. The problem is I can't do the opposite direction: if $\langle G,k \rangle$ isn't in MAX-CUT than $\langle G',k+|V| \rangle$ isn't in MAX-3-CUT. I also tried to show that if $\langle G',k' \rangle$ is in MAX-3-CUT then $\langle G,k \rangle$ is in MAX-CUT but I get stuck with how to turn 3 sets into 2.

Note: I was able to show that MAX-3-CUT is NPC by reducing from 3COL (pretty straightforward), but I need it to be reduced from MAX-CUT.

Answer 1

Hint : Consider $G '=(V'=V \cup\{w_i|i\in [1,|V|]\},E'=E\cup\{(w_i,v)|v \in V , i\in [1,|V|]\})$ and $k'=|V|^2+k $

Consider a partition of V' in 3 parts, call $P $ the one with the smallest number of nodes in $V $.

Note that by putting a w in P , if it were not in it, you increase the number of edges in your 3cut.

Then, note that if all the ws are in the same part, then removing a node of V from that part increases the number of edges in your 3cut.