图11* 图11-* 11.4欧拉图和哈密顿图 下面推论紧接着280页推论11.7 【推论11.8*】设G是简单图，”，y,是不相邻顶点，且满足d()+d(v,)≥n。则G存在 哈密尔顿圈的充要条件是G+(y,V,)有哈密尔顿圈。 【证】必要性显然，下面证充分性。假定G中不存在哈密顿圈，则G+(,')中存在的哈 密顿圈一定经过边(y,y),删去(y,)),即G中存在一条以，y,为端点的哈密顿路，又 因d(y,)+d(v,)≥n,仿照定理11.9证明(2)(c)中的方法，可以构造出哈密顿圈，与假设矛 盾。 以下内容加在习题11.4前面 【定义11.*】若y,和v,是简单图G的不相邻顶点，且满足d(y)+d(v,)≥n,则令 G'=G+(心，y),对G重复上述过程，直至不再有这样的顶点对为止。最终得到的图称为 G的闭合图，记作C(G)。 【引理11.*】简单图的闭合图是唯一的。 【证】设C(G)和C2(G)是G的两个闭合图，E1={a,a2,…a,}，E2={b,b2,…b} 分别是C(G)和C,(G)中新加入边的集合，可以证明E,=E2,即C(G)=C,(G)。如若不i g b c d e f h a 图11--** e d a b c 图11--** 11.4 欧拉图和哈密顿图 下面推论紧接着 280 页推论 11.7 【推论 11. 8*】 设G 是简单图， , i j v v 是不相邻顶点，且满足 ( ) ( ) i j d v  d v  n 。则G 存在 哈密尔顿圈的充要条件是 ( , ) G i j  v v 有哈密尔顿圈。 【证】必要性显然，下面证充分性。假定G 中不存在哈密顿圈，则 ( , ) G i j  v v 中存在的哈 密顿圈一定经过边( , ) i j v v ，删去 ( , ) i j v v ，即G 中存在一条以 , i j v v 为端点的哈密顿路，又 因 ( ) ( ) i j d v  d v  n ，仿照定理 11.9 证明(2)(c)中的方法，可以构造出哈密顿圈，与假设矛 盾。 以下内容加在习题 11.4 前面 【定义 11. *】若 i v 和 j v 是简单图 G 的不相邻顶点，且满足 ( ) ( ) i j d v  d v  n ，则令 ' ( , ) G G i j   v v ，对G ' 重复上述过程，直至不再有这样的顶点对为止。最终得到的图称为 G 的闭合图，记作C(G)。 【引理 11. *】简单图的闭合图是唯一的。 【证】设 1 C (G) 和 2 C (G)是G 的两个闭合图， 1 1 2 { , , } E r  a a a ， 2 1 2 { , , } E s  b b b 分别是 1 C (G) 和 2 C (G)中新加入边的集合，可以证明 E1  E2 ，即 1 2 C (G)  C (G) 。如若不