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

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

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