proof of Mantel’s theorem
Let be a triangle-free graph. We may assume that has at least three vertices and at least one edge; otherwise, there is nothing to prove. Consider the set of all functions such that . Define the total weight of such a function by
By declaring that if and only if we make into a poset.
Consider the function which takes the constant value on each vertex. The total weight of this function is
We claim that a maximal element of above is supported on a copy of inside . To see this, suppose in . If has support on a subgraph larger than , then there are nonadjacent vertices and such that and are both positive. Without loss of generality, suppose that
Now we push the function off . To do this, define a function by
Observe that , so is still in the poset . Furthermore, by inequality (*) and the definition of ,
Thus in and is supported on one less vertex than is. So let be a maximal element of above . We have just seen that must be supported on adjacent vertices and . The weight is just ; since and has maximal weight, it must be that . Hence
which gives us the desired inequality: .
|Title||proof of Mantel’s theorem|
|Date of creation||2013-03-22 13:03:04|
|Last modified on||2013-03-22 13:03:04|
|Last modified by||mps (409)|