证明:(1)证明对每一对不相邻的顶点u,v, 若d(u)+d(v)n-1,则G有哈密顿路。 1)先证明G是连通的 2)再证G有哈密顿路。 采用反证法 若G中无哈密顿路,令P(V1,V2V1)为 G中的最长路,长度kn-1 ①证明G中存在长度为H+1的回路 分v1与vn1相邻和v与v不相邻两种情况 讨论证明:(1)证明对每一对不相邻的顶点u,v, 若d(u)+d(v)≥n-1,则G有哈密顿路。 1)先证明G是连通的 2)再证G有哈密顿路。 采用反证法. 若G中无哈密顿路，令P(v1 ,v2 ,… vl+1 )为 G中的最长路，长度l<n-1 ① 证明G中存在长度为l+1的回路 分v1与vl+1相邻和v1与vl+1不相邻两种情况 讨论