（1）歸納法,設(shè)n=k成立,對n=k+1,G里先選k個(gè)點(diǎn),不妨設(shè)此k點(diǎn)子圖G'本身聯(lián)通,剩下一點(diǎn)a若和G'里的任意點(diǎn)相連,則已證明.若否,則a與G'里的點(diǎn)都不相連,則G的補(bǔ)圖已經(jīng)自然聯(lián)通了：通過a,2步以內(nèi)即可從一點(diǎn)到任意一點(diǎn).
（2）證明：對任意點(diǎn)u和v,d(u)+d(v)>=n.用反證法：若d(u)+d(v)<=n-1,因?yàn)闈M連時(shí)d(u)+d(v)=2n-2,去掉u連v的邊,d(u)+d(v)減掉2,然后去掉uv和其他點(diǎn)的一條邊,d(u)+d(v)都只減掉1,所以為了讓d(u)+d(v)<=n-1,最起碼要去掉(2n-2)-(n-1)-1=n-2條邊.此時(shí),邊數(shù)<=n(n-1)/2-(n-2)=(n-1)(n-2)/2+1,與邊數(shù)的條件矛盾.因此任意點(diǎn)u和v,必須都有d(u)+d(v)>=n,然后直接套用哈密頓圈的著名定理即可：若對任意uv,都有d(u)+d(v)>=n,則圖里必有哈密頓圈.
(n-1)(n-2)/2+1條邊的反例：n-1點(diǎn)的子圖G'全聯(lián)通,然后剩下點(diǎn)a與G'里某一點(diǎn)相連.容易證明：因?yàn)閐(a)=1,無哈密頓圈,而且邊數(shù)確實(shí)等于(n-1)(n-2)/2+1.