一定存在一個(gè)度數(shù)至少為n-2的點(diǎn)v.否則的話,每個(gè)點(diǎn)的度數(shù)不超過n-3,那么邊數(shù)最多只有n*(n-3)/22.如果v的度數(shù)是n-2,那么把v從圖中去掉,剩余子圖含有n-1個(gè)點(diǎn)以及至少(n-2)(n-3)/2+2條邊.由歸納假設(shè),子圖中有HC(Hamilton Circuit):u1-u2-.-u(n-1)-u1.從這n-1個(gè)點(diǎn)里任取兩個(gè)與v相連的,比如ui與uj.那么原圖的HC就是u1-u2-.-ui-v-uj-.-u(n-1)-u1.3.如果v的度數(shù)是n-1,那么把v從圖中去掉,剩余子圖有至少(n-2)(n-3)/2+1條邊.在子圖里任意加上一條邊,使得邊數(shù)達(dá)到(n-2)(n-3)/2+2,再用歸納假設(shè),得到一個(gè)HC.如果HC中不包含新加的邊,用2的方法構(gòu)造新HC;如果包含,那么把這條ui-uj邊替換成兩條ui-v-uj.