设G是一个有p个顶点q条边的图.试证：如果q=(1/2)*(p-1)(p-2)+2,则G是哈密顿图.

Question

设G是一个有p个顶点q条边的图.试证：如果q=(1/2)*(p-1)(p-2)+2,则G是哈密顿图.

Answer 1

很陷阱.可以看出p-1个顶点的完全图的边数刚好是1/2*(p-1)(p-2)（也就是一到p-2的求和）
再加上2条边刚好连上第p个点.
完全图中当然可以找出任何两点的H路了