Mantel's theorem

Statement

Let $G$ be a finite simple graph with $n$ vertices and no cycle of length $3$. Then $G$ has at most $\lfloor n^2/4 \rfloor$ edges.

Remarks

The bound is sharp: the complete bipartite graph $K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}$ has no triangle and has $\lfloor n^2/4 \rfloor$ edges. The theorem is the case $r = 2$ of Turán's theorem.

History

Willem Mantel stated the theorem in 1907.

Explanations

L1 human

A graph on $n$ vertices without a triangle can have at most about a quarter of $n^2$ edges. Split the vertices into two equal halves and join each pair across: this graph reaches the bound.