A maxcut of an undirected graph with nonnegative edge weights is a cut of maximum weight. The graph need not be a simple graph. A cut separates a nontrivial subset of vertices from its complement, and its weight is the sum of weights of crossing edges. Determining a maxcut is an NP-hard problem.
For an unweighted simple graph 
with 
edges, write 
for the maximum number of crossing edges.
Balla et al. (2024) prove
 |
where 
is the vector
chromatic number. Juliano (2026) proves that the constant 
is optimal. More precisely, for every 
, some simple graph
with 
edges
satisfies
 |
