Number of edges in Turán graph

Question

I am trying to prove that the number of edges in the Turán graph $T^r(n)$ (that is, the complete $r$-partite graph on $n$ vertices whose partition sets differ in size by at most 1) satisfy the inequality $$|E(T^r(n))| \geq (1-\frac{1}{r} - o(1))\frac{n^2}{2},$$ and I'm stuck. Any help is much appreciated.

Answer 1

I recall that the number $|E(T^r(n))|$ can be easily calculated exactly. Let $n=qr+s$, where $0\le s<r$. Then the $r$-partition of the vertex set of the graph $T^r(n)$ has $s$ parts of size $q+1$ and $r-s$ parts of size $q$. Thus

$$|E(T^r(n))|={s \choose 2}(q+1)^2+s(r-s)q(q+1)+ {r-s \choose 2}q^2=\frac 12\left( q^2r^2-q^2r+2sqr-2sq+s^2-s\right)=\frac 12\left(n^2-q(n+s)-s\right)= \frac 12\left(n^2-\frac {(n-s)(n+s)}{r}-s\right)= \frac 12\left(n^2-\frac {(n^2-s^2)}{r}-s\right).$$

Thus $$\left|E(T^r(n))|-\frac{n^2}{2}\left(1-\frac 1r\right)\right|=\frac{s(r-s)}{2r}\le \left(\frac {s+r-s}2\right)^2\frac 1{2r}=\frac r8.$$