Remark on Turán's Theorem

Question

In my notes, Turán's Theorem is stated as follows:

Theorem: Let $G$ be a graph on $n$ vertices. Then $e(G) > e(T_{r-1}(n)) \implies G \supset K_r $.

There are then several remarks on the theorem, one of which I don't follow:

Remark: If we knew $G$ was $(r-1)$-partite, then we are done by some kind of AM-GM inequality. But there's no reason why $G$ should be $(r-1)$-partite: e.g. $C_5 $ is $K_3$-free, but not bipartite.

Firstly, am I correct in saying that the reasoning for the above is that if we knew $G$ was $(r-1)$-partite, then it couldn't contain a $K_r$, and so we'd aim to prove (using "some kind of AM-GM inequality") that $e(G) < e(T_{r-1}(n))$? My main problem is that I don't quite know what "some kind of AM-GM inequality" actually means. Could someone show me explicitly what is meant here?

My thoughts: I can sort of see what's going on: we aim to show that the largest number of edges an $(r-1)$-partite graph can have without containing $K_r$ occurs when the vertex classes are as equal in size as possible (as per the definition of Turán's graph). I don't see how AM-GM comes into it though.

Thank you.

Answer 1

Assume that $G$ is $(r-1)$-partite. (You are right in observing that $G$ does not contain $K_r$ as a subgraph.) Let the sizes of the $(r-1)$ vertex classes be $n_1, n_2, \ldots, n_{r-1}$. Then the number of edges is maximised when $G$ is a complete $(r-1)$-partite graph on these vertices.

The number of edges in a complete $(r-1)$-partite graph on these vertices is $$ \frac{n(n-1)}{2} - \sum_{i=1}^{r-1} \frac{n_i (n_i-1)}{2}. $$ (Of the $\frac{n(n-1)}{2}$ edges in a complete graph, we should remove the edges lying inside each of the $(r-1)$ parts.) This can be simplified to $$ \frac{n^2}{2} - \sum_{i=1}^{r-1} \frac{n_i^2}{2} $$ since $\sum_i n_i = n$. Maximizing this quantity is equivalent to minimizing $$ \sum_{i=1}^{r-1} n_i^2 $$ subject to the condition $\sum_i n_i = n$. By Cauchy-Schwarz, we have $$ \begin{align*} (r-1) \cdot \left( \sum_{i=1}^{r-1} n_i^2 \right) &\geqslant \left( \sum_{i=1}^{r-1} n_i \right)^2 \\ &= n^2, \end{align*} $$ with equality when all the $r-1$ numbers $n_1, \ldots, n_{r-1}$ are equal. Since these numbers are integral, we want them to be as equal to each other as possible.