请输入您要查询的字词:

 

单词 ProofOfMantelsTheorem
释义

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

W(c)=uvE(G)c(u)c(v).

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

W(c0)=uvE(G)1|V(G)|1|V(G)|=|E(G)||V(G)|2,

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

c*(w)={c(u)+c(v)w=u0w=vc(w)otherwise.

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)
=uwE(G)[c(u)+c(v)]c(w)+0+wzE(G)c(w)c(z)
=uwE(G)c(u)c(w)+vwc(v)c(w)+wzE(G)c(w)c(z)
=W(c).

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

14=W(c)W(c0)=|E(G)||V(G)|2,

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

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 6:40:43