Max-cut is simply a division of the vertices of an arbitrary graph into two subsets, such that the number of edges going from vertices in one subset to vertices in the other subset is maximized. From Garey and Johnson, max-cut is NP-complete.

Note that max-cut is different from max bisection in that max cut does not require the subsets to have equal size. However, both problems are NP-complete.