《离散数学》证明 若G是连通平面图,则G中必有一个结点V,使得deg(V)≤5

原来为你 1年前 已收到1个回答 举报

枫霜二月 春芽

共回答了16个问题采纳率:100% 举报

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

1年前

8
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 16 q. 0.033 s. - webmaster@yulucn.com