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