如何证明小于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