题目

设G为一n阶简单无向图,证明以下结论：1：若G不联通,则G的补图联通 2:若G至少具有(n-1)*(n-2)/2 +2
条边,则G中存在Hamilton圈,并举例说明减少一条边后的n阶简单无向图中不一定存在Hamilton圈

提问时间：2021-01-08

答案

（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.