Sharp lower bounds for bisections of graphs with bounded maximum degree

Source abstract

A bisection of a graph is a partition of its vertex set into two parts whose sizes differ by at most one. We prove that every graph with $m$ edges and maximum degree at most $k$ has a bisection of size at least $\frac{k+1}{2k}m$ when $k$ is odd, and at least $\frac{k+2}{2(k+1)}m$ when $k$ is even. Both bounds are sharp, with equality for complete graphs. This establishes the unweighted case of the bisection conjecture of Gerke, Gutin, Yeo and Zhou (arXiv 2024), removes the additive error from the corresponding bounds of Lee, Loh and Sudakov (JCTB 2013), and extends the odd-degree regular case proved by Bollobás and Scott (JGT 2004) to arbitrary graphs of bounded maximum degree. The proof combines the matching-and-pairing method with the Gallai--Edmonds decomposition. Hall's theorem controls the number of uncovered factor-critical components whose internal degrees are all even. A boundary-edge count bounds this obstruction by the total degree deficiency, while the remaining uncovered components supply the required pairing gain.