= Mantel theorem
{c}
{title2=$\operatorname{ex}(n,K_3)=\lfloor n^2/4\rfloor$}
The <complete bipartite graph> $K_{3,3}$ has <vertex sets> $A=\{a_1,a_2,a_3\}$ and $B=\{b_1,b_2,b_3\}$, with every <edge> between $A$ and $B$ and none inside either part. Its six <vertices> support $3\cdot3=9$ <edges> and no <triangles in a graph>: among any three <vertices>, two belong to the same <independent set> and have no joining <edge>.
\Image[/mantel-bipartite-bound-and-extra-edge.png]
{title=The sharp nine-<edge> <triangle-free graph> $K_{3,3}$ and the three <triangles in a graph> created by adding $a_1a_2$}
Add the single <edge> $a_1a_2$. Each $b_j$ is a <common neighbour> of its endpoints, producing the <triangle in a graph> $a_1a_2b_j$. These are exactly the three new <triangles in a graph>, because every <triangle in a graph> must use the only <edge> inside a part. The new count is ten <edges>; nine was the last possible count without a <triangle in a graph> on six <vertices>.
In general, every <simple graph> with a <finite set> of $n\geq0$ <vertices> that is <triangle-free> has at most
$$
m\leq\left\lfloor\frac{n^2}{4}\right\rfloor
$$
<edges>. This is the $r=2$ case of <Turán's theorem>, with forbidden <clique> $K_3$. Equality holds exactly for the balanced <complete bipartite graph> $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$, up to <graph isomorphism>; empty parts are allowed for $n<2$.<Graph Theory by Reinhard Diestel>[third electronic edition (2005), §7.1, printed p. 165, Theorem 7.1.1 and the definition of Turán graphs, specialized to the forbidden graph K3]{ref}
The <floor function> gives the exact <integer> bound. Splitting $n$ <vertices> into two <independent sets> of sizes $a$ and $n-a$, and putting in every cross <edge>, gives
$$
a(n-a)=\frac{n^2}{4}-\left(a-\frac n2\right)^2.
$$
The count is largest when $a$ is an <integer> nearest $n/2$. For $n=2k$ it is $k^2$; for $n=2k+1$ it is $k(k+1)$. Both equal $\lfloor n^2/4\rfloor$. This proves attainability for every $n$, including the empty <graph>.
A short proof of the upper bound uses <degrees of vertices>. In a <triangle-free graph>, the endpoints $u,v$ of an <edge> have disjoint <vertex neighbourhoods>: a <common neighbour> would complete a <triangle in a graph>. Thus $d(u)+d(v)\leq n$. Summing over <edges> counts $d(v)$ once for each of the $d(v)$ <edges> incident to $v$, giving
$$
\sum_{v\in V}d(v)^2=\sum_{uv\in E}(d(u)+d(v))\leq nm.
$$
For $n>0$, the <Cauchy-Schwarz inequality> and <handshaking lemma> yield
$$
4m^2=\left(\sum_{v\in V}d(v)\right)^2\leq n\sum_{v\in V}d(v)^2\leq n^2m.
$$
If $m>0$, division gives $m\leq n^2/4$; $m=0$ is immediate. Since $m$ is an <integer>, apply the <floor function>. The case $n=0$ is immediate too. This proves the bound; the full equality characterization follows from <Turán's theorem>.
The useful reversal is that more than $\lfloor n^2/4\rfloor$ <edges> force a <triangle in a graph>, whatever their placement. A global count certifies a local pattern. The extremizer is <bipartite>, but a <triangle-free graph> need not be <bipartite>: a five-<vertex> <graph cycle> has five <edges>, below the bound of six. Historically, <Willem Mantel> posed the triangle-exclusion question in 1907.<Wie weet wie Willem Wijthoff was? by Robbert Fokkink>[Robbert Fokkink, Wie weet wie Willem Wijthoff was?, Nieuw Archief voor Wiskunde 5/17(4), December 2016, printed p. 279, Wythoffs bewijs van de stelling van Mantel: attribution of problem 28 in 1907]{ref}
Back to article page
