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

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

人气：488 ℃　时间：2020-06-16 17:07:08

解答

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