设G为一n阶简单无向图,证明以下结论：1：若G不联通,则G的补图联通 2:若G至少具有(n-1)*(n-2)/2 +2
问题描述：
设G为一n阶简单无向图,证明以下结论：1：若G不联通,则G的补图联通 2:若G至少具有(n-1)*(n-2)/2 +2
条边,则G中存在Hamilton圈,并举例说明减少一条边后的n阶简单无向图中不一定存在Hamilton圈
答
（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,然后直接套用哈密顿圈的著名定理即可：若对任意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.