Exact bounds for judicious partitions of graphs
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.
scientific article; zbMATH DE number 1446785