# Graph coloring decision problem NP-complete

Given a graph $$G = (V, E)$$ and a natural number $$k$$, consider the problem of determining whether there is a way to color the vertices with two colors in such a way that at least $$k$$ edges are polychromatic.

Prove that this problem is NP-complete.

I thought about reducing it to the 3-colorability problem, but I can't figure out a possible transformation that would work.

• Depends what you mean. Literally, it's the same thing as having at most $m-k$ monochromatic edges, where $m$ is the total number of edges. But, in complexity terms, it doesn't matter whether you call that number $m-k$ or $k'$ or just $k$. – David Richerby Dec 7 '17 at 15:01
A simpler reduction is from MAX-CUT. The idea is to represent each edge as a gadget which is a complete bipartite graph having $N$ vertices on each side. By choosing $N$ large enough, we can force any potential coloring to color all vertices on one side using color 1, and all vertices on the other side using color 2. You can now connect these gadgets in such a way that the maximum number of bichromatic edges is closely related to the maximum cut in the original graph.