设G为一n阶简单无向图，证明以下结论： 1：若G不联通，则G的补图联通 2: 若G至少具有(n-1)*(n-2)/2 +2

Question

条边，则G中存在Hamilton圈，并举例说明减少一条边后的n阶简单无向图中不一定存在Hamilton圈

Answer 1

（1）归纳法，设n=k成立，对n=k+1，G里先选k个点，不妨设此k点子图G'本身联通，剩下一点a若和G'里的任意点相连，则已证明。若否，则a与G'里的点都不相连，则G的补图已经自然联通了：通过a，2步以内即可从一点到任意一点。

（2）证明：对任意点u和v，d(u)+d(v)>=n。用反证法：若d(u)+d(v)<=n-1，因为满连时d(u)+d(v)=2n-2，去掉u连v的边，d(u)+d(v)减掉2，然后去掉uv和其他点的一条边，d(u)+d(v)都只减掉1，所以为了让d(u)+d(v)<=n-1，最起码要去掉(2n-2)-(n-1)-1=n-2条边。此时，边数<=n(n-1)/2-(n-2)=(n-1)(n-2)/2+1，与边数的条件矛盾。因此任意点u和v，必须都有d(u)+d(v)>=n，然后直接套用哈密顿圈的著名定理即可：若对任意uv，都有d(u)+d(v)>=n，则图里必有哈密顿圈。

(n-1)(n-2)/2+1条边的反例：n-1点的子图G'全联通，然后剩下点a与G'里某一点相连。容易证明：因为d(a)=1，无哈密顿圈，而且边数确实等于(n-1)(n-2)/2+1。