proof of Mantel’s theorem

Let G be a triangle-free graph. We may assume that G has at least three vertices and at least one edge; otherwise, there is nothing to prove. Consider the set P of all functions c:V(G)+ such that vV(G)c(v)=1. Define the total weight W(c) of such a function by


By declaring that cc* if and only if W(c)W(c*) we make P into a poset.

Consider the function c0P which takes the constant value 1|V(G)| on each vertex. The total weight of this function is


which is positive because G has an edge. So if cc0 in P, then c has support on an induced subgraphMathworldPlanetmath of G with at least one edge.

We claim that a maximal element of P above c0 is supported on a copy of K2 inside G. To see this, suppose cc0 in P. If c has support on a subgraph larger than K2, then there are nonadjacent vertices u and v such that c(u) and c(v) are both positive. Without loss of generality, suppose that

uwE(G)c(w)vwE(G)c(w). (*)

Now we push the function off v. To do this, define a function c*:V(G)+ by


Observe that wV(G)c*(w)=1, so c* is still in the poset P. Furthermore, by inequality (*) and the definition of c*,

W(c*) =uwE(G)c*(u)c*(w)+vwE(G)c*(v)c*(w)+wzE(G)c*(w)c*(z)

Thus c*c in G and is supported on one less vertex than c is. So let c be a maximal element of P above c0. We have just seen that c must be supported on adjacent verticesMathworldPlanetmath u and v. The weight W(c) is just c(u)c(v); since c(u)+c(v)=1 and c has maximal weight, it must be that c(u)=c(v)=12. Hence


which gives us the desired inequality: |E(G)||V(G)|24.

Title proof of Mantel’s theorem
Canonical name ProofOfMantelsTheorem
Date of creation 2013-03-22 13:03:04
Last modified on 2013-03-22 13:03:04
Owner mps (409)
Last modified by mps (409)
Numerical id 6
Author mps (409)
Entry type Proof
Classification msc 05C75
Classification msc 05C69