> 数学 >
如何证明小于30条边的平面简单图有一个结点的度数小于等于4
人气:293 ℃ 时间:2020-05-21 03:39:54
解答
设无向图中顶点个数为 N,则边数最大为 N*(N-1)/2
假设所有结点的度数都大于4,则总度数>4N
边数=总度数/2 > 2N
N*(N-1)/2 > 2N
N>5
边数> 6*(6-1) =30条
与题目所给矛盾,所以小于30条边的平面简单图有一个结点的度数小于等于4
推荐
猜你喜欢
© 2024 79432.Com All Rights Reserved.
电脑版|手机版