若G是连通平面图,则G中必有一个结点V,使得deg(V)≤5.

Question

若G是连通平面图,则G中必有一个结点V,使得deg(V)≤5.

Answer 1

证明：
假设G(V,E),任意的ai ∈ V,都有deg(ai) ≥ 6,则∑ deg(ai) ≥ 6n,根据握手定理 ∑ deg(ai) = 2m,故
2m ≥ 6n,即 m ≥ 3n,与平面图 m ≤ 3n-6 矛盾,所以假设不成立.