设无向简单图G= ,l V l=9,Δ(G)=6,δ(G)=5证明:G中至少有5个6度顶点或至少有6个5度顶点。

设无向简单图G= ,l V l=9,Δ(G)=6,δ(G)=5证明:G中至少有5个6度顶点或至少有6个5度顶点。

证明:G= ,设度为6的顶点数为n₆,度为5的顶点数为n₅
已知:Δ(G)=6,δ(G)=5,则图中仅含度为5和度为6的顶点,即
n₅+n₆=l V l=9   (1)
 反证,若n₅≤5且n₆≤4,由式(1)可知,等号必成立,即n₅=5且n₆=4
 2×边数=5×n₅+6×n₆=5×5+6×4=25+24=49   (2)
 式(2)的左侧为偶数,右侧为奇数,矛盾。故假设不成立,结论得证。 证毕