若无向简单图G有2n个顶点 每个顶点的度数至少为n证明此图是连通图。
顶点,度数
已帮助 人
若无向简单图G有2n个顶点，每个顶点的度数至少为n证明此图是连通图。
-
[证明]用反证法，设图G不是连通图，不妨设图G有两个连通分支G1和G2构成，其中G1含有k个顶点(1≤k＜n)，G2含有2n-k个顶点。在连通分支G1中任取一点v1，在连通分支G2中任取一点v2。由于图G是简单图，所以G1和G2也是简单图，于是有
deg(v1)≤k-1
deg(v2)≤2n-k-1由此可得
deg(v1)+deg(v2)≤k-1+2n-k-1=2n-2
但假设图G中每个顶点的度数至少为n，因此
deg(v1)+deg(v2)≥2n由此引出矛盾，本题得证。