Question

证明在无向简单连通平面图中，必存在一个顶点，其度数小于等于5。

Answer 1

【答案】：[证明]用反证法。
设无向简单连通平面图G中有n个顶点v₁，v₂，…，v_n。如果G中没有一个顶点其度数小于等于5，也即对于任意的顶点v_i，都有
deg(v_i)≥6
由于图G是简单连通平面图，所以
3n-6≥m
或者有
6n-12≥2m
由于
deg(v_i)=2m
由此得到
6n-12≥6n
这是不可能的，所以在无向简单平面图中，必存在一个顶点，其度数小于等于5。