= Solution
We prove the <Quadratic Turan edge bound> by induction. The case $r=1$ is immediate. For $r\geq2$, if $G$ contains no $K_r$, the induction hypothesis for $r-1$ gives the stronger bound. Otherwise choose a copy $S$ of $K_r$. Every vertex outside $S$ has at most $r-1$ neighbours in $S$, since one adjacent to all of $S$ would complete a $K_{r+1}$. Thus the number of edges having at least one endpoint in $S$ is at most
$$
\binom r2+(n-r)(r-1)
=(r-1)\left(n-\frac r2\right).
$$
The graph $G-S$ is still $K_{r+1}$-free, so induction on the number of vertices gives
$$
\begin{aligned}
e(G)
&\leq
\left(1-\frac1r\right)\frac{(n-r)^2}{2}
+(r-1)\left(n-\frac r2\right)\\
&=\boxed{\left(1-\frac1r\right)\frac{n^2}{2}}.
\end{aligned}
$$
This proves the stated form of <Turan theorem>.
Back to article page
