作业帮 > 数学 > 作业

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

来源:学生作业帮 编辑:搜搜考试网作业帮 分类:数学作业 时间:2024/06/11 13:48:47
如何证明小于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