用到這幾個(gè)概念：
1、設(shè)F是圖G的一個(gè)子圖,對(duì)于F中的任意頂點(diǎn)u和v,只要uv是G中的邊,則uv一定是F中的邊,此時(shí)稱F為G的一個(gè)誘導(dǎo)子圖.
2、若S是圖G的一個(gè)非空頂點(diǎn)集合,則由S誘導(dǎo)的G的子圖就是以S為頂點(diǎn)集的誘導(dǎo)子圖.
3、除第一個(gè)和最后一個(gè)頂點(diǎn)外,沒有頂點(diǎn)重復(fù)的回路(circuit)稱為圈(cycle).k圈是一個(gè)長度為k的圈,記作Ck其中k是下標(biāo)(k≥3).
4、一個(gè)含圖G的每個(gè)頂點(diǎn)的圈稱為是G的一個(gè)Hamilton圈.一個(gè)含有Hamilton圈的圖稱為是一個(gè)Hamilton圖(或稱此圖是Hamilton的).
要用到下述定理：
Th.設(shè)u和v是一個(gè)n階圖G的兩個(gè)不鄰接的頂點(diǎn),并且degu+degv≥n.則G+uv是Hamilton的當(dāng)且僅當(dāng)G是Hamilton的.
此定理的證明見Gary.Chartrand的書《圖論導(dǎo)引》
下面是對(duì)本題的證明.
證明：設(shè)P:x0,x1,...,xm是圖G中最長的一條路(長為m),記由{x0,...,xm}誘導(dǎo)的G的子圖為H.由P是G中最長路知,與x0以及xm相鄰的點(diǎn)都在路P上(否則與P是G中最長路矛盾),因此由誘導(dǎo)子圖定義知,在H中x0(或xm)的度數(shù)與在G中x0(或xm)的度數(shù)是一樣的,不妨就將其簡單記作deg(x0)及deg(xm). 我們采用反證法,假設(shè)m＜2k.顯然n＞2k≥2,首先m＞0(否則G不連通)；若m=1,由G的頂點(diǎn)數(shù)n＞2知V(G)-{x0,x1}非空,由G連通知,存在一點(diǎn)y∈V(G)-{x0,x1}以及xi∈{x0,x1}使得yxi∈E(G),則y,x0,x1組成長為2的路,與x0x1是G中最長路矛盾,因此m＞1.從而x0與xm不相鄰.又deg(x0)+deg(xm)≥2k≥m+1(由假設(shè)m＜2k知),而且H+x0xm包含有圈C(m+1)(m+1是下標(biāo)):x0,x1,...,xm,x0.故H+x0xm是Hamilton的,由上面的定理知,H是Hamilton的.故H包含一個(gè)圈C(m+1).由于n＞2k≥m+1,因此V(G)-{x0,...,xm}非空,由G連通知,存在一點(diǎn)y∈V(G)-{x0,...,xm}以及xi∈{x1,...x(m-1)}使得yxi∈E(G).因此G中包含這樣一個(gè)圖形：一個(gè)圈C(m+1)以及圈外一點(diǎn)y與C(m+1)中的點(diǎn)xi相鄰接,這樣就找到G中一條長為m+1的路(在紙上畫畫圖便知道了),與P:x0,...,xm是G中最長路矛盾.故m≥2k. 證畢.