# Turán's graph $T_{k, n}$ has more edges than any other $k$-partite graph with $n$ vertices.

In Bondy and Murty's Graph Theory, exercise $1.1.11$ defines something called Turán's graph $T_{k, n}$, as a complete, $k$-partite graph where all parts are of size $\lceil \frac{n}{k} \rceil$, or $\lfloor \frac{n}{k} \rfloor$. I want to show the following:

$T_{k, n}$ has more edges than any other complete $k$-partite graph with $n$ vertices.

I know from part $a)$ that in this case, the number of edges of a complete, $k$-partite graph is $\frac{1}{2} \sum_{i=1}^{k} a_{i}(n-a_{i})$, where $a_{i}$ are the sizes of the parts $A_{i}$. So I want to prove that if $n=kq+r$, $0 \leq r < n$, $q = \lfloor \frac{n}{k} \rfloor$, $a_{1}= \space ... \space =a_{r}=q+1$, $a_{r+1}= \space ... \space =a_{k} = q$, and $b_{i}$ any other sequence of $k$ positive numbers such that $\sum_{i=1}^{k} b_{i} = n$, that $$\sum_{i=1}^{k} a_{i}(n-a_{i}) \geq \sum_{i=1}^{k} b_{i}(n-b_{i}).$$ Is there an elementary-inequality way of proving this? I've tried Lagrange multipliers, but it seems like overkill, and it'd require further discussion since $a_{i}$ can only be positive integers, not real numbers.

• See Jensen’s Inequality. – Bob Krueger Nov 28 '17 at 18:01
• @BobKrueger Jensen's inequality, and convexity in general, certainly underlie what's going on, but naively applying it still doesn't deal with the case where $\frac nk$ is not an integer. (It merely gives us an easy way to prove an upper bound of $n(n - \frac nk)$ on the number of edges, but this is not quite tight when $k$ does not divide $n$.) – Misha Lavrov Nov 28 '17 at 18:48

The only real way avoid "further discussion" to deal with the issue of integers is what they call a smoothing argument.

First, if we have $b_i - b_j\ge 2$ for any $i,j$, then replacing them by $b_i' = b_i - 1$ and $b_j' = b_j + 1$ while leaving all terms the same will increase the sum: $$\sum_{i=1}^k b_i (n-b_i) < \sum_{i=1}^k b_i' (n-b_i').$$ This is easy to check, since only two terms of the sum change, and the total change is by $2(b_i - b_j - 1) > 0$.

Second, if some of the parts do not have size $\lfloor \frac nk \rfloor$ or $\lceil \frac nk \rceil$, then the largest part and the smallest part must differ in size by at least $2$:

• The average size is $\frac nk$, so the largest part must have size at least $\lceil \frac nk \rceil$ and the smallest part must have size at most $\lfloor \frac nk \rfloor$.
• If $\frac nk$ is not an integer, then this already guarantees a difference of $2$ unless the largest part has size exactly $\lceil \frac nk \rceil$ and the smallest part has size exactly $\lfloor \frac nk \rfloor$.
• If $\frac nk$ is an integer, then any part of size less than $\frac nk$ forces a part of size greater than $\frac nk$, and vice versa.

In such a case, the inequality above shows that such a $k$-partite graph cannot have the maximum number of edges. This leaves the Turán graph as the only possibility.

• Hm, this discussion occured to me, but I didn't think it would be this simple. Thank you! – Matija Sreckovic Nov 28 '17 at 19:01