若无向简单图G有2n个顶点,每个顶点的度数至少为n证明此图是连通图。

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

共1个回答

热心网友时间：2024-11-17 15:37

【答案】：[证明]用反证法，设图G不是连通图，不妨设图G有两个连通分支G₁和G₂构成，其中G₁含有k个顶点(1≤k＜n)，G₂含有2n-k个顶点。在连通分支G₁中任取一点v₁，在连通分支G₂中任取一点v₂。由于图G是简单图，所以G₁和G₂也是简单图，于是有
deg(v₁)≤k-1
deg(v₂)≤2n-k-1由此可得
deg(v₁)+deg(v₂)≤k-1+2n-k-1=2n-2
但假设图G中每个顶点的度数至少为n，因此
deg(v₁)+deg(v₂)≥2n由此引出矛盾，本题得证。

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