Show that the size of the Turan graph $T_r(n)$ is at least $(1 - \frac{1}{r}) \binom{n}{2}$. A Turan graph $T_r(n)$ is defined as the complete $r$-partite graph of order $n$ such that the number of vertices in each of the $r$ classes is either $\lfloor \frac{n}{r}\rfloor$ or $\lceil \frac{n}{r} \rceil$. For fixed $n$ and $r$, $T_r(n)$ is unique up-to isomorphism. The size of $T_r(n)$ can be simply counted as: $\binom{n}{2} - (n \bmod r) \binom{\lceil \frac{n}{r} \rceil}{2} - (r - (n\bmod r))\binom{\lfloor \frac{n}{r}\rfloor}{2}$.
Here is what I have: assume $n = kr + s,\ 0 \leq s \leq r-1$. Note that at least one class must have exactly $\lfloor \frac{n}{r} \rfloor$ vertices. Then, $\binom{n}{2} - (n \bmod r) \binom{\lceil \frac{n}{r} \rceil}{2} - (r - (n\bmod r))\binom{\lfloor \frac{n}{r}\rfloor}{2}$
$\geq$ $\binom{n}{2} -(r-1) \binom{\lceil \frac{n}{r} \rceil}{2} - \binom{\lfloor \frac{n}{r} \rfloor}{2}$
$=\binom{n}{2} - (r-1) \binom{k+1}{2} - \binom{k}{2}$
$= \frac{n(n-1)}{2} - \frac{(r-1)k(k+1)}{2} - \frac{k(k-1)}{2}$
$= \frac{n(n-1)}{2} - \frac{rk(k+1) - k(k+1)}{2} - \frac{k(k-1)}{2}$
$\geq \frac{n(n-1)}{2} - \frac{n(k+1) - k(k+1)}{2} - \frac{k(k-1)}{2}$
$= \frac{n(n-1)-n(k+1) + k(k+1) - k(k-1)}{2}$
$= \frac{n(n-1)-n(k+1) + 2k}{2}$
$= \binom{n}{2}(1 - \frac{k+1}{n-1} + \frac{2k}{n(n-1)})$.
But clearly, $(1 - \frac{k+1}{n-1} + \frac{2k}{n(n-1)})$ may be smaller than $1 - \frac{1}{r}$, as seen by taking $n=31$ and $r=5$.

Let $e$ be the number of edges and $a$ the average degree of a vertex. We want to show that
$$e\ge\left(1-\frac1r\right)\binom n2.$$
Since $e=\frac{na}2$ and $\binom n2=\frac{n(n-1)}2$, that's the same as showing
$$\frac{na}2\ge\left(1-\frac1r\right)\frac{n(n-1)}2,$$
that is, we have to show that
$$a\ge\left(1-\frac1r\right)(n-1).$$
Since the degree of each vertex is either $n-\lfloor\frac nr\rfloor$ or $n-\lceil\frac nr\rceil$, and since $\lceil\frac nr\rceil\le\frac{n+r-1}r=1+\frac{n-1}r$, we have
$$a\ge n-\left\lceil\frac nr\right\rceil\ge n-\left(1+\frac{n-1}r\right)=\left(1-\frac1r\right)(n-1),$$
Q.E.D.
