作业帮 > 数学 > 作业

如何证明小于30条边的平面简单图有一个结点的度数小于等于4

来源:学生作业帮 编辑:百度作业网作业帮 分类:数学作业 时间:2024/07/31 11:37:26
如何证明小于30条边的平面简单图有一个结点的度数小于等于4
如何证明小于30条边的平面简单图有一个结点的度数小于等于4
设无向图中顶点个数为 N,则边数最大为 N*(N-1)/2
假设所有结点的度数都大于4,则总度数>4N
边数=总度数/2 > 2N
N*(N-1)/2 > 2N
N>5
边数> 6*(6-1) =30条
与题目所给矛盾,所以小于30条边的平面简单图有一个结点的度数小于等于4