A complete $k$-partite graph is a graph with disjoint sets of nodes where there is no edges between the nodes in same set, and there is an edge between any node and other nodes in the other subsets.
The subsets are $X_1,\dots,X_p$, and the number of nodes is $N$. What is the maximum number of edges that can be in this complete $k$-partite graph?
1 Answer
Divide up the vertices into your $k$ sets of sizes $a_{1}+...+a_{k}=N$ and consider a vertex in the first set. It has $a_{2}+...+a_{k}$ possible edges to make, therefore the contribution of the first disjoint set is $a_{1}(a_{2}+...+a_{k})$ edges. Since this first set has made as many edges as it may, we then 'ignore' these $a_{1}$ vertices and proceed in a similar fashion with the remaining disjoint sets. The total will amount to $a_{1}(a_{2}+...+a_{k})+a_{2}(a_{3}+...+a_{k})+...+a_{k-1}a_{k}$ edges.
If your sets are all of size $n/k$ then the total number of edges should at max be $\frac{n^{2}}{k^{2}}[(k-1)+(k-2)+...+1]=\frac{n^{2}(k-1)}{2k}$.
