(iyv1与v1相邻→存在长度为1的回路 (i)v1与v不相邻→存在长度为H1的回路 (a)先证明G中与v相邻的顶点都在路P中, G中与v种相邻的顶点也都在路P中, (b)必存在点v使得在G中v1与v相邻,v;1与 v1相邻 故v1与v不相邻→存在长度为+1的回路 ②若G中存在长度为H1的回路,利用连通性 证明G中必存在长度为H+1的路,矛盾 (2)证明对每一对不相邻的顶点u,w,若 d(u)+d(v)≥n,则G有哈密顿回路(i)v1与vl+1相邻存在长度为l+1的回路 (ii)v1与vl+1不相邻存在长度为l+1的回路 (a)先证明G中与v1相邻的顶点都在路P中， G中与vl+1相邻的顶点也都在路P中， (b)必存在点vi ,使得在G中v1与vi相邻, vi-1与 vl+1相邻 故v1与vl+1不相邻存在长度为l+1的回路 ②若 G中存在长度为l+1的回路，利用连通性 证明G中必存在长度为l+1的路，矛盾 (2) 证明对每一对不相邻的顶点 u,v, 若 d(u)+d(v)≥n,则G有哈密顿回路