# 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 {\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\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 {\mathbb{R}}_{+}$ by

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

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 |