Mantel's theorem

Mantel’s theorem is a special case of Turan theorem.

Theorem The maximum size of a graph of order $n$ that is triangle-free (it doesn’t contain $K_3$) is

$$m\le \frac{n^2}{4}$$

Proof Pick any edge in $xy\in E$ (it can’t be empty since it has maximum size). Since it is triangle-free, the neighbourhoods of $x$ and $y$ are disjoint so that

$$d(x)-1+d(y)-1\le n-2⟹d(x)+d(y)\le n$$

summing over all edges

$$\sum _{xy\in E}d(x)+d(y)\le n|E|$$

every therm $d(x)$ in the sum appears $d(x)$ times, so

$$\sum _{x\in V}d(x{)}^2\le n|E|$$

we can use Cauchy-Schwarz inequality to lower boud the first term (or use the fact what the variance is always non-negative)

$${\left(\sum _{x\in V}d(x)\right)}^2\le n^2|E|$$

using the Handshake Lemma

$$4|E|\le n^2⟹|E|\le \frac{n^2}{4}\square$$