Let 
be a (not necessarily simple)
undirected edge-weighted graph with nonnegative
weights. A cut 
of 
is any nontrivial subset of 
, and the weight of the cut is the
sum of weights of edges crossing the cut. A maxcut is then
defined as a cut of 
of maximum weight. Determining the maxcut of a graph is an
NP-hard problem.
Maxcut
See also
Cut, Mincut, Weighted GraphExplore with Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Maxcut." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Maxcut.html