Remark on Turán's Theorem 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.
 A: 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.
