设G是一个有p个顶点q条边的图.试证：如果q=1/2(p-1)(p-2)+2,则G是哈密顿图.注：G的一个包含所有顶点的圈称为G的一个哈密顿圈.具有哈密顿圈的图称为哈密顿图.

分类: 作业答案 • 2022-08-09 20:53:33

问题描述：

设G是一个有p个顶点q条边的图.试证：如果q=1/2(p-1)(p-2)+2,则G是哈密顿图.
注：G的一个包含所有顶点的圈称为G的一个哈密顿圈.具有哈密顿圈的图称为哈密顿图.

答

很陷阱.实际上1/2(p-1)(p-2)就是p-1个点的完全图的边数（就是1到p-2的求和）,在完全图中当然存在任意两点的H路了,再加上2条边正好连上第p个点.