证明:少于30条边的简单平面图有一个顶点度数小于等于4。

证明:少于30条边的简单平面图有一个顶点度数小于等于4。
【正确答案】：证明:设G= 为简单平面图,边数为m,顶点个数为n,面数为r。由已知,m_max=29。
反证,若图中所有顶点的度数均大于4。
每个面至少由3条边组成 :3r≤2m<2×30=60,r<20,r_max=19。
图中各顶点度数之和为边数的2倍,∑deg(v_i)=2m> 4n,即2n得到n<15,n_max=14。
平面图满足欧拉公式,n-m+r=2,m+2≤n_max+r_max=33,m≤31,m_max=31,矛盾。

证明:少于30条边的简单平面图有一个顶点度数小于等于4。

相关题目