Turán's theorem

Idea. The neighbours of a vertex of largest degree form a graph with no $K_r$; the outside vertices have degree at most $\Delta$.

Base case $r=1$. No $K_2$ means no edge, and the bound is $0$ ✓.

Induction step. Let $r\ge2$ and assume the statement for $r-1$. Let $v$ have maximum degree $\Delta$, let $A=N(v)$ ($|A|=\Delta$) and $B=V\setminus A$ ($|B|=n-\Delta$).
- The graph induced on $A$ contains no $K_r$. By induction, $e(A)\le\left(1-\frac1{r-1}\right)\frac{\Delta^2}2$.
- Every edge not inside $A$ has at least one endpoint in $B$. Therefore the number of such edges is at most $\sum_{u\in B}\deg u\le(n-\Delta)\Delta$.

Adding,
$$e(G)\le\frac{r-2}{r-1}\cdot\frac{\Delta^2}2+(n-\Delta)\Delta=n\Delta-\frac r{2(r-1)}\Delta^2.$$

Maximising over $\Delta$. The right side is a concave quadratic in $\Delta$, maximal at $\Delta=\frac{(r-1)n}r$, where its value is
$$\frac{(r-1)n^2}{2r}=\left(1-\frac1r\right)\frac{n^2}2.$$
So $e(G)\le\left(1-\frac1r\right)\frac{n^2}2$ ∎.

Sharpness. Splitting the vertices into $r$ equal groups and joining vertices of different groups gives a $K_{r+1}$-free graph with this many edges when $r\mid n$. For $r=2$ this is Mantel's theorem.

Lesson. Take a vertex of maximum degree, bound what happens inside and outside its neighbourhood, and let induction on the clique size do the rest.