推论:若G是有n(≥3个顶点的简单图, 对于每一个顶点v满足d(v)≥n/2,则G是 哈密顿图。 证明:若G中任意两点都相邻,则有一条 哈密顿回路: 1V2:V3 若G中存在不相邻的点,则对于任意两个 都不相邻的点u,v, 有d(u)+d(V)≥n,由定理5.14知G是哈密 顿图。 显然≥3的完全图是哈密顿图。推论：若G是有n(≥3)个顶点的简单图, 对于每一个顶点v满足d(v)≥n/2,则G是 哈密顿图。 证明：若G中任意两点都相邻，则有一条 哈密顿回路： v1,v2,v3,…vn,v1。 若G中存在不相邻的点，则对于任意两个 都不相邻的点u,v， 有d(u)+d(v)≥n,由定理 5.14知G是哈密 顿图。 显然≥3的完全图是哈密顿图