# alternate proof of Mantel’s theorem

Let $G$ be a triangle-free graph of order $n$. For each edge $xy$ of $G$ we consider the neighbourhoods (http://planetmath.org/NeighborhoodOfAVertex) $\mathrm{\Gamma}(x)$ and $\mathrm{\Gamma}(y)$ of $G$. Since $G$ is triangle-free, these are disjoint.

This is only possible if the sum of the degrees of $x$ and $y$ is less than or equal to $n$. So for each edge $xy$ we get the inequality

$$\delta (x)+\delta (y)\le n$$ |

Summing these inequalities for all edges of $G$ gives us

$${\mathrm{\Sigma}}_{x\in V(G)}{(\delta (x))}^{2}\le n|E(G)|$$ |

(The left hand side is a sum of $\delta (x)$ where each edge incident with $x$ contributes one term and their are $\delta (x)$ such edges.)

Since ${\mathrm{\Sigma}}_{x\in V(G)}\delta (x)=2|E(G)|$, we get $4{|E(G)|}^{2}={({\mathrm{\Sigma}}_{x\in V(G)}\delta (x))}^{2}$ and applying the Cauchy-Schwarz inequality gives $4{|E(G)|}^{2}\le n{\mathrm{\Sigma}}_{x\in V(G)}{(\delta (x))}^{2}\le {n}^{2}|E(G)|$.

So we conclude that for a triangle-free graph $G$,

$$|E(G)|\le \frac{{n}^{2}}{4}$$ |

Title | alternate proof of Mantel’s theorem |
---|---|

Canonical name | AlternateProofOfMantelsTheorem |

Date of creation | 2013-03-22 17:56:35 |

Last modified on | 2013-03-22 17:56:35 |

Owner | lieven (1075) |

Last modified by | lieven (1075) |

Numerical id | 5 |

Author | lieven (1075) |

Entry type | Proof |

Classification | msc 05C75 |

Classification | msc 05C69 |