TOPICS
Search

Graph Bisection


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 G with maximum vertex degree at most an odd positive integer k and arbitrary nonnegative real edge weights, Gerke et al. (2026) proved

 bis_w(G)>=(k+1)/(2k)w(G),

where w(G) is the total edge weight and bis_w(G) is the maximum bisection weight. For a positive even integer k, this gives

 bis_w(G)>=(k+2)/(2(k+1))w(G).

Both coefficients are sharp, with equality for the complete graph K_(k+1) 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 K_(1,2r-1) with unit edge weights has maximum cut weight 2r-1 but maximum bisection weight r (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 K_(1,3), has a bisection of weight at least 11/15 of its total nonnegative edge weight. The graph may be disconnected and may contain claw components, provided it is not itself K_(1,3). 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 11/15. The result also holds for loopless triangle-free subcubic multigraphs, counting multiplicities in the degree and excluding the entire claw.


See also

Cut, Maxcut, Set Partition

Explore with Wolfram|Alpha

References

Lee, C.; Loh, P.-S.; and Sudakov, B. "Bisections of Graphs." J. Combin. Th. Ser. B 103, 599-629, 2013. https://doi.org/10.1016/j.jctb.2013.06.002.Gerke, S.; Gutin, G.; Yeo, A.; and Zhou, Y. "Sharp Lower Bounds for Weighted Bisections of Graphs with Bounded Maximum Degree." 17 Nov 2026. https://arxiv.org/abs/2611.22760v1.Wu, S. and Zeng, Q. "Weighted Bisections of Triangle-free Subcubic Graphs." 15 Nov 2026. https://arxiv.org/abs/2611.19881v1.

Cite this as:

Weisstein, Eric W. "Graph Bisection." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphBisection.html

Subject classifications