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:V(G)\to {ℝ}_{+}$ 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\le c^{*}$ if and only if $W(c)\le 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\ge 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\ge 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)\ge \sum _{vw\in E(G)}c(w).$$ (*)

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

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^{*}$,

$W(c^{*})$ $={\displaystyle \sum _{uw\in E(G)}}{c}^{*}(u)\cdot c^{*}(w)+{\displaystyle \sum _{vw\in E(G)}}{c}^{*}(v)\cdot c^{*}(w)+{\displaystyle \sum _{wz\in E(G)}}{c}^{*}(w)\cdot c^{*}(z)$

$={\displaystyle \sum _{uw\in E(G)}}[c(u)+c(v)]\cdot c(w)+0+{\displaystyle \sum _{wz\in E(G)}}c(w)\cdot c(z)$

$={\displaystyle \sum _{uw\in E(G)}}c(u)\cdot c(w)+{\displaystyle \sum _{vw}}c(v)\cdot c(w)+{\displaystyle \sum _{wz\in E(G)}}c(w)\cdot c(z)$

$=W(c).$

Thus $c^{*}\ge 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)\ge W(c_0)=\frac{|E(G)|}{{|V(G)|}^2},$$

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

Title	proof of Mantel’s theorem
Canonical name	ProofOfMantelsTheorem
Date of creation	2013-03-22 13:03:04
Last modified on	2013-03-22 13:03:04
Owner	mps (409)
Last modified by	mps (409)
Numerical id	6
Author	mps (409)
Entry type	Proof
Classification	msc 05C75
Classification	msc 05C69