Question

If G is a k-partite graph of order n with partite sets of sizes a1, a2,.....an, then

Answer 1

\[\left| E \right| \le 1/2 \sum_{i=1}^{k} ai (n-ai)\]

A complete k partite graph is one such that any two vertices are adjacent. Then the inequality, becomes an equality for complete k partites. Assuming K divdes n evenly, find the choice of a1, a2, ....ak, that maximizes the \[\left| E \right|\]