Exact bounds for judicious partitions of graphs (Q1977429)

Extending a result of \textit{C. S. Edwards} [Can. J. Math. 25, 475-485 (1973; Zbl 0229.05129) and Recent Adv. Graph Theory, Proc. Symp. Prague 1974, 167-181 (1975; Zbl 0326.05115)] it is shown that a graph with \(m\) edges has a bipartition with at least \(t=m/2 + (\sqrt{8m+1}-1)/8\) edges and at most \(t/2\) inner edges in either class. This result is sharp for complete graphs of odd order which are the only extremal graphs with no isolated vertices. Similar results are proved for the case of more classes.