# proof of Mantel’s theorem

Let $G$ be a triangle-free graph. We may assume that $G$ has at least three vertices and at least one edge; otherwise, there is nothing to prove. Consider the set $P$ of all functions $c\colon V(G)\to\mathbb{R}_{+}$ such that $\sum_{v\in V(G)}c(v)=1$. Define the total weight $W(c)$ of such a function by

 $W(c)=\sum_{uv\in E(G)}c(u)\cdot c(v).$

By declaring that $c\leq c^{*}$ if and only if $W(c)\leq W(c^{*})$ we make $P$ into a poset.

Consider the function $c_{0}\in P$ which takes the constant value $\frac{1}{|V(G)|}$ on each vertex. The total weight of this function is

 $W(c_{0})=\sum_{uv\in E(G)}\frac{1}{|V(G)|}\cdot\frac{1}{|V(G)|}=\frac{|E(G)|}{% |V(G)|^{2}},$

which is positive because $G$ has an edge. So if $c\geq c_{0}$ in $P$, then $c$ has support on an induced subgraph of $G$ with at least one edge.

We claim that a maximal element of $P$ above $c_{0}$ is supported on a copy of $K_{2}$ inside $G$. To see this, suppose $c\geq c_{0}$ in $P$. If $c$ has support on a subgraph larger than $K_{2}$, then there are nonadjacent vertices $u$ and $v$ such that $c(u)$ and $c(v)$ are both positive. Without loss of generality, suppose that

 $\sum_{uw\in E(G)}c(w)\geq\sum_{vw\in E(G)}c(w).{}$ (*)

Now we push the function off $v$. To do this, define a function $c^{*}\colon V(G)\to\mathbb{R}_{+}$ by

 $c^{*}(w)=\begin{cases}c(u)+c(v)&w=u\\ 0&w=v\\ c(w)&\text{otherwise.}\end{cases}$

Observe that $\sum_{w\in V(G)}c^{*}(w)=1$, so $c^{*}$ is still in the poset $P$. Furthermore, by inequality (*) and the definition of $c^{*}$,

 $\displaystyle W(c^{*})$ $\displaystyle=\sum_{uw\in E(G)}c^{*}(u)\cdot c^{*}(w)+\sum_{vw\in E(G)}c^{*}(v% )\cdot c^{*}(w)+\sum_{wz\in E(G)}c^{*}(w)\cdot c^{*}(z)$ $\displaystyle=\sum_{uw\in E(G)}[c(u)+c(v)]\cdot c(w)+0+\sum_{wz\in E(G)}c(w)% \cdot c(z)$ $\displaystyle=\sum_{uw\in E(G)}c(u)\cdot c(w)+\sum_{vw}c(v)\cdot c(w)+\sum_{wz% \in E(G)}c(w)\cdot c(z)$ $\displaystyle=W(c).$

Thus $c^{*}\geq c$ in $G$ and is supported on one less vertex than $c$ is. So let $c$ be a maximal element of $P$ above $c_{0}$. We have just seen that $c$ must be supported on adjacent vertices $u$ and $v$. The weight $W(c)$ is just $c(u)\cdot c(v)$; since $c(u)+c(v)=1$ and $c$ has maximal weight, it must be that $c(u)=c(v)=\frac{1}{2}$. Hence

 $\frac{1}{4}=W(c)\geq W(c_{0})=\frac{|E(G)|}{|V(G)|^{2}},$

which gives us the desired inequality: $|E(G)|\leq\frac{|V(G)|^{2}}{4}$.

Title proof of Mantel’s theorem ProofOfMantelsTheorem 2013-03-22 13:03:04 2013-03-22 13:03:04 mps (409) mps (409) 6 mps (409) Proof msc 05C75 msc 05C69