alternate proof of Mantel’s theorem
Let be a triangle-free graph of order . For each edge of we consider the neighbourhoods (http://planetmath.org/NeighborhoodOfAVertex) and of . Since is triangle-free, these are disjoint.
This is only possible if the sum of the degrees of and is less than or equal to . So for each edge we get the inequality
Summing these inequalities for all edges of gives us
(The left hand side is a sum of where each edge incident with contributes one term and their are such edges.)
Since , we get and applying the Cauchy-Schwarz inequality gives .
So we conclude that for a triangle-free graph ,
|Title||alternate proof of Mantel’s theorem|
|Date of creation||2013-03-22 17:56:35|
|Last modified on||2013-03-22 17:56:35|
|Last modified by||lieven (1075)|