这个很简单,如果是作业题的话.
因为如果是作业题,那么很可能你课堂上学过这样一个定理：
若每2个点的度数之和大于等于n,则有Hamiltonian回路.
就用这个定理就可以了.
具体方法：
完全图,总共有：n(n-1)/2条边.
那么,G最多比完全图少了：n(n-1)/2 - (n-1)(n-2)/2 - 2 = n-3 条边.
下面,我们来看看G中两个顶点的度数之和,最少是多少.
完全图中,两个顶点度数之和为：2(n-1)
现在少了 n-3 条边,最极端的情形,这 n-3 条边均与某两个顶点相连,而且其中1条边还是连接这2个顶点的.于是,这2个顶点最多少了 n-2 的度数,也就是还剩：
2(n-1) - (n-2) = n 度数.
所以,符合那个定理,有H回路.