Question

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

Answer 1

【答案】：[证明]用反证法，设图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由此引出矛盾，本题得证。