离散数学问题

Question

show that a simple plannar graph G with 30 edges has a vertex whose degree is less than or equals to 4

Answer 1

中文是不是这个意思：边数为30的无向简单图可以存在一个顶点的度小于等于4
由n阶无向完全图的边数为n(n-1)/2，n=9时，完全图的边数为36，每个顶点的度都为8
边数为30的无向简单图在9阶完全图上减少6边，可以可以存在一个顶点的度小于等于4追问

9阶完全图不是可平面的呀？

追答

我概念已模糊了，9阶无向完全图不是可平面的？

Answer 2

能不能先翻译一下追问

证明一个有30条边的简单可平面图G，有一个点的度数小于等于4

追答

证明： 设结点数为v，边数为e
（1）若v＜3，则结论显然成立。
（2）若v≥3,则3v－6≥e，解得v≥(e+6)/3 假设图中每个结点的度数都大于4，即大于等于5。
则所有结点的度数之和就大于等于5(e+6)/3，
因此边数e≥5(e+6)/6 ，
解得 e≥30，这和已知边数小于30相矛盾。
所以结论成立