首页 > 离散数学(02324) > 题目详情

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

分类: 离散数学(02324) 发布时间: 2024-08-04 00:05 浏览量: 1
设G是无向简单图,有2n个结点且每个结点度数均为n证明:G是连通图。
【正确答案】：证明:假设G不是连通图,设H是G的一个连通分支。
由于图G是简单图且每个结点的度数为n,
所以子图H与G-H也是简单图且每个结点的度数为n。
因此,H与G-H中的结点数均至少为n+1。
于是G的结点数大于等于2n+2。
这与G的结点数为2n矛盾。
因此假设为谬,所以G是连通图。
← 返回分类 返回首页 →

相关题目

↑