Turán's theorem, triangle-free case (Mantel's theorem)

We induct on $n$. For $n \le 2$ the claim is trivial since $\lfloor n^2/4 \rfloor \ge 0$ and any graph on at most 2 vertices has at most 1 edge.

Suppose the statement holds for all triangle-free graphs on fewer than $n$ vertices, and let $G$ be triangle-free on $n$ vertices. If $G$ has no edges the bound holds trivially, so assume $G$ has an edge $uv$. Since $G$ is triangle-free, $u$ and $v$ have no common neighbor, i.e. $N(u) \cap N(v) = \varnothing$.

Because $N(u)$ and $N(v)$ are disjoint subsets of the $n$-vertex set, $\deg(u)+\deg(v) = |N(u)|+|N(v)| = |N(u) \cup N(v)| \le n$.

Remove $u$ and $v$ from $G$ to get a triangle-free graph $G'$ on $n-2$ vertices. Every edge of $G$ is either the edge $uv$, an edge from $u$ or $v$ to the rest, or an edge of $G'$; counting carefully, $e(G) = e(G') + \deg(u) + \deg(v) - 1$ (the $-1$ corrects for the edge $uv$ being counted once inside $\deg(u)+\deg(v)$ but it is not an edge of $G'$).

By the induction hypothesis $e(G') \le \lfloor (n-2)^2/4 \rfloor$, so $e(G) \le \lfloor (n-2)^2/4 \rfloor + n - 1$. A direct computation gives $(n-2)^2/4 + n - 1 = n^2/4 - n + 1 + n - 1 = n^2/4$, and checking the even/odd cases of $n$ separately shows $\lfloor (n-2)^2/4 \rfloor + n - 1 \le \lfloor n^2/4 \rfloor$ exactly. Hence $e(G) \le \lfloor n^2/4 \rfloor$, completing the induction.

For the extremal case, the complete bipartite graph with parts of size $\lfloor n/2 \rfloor$ and $\lceil n/2 \rceil$ has no triangle (any triangle would need an edge inside one part, but there are none) and has exactly $\lfloor n/2 \rfloor \cdot \lceil n/2 \rceil = \lfloor n^2/4 \rfloor$ edges, so the bound is tight.