(经典证明题) G为n阶无向简单图，边数m=(n-1)(n-2)/2+2，证明G是哈密尔顿图。

G为n阶无向简单图，边数m=(n-1)(n-2)/2+2，证明G是哈密尔顿图。

请大家指教。

5 个解决方案

#1

UP

#2

这个，我想了一下
用反证的方法
设这个图不是汉密顿图
则使边分布在尽量少的点上
因为有m=(n-1)(n-2)/2+2条边
2m>（n-1)(n-2)则至少有n-1个顶点和外的n-2个顶点之间有边
要使它不是汉密顿图则只有这n-1个顶点不和另一个顼点有关系
而m=(n-1)(n-2)/2+2,还有另两条边，则只有余下的一个和此n-1个中的
两个之间有边，则存在有一回路经过所有的点，则假设不成立
：
比较乱，请有心人整理一下，具体怎么写？

#3

根据汉密顿图的判别条件，在无向简单图G=<V,E>.中，若能找到u,v两个顶点，使得deg(u)+deg(v)>=|V| ，则G是哈密顿图。
在该题中，|v|=n，首先，所有顶点的度数之和为：
2E=(n-1)(n-2)+4=n*n-3*n+6
其次，在该图中，任意去掉两个顶点u和v后，一个有(n-2)个顶点的无向完全图来说，共有(n-2)(n-3)/2条边，即一个有(n-2)个顶点的无向图中所有点的度数之和最大为(n-2)(n-3)=n*n-5n+6，所以，与顶点u和v相关的边的度数之和大于等于(n*n-3n+6)-(n*n-5n+6)=2n，即deg(u)+deg(v)>=n。所以G是哈密顿图。

#4

thanks

#5

这里果然高手如云：Dtang属说理型的，Sunli则是严密的数学论证。

多谢！