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

若简单图至多有2n个顶点,每个顶点度数至少为n,G必为连通图。

分类: 离散数学(02324) 发布时间: 2024-08-04 00:07 浏览量: 0
若简单图至多有2n个顶点,每个顶点度数至少为n,G必为连通图。
【正确答案】：证明:G= ,l Ⅴ l≤2n,deg(vi)≥n。
 若G不是连通图,即W(G)≥2。对任一个连通分量,因每个顶点度数至少为n,且G为简单图,没有多重边及自悬边,故连通分量中所含顶点的个数≥n+1,
 l Ⅴ l≥2(n+1)=2n+2,与l Ⅴ l≤2n矛盾。所以G必为连通图。  证毕
← 返回分类 返回首页 →

相关题目

↑