设G是无向简单图，有2n个结点且每个结点度数均为n。证明：G是连通图。

设G是无向简单图，有2n个结点且每个结点度数均为n。证明：G是连通图。

证明：假设C不是连通图，设H是G的-个连通分支。
由于图C是简单图几每个结点的度数为n，所以子图H与G-H也是简单图且每个结点的度数为n。
因此，H与G-H中的结点数均至少为+1。
于是G的结点数大于等于2n +2，这与G的结点数为2n矛盾。，因此假设为谬，所以C是连通图。