# What is the maximum number of edges in a complete multipartite graph?

The concept of complete bipartite graphs can be generalized to define the complete multipartite graph $K(r_1,r_2,...,r_k)$. It consists of $k$ sets of vertices each with cardinality $r_i$ for $i$ in $\{1,2,\ldots,k\}$ where all possible "interest" edges are present but no "intraset" edges are present.

For bipartite graphs I have Mathematica code: Table[Floor[n/2] Ceiling[n/2], {n, 0, 10}] {0, 0, 1, 2, 4, 6, 9, 12, 16, 20, 25}

for tripartite graphs I have:

f[n_] := Which[Mod[n, 3] == 0, 3 (n/3)^2, Mod[n, 3] == 1, Floor[n/3]^2 + 2 Ceiling[n/3] Floor[n/3], Mod[n, 3] == 2, Ceiling[n/3]^2 + 2 Ceiling[n/3] Floor[n/3]]; Table[f[n], {n, 0, 10}] {0, 0, 1, 3, 5, 8, 12, 16, 21, 27, 33}

In neither case am I convinced that I am correct. It just seems intuitive that the sets must be (as nearly as possible) the same size. How can I generalize for larger k?

This question is an exercise in "Combinatorics and Graph Theory" Harris,Herst,Mossinghoff. page 16.

I read and understood the solution given by Kaya in another post: $n^2\frac{k-1}{2k}$ but this is only true when $n$ is a multiple of $k$. I want to be able to write a code in Mathematica for any $k$ and any $n$.

-

Forget the coding, we can solve it explicitly!

Let $N=r_1+r_2+...r_k$ be the number of vertices in the graph. Now, for each $r_i$-partite set, we are blocked from making $r_i\choose 2$ edges. However, this is the only restriction on edges, so the number of edges in a complete multipartite graph $K(r_1,\ldots, r_k)$ is just

$|E|={N\choose2}-\sum\limits_{i=1}^k{r_i\choose 2}$

Hence, if you want to $\textit{maximize}$ the number of edges for a given $k$, you can just choose each sets such that $r_i=1\forall i$, which gives you the maximum $N\choose 2$.

If on the other hand you want to $\textit{minimize}$ the number of edges for a given $k$, we can use a little switching argument to show that the minimum occurs when all the $r_i$s are as near to $\frac{N}{k}$ as possible.

Here's the switching argument: Let $r=\lfloor \frac{N}{k}\rfloor$. Assume for the sake of contradiction that there exist $r_i$ and $r_j$ such that $r_j-r_i\geq 2$ in a $k$-partite graph $M$ with a minimum number of edges. Let $|M|$ denote the number of edges in $M$. Consider now $M'$ which we create from $M$ by taking a vertex $x$ in the $r_j$ set and adding it to the $r_j$ set. This switch adds $r_j-1$ edges and gets rid of $r_i$ edges. Hence $|M'|=|M|+r_j-1-r_i\leq |M|-1$ Hence we have a contradiction. This means that the sizes of two sets cannot differ in size by more than $1$. Hence a $k$-partite graph of minimum size must must have $r_i\in\{r,r+1\}$ for all $i\in\{1,2,\ldots,k\}$. In particular, if $N\equiv h \mod k$. Then the minimum number of edges of a $k$-partite graph is

$|E|={N\choose 2}-h{r+1\choose 2}-(k-h){r \choose2}$.

-
Yes, thank you. I see now what I really want to know is how to compute the minimum number of edges in a complete k-partite graph. –  Geoffrey Critzer May 24 '14 at 18:53
Great, yeah, that's the more interesting question. I'll update my answer to include the full minimization argument. –  Peter Woolfitt May 24 '14 at 18:55
Your last sentence: "In particular, if N is congruent to h mod r. I think you mean if N is congruent to h mod k. –  Geoffrey Critzer May 25 '14 at 18:20
The second N in your formula should be k not N. –  Geoffrey Critzer May 25 '14 at 18:22
Transpose[ Table[nn = 10; PadLeft[Table[ Binomial[n, 2] - Mod[n, k] Binomial[Floor[n/k] + 1, 2] - (k - Mod[n, k]) Binomial[Floor[n/k], 2], {n, k, nn}], nn + 1], {k, 1, 10}]] // Grid –  Geoffrey Critzer May 25 '14 at 18:28