A graph bisection is a set partition of the vertex set of a graph into two parts whose sizes differ by at most one (Lee et al. 2013). Its size is the number of edges joining different parts. For a weighted graph, its weight is the sum of the weights of those edges. A maximum-weight bisection maximizes this sum subject to the balance requirement.
For a finite simple graph with maximum
vertex degree at most an odd positive integer
and arbitrary nonnegative real edge weights,
Gerke et al. (2026) proved
where
is the total edge weight and
is the maximum bisection weight. For a positive even
integer
, this gives
Both coefficients are sharp, with equality for the complete graph
with all edge weights equal to 1. Neither connectedness nor a positive minimum
vertex degree is required.
These sharp universal guarantees coincide with those for an unrestricted cut, although balance can reduce the optimum for an individual graph.
For example, the star graph with unit edge weights has maximum cut weight
but maximum bisection weight
(Gerke et al. 2026).
Wu and Zeng (2026) prove that every finite triangle-free graph of maximum vertex
degree at most 3, other than the entire claw graph , has a bisection of weight at least
of its total nonnegative edge weight. The graph may be
disconnected and may contain claw components, provided it is not itself
. The constant is sharp: the unweighted Petersen
graph has 15 edges and maximum bisection size 11. More strongly, each graph in
the theorem admits one probability distribution on bisections in which every edge
is cut with probability at least
. The result also holds for
loopless triangle-free subcubic multigraphs, counting
multiplicities in the degree and excluding the entire claw.