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

【参考答案】

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