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 ( Γ(x) and Γ(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


Summing these inequalities for all edges of G gives us


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

Since ΣxV(G)δ(x)=2|E(G)|, we get 4|E(G)|2=(ΣxV(G)δ(x))2 and applying the Cauchy-Schwarz inequality gives 4|E(G)|2nΣxV(G)(δ(x))2n2|E(G)|.

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

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