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.
Any leads?