若简单图至多有2n个顶点,每个顶点度数至少为n,G必为连通图。

若简单图至多有2n个顶点,每个顶点度数至少为n,G必为连通图。

证明:G= ,l Ⅴ l≤2n,deg(vi)≥n。
 若G不是连通图,即W(G)≥2。对任一个连通分量,因每个顶点度数至少为n,且G为简单图,没有多重边及自悬边,故连通分量中所含顶点的个数≥n+1,
 l Ⅴ l≥2(n+1)=2n+2,与l Ⅴ l≤2n矛盾。所以G必为连通图。  证毕