设G是简单图,有n个顶点,最小度数a>[n/2]-1,证明G是连通的

发布网友发布时间：2023-07-12 13:55

共1个回答

热心网友时间：2024-10-30 15:51

设G不连通,则G中至少包含两个连通分支,而且必有一个分支顶点数小于等于n/2.
即使这个分支是完全图,其每个顶点的度数d(p)(n/2)-1矛盾.所以图G只有一个连通分支,G是连通的.

声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL:11247931@qq.com

设G是简单图,有n个顶点,最小度数a&gt;[n/2]-1,证明G是连通的