Judicious partitions of graphs (Q1314903)

Let \(G\) be a graph and let \(e(G[V_ i])\) be the number of edges of the subgraph of \(G\) induced by \(V_ i\). Set \(p_ k(G) = \min (\max_{1 \leq i \leq k} e(G[V_ i]))\) where the minimum is taken over all partitions \(V_ 1, \dots, V_ k\) of the vertex set of \(G\) into \(k\) sets. It is proved that \(p_ k(G) \leq e(G) / {k+1 \choose 2}\). A better bound is given for graphs with many edges.