Mantel's theorem: prove that a triangle-free graph on $n$ vertices has at most $\left\lfloor n^2/4 \right\rfloor$ edges, and exhibit a graph attaining the bound.
- 1
Let $G$ be triangle-free with vertex set $V$, $|V| = n$, and $m = |E|$ edges. Key local fact: for any edge $uv$, the endpoints $u$ and $v$ have no common neighbor (a common neighbor $w$ would make triangle $uvw$), and every neighbor of $u$ or $v$ is one of the $n$ vertices, so $\deg(u) + \deg(v) \le n$.
- 2
Sum this over all edges and double count: $\sum_{uv \in E}\bigl(\deg(u) + \deg(v)\bigr) \le mn$. The left side counts, for each vertex $v$, the quantity $\deg(v)$ once per incident edge — that is $\deg(v)$ times — so it equals $\sum_{v \in V} \deg(v)^2$. Hence $\sum_{v} \deg(v)^2 \le mn$.
- 3
By Cauchy–Schwarz, $\sum_{v} \deg(v)^2 \ge \dfrac{\left(\sum_v \deg(v)\right)^2}{n} = \dfrac{(2m)^2}{n} = \dfrac{4m^2}{n}$, using the Handshake Lemma $\sum_v \deg(v) = 2m$. Chaining, $\dfrac{4m^2}{n} \le mn$, so $m \le \dfrac{n^2}{4}$; as $m$ is an integer, $m \le \left\lfloor n^2/4 \right\rfloor$.
- 4
The bound is sharp: the complete bipartite graph $K_{\lfloor n/2\rfloor,\,\lceil n/2\rceil}$ is triangle-free (any triangle would need two vertices on the same side, which are nonadjacent) and has exactly $\lfloor n/2\rfloor\cdot\lceil n/2\rceil = \left\lfloor n^2/4 \right\rfloor$ edges.
Answer:A triangle-free graph on $n$ vertices has at most $\left\lfloor n^2/4 \right\rfloor$ edges, attained by $K_{\lfloor n/2\rfloor,\,\lceil n/2\rceil}$.