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) $\Gamma(x)$ and $\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)\leq n$

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

 $\Sigma_{x\in V(G)}(\delta(x))^{2}\leq 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 $\Sigma_{x\in V(G)}\delta(x)=2|E(G)|$, we get $4|E(G)|^{2}=(\Sigma_{x\in V(G)}\delta(x))^{2}$ and applying the Cauchy-Schwarz inequality gives $4|E(G)|^{2}\leq n\Sigma_{x\in V(G)}(\delta(x))^{2}\leq n^{2}|E(G)|$.

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

 $|E(G)|\leq\frac{n^{2}}{4}$
Title alternate proof of Mantel’s theorem AlternateProofOfMantelsTheorem 2013-03-22 17:56:35 2013-03-22 17:56:35 lieven (1075) lieven (1075) 5 lieven (1075) Proof msc 05C75 msc 05C69