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