是这样，则不失一般性，设a+1=(u,v)∈E,是构造C(G)时第一条不属于E2的边，亦即 a1C2(G)。令H=GU{a,a2,…a,},，这时H是C(G)和C,(G)的子图。由于构造 C,(G)时要加入a1,显然H中满足d(w)+d(v)≥n,但(u,)C2(G),与C2(G)是G的 闭合图矛盾。 【定理11.*】简单图G是哈密顿图的充要条件是其闭合图是哈密顿图。 证明：设C(G)=GUE1,E,={e,e2,e,},由上面推论11.8*和引理11.*，G有哈密顿圈 台G+e,有哈密顿圈一…台GUE,有哈密顿圈。由于C(G)唯一，故定理得证。 请在排版时把此定理证明中的推论11.8*和引理11.*换成相应编号。 12.2欧拉公式和极大平面图 将289页第19行的“本节以下内容中的G均是简单连通可平面图，且共有n(n≥3)个顶 点，m条边，r个面。”删去（因为这句话在本节中只影响到了定理12.3）。并在此处加上 一个推论12.2（或者借用习题12.1第一题的结论），后面的推论编号相应增加1。 【推论12.2】设G是平面图，有k个连通分量（若G为连通图则k=1),n个顶点，m条 边，r个面，则n-m+r=k+1。 【证】对G中连通分量的个数k用归纳法来证明。当k=1时，G为连通图，由欧拉定理， 结论显然成立。假设当k=p-1时，n-m+r=k+1=p成立，考虑k=p时的情况。易证， 在G中一定存在这样的连通分量，它的内部面中没有其它的连通分量，即其它连通分量都 在它的外部面中。任取这样的一个连通分量G,设G有n个顶点，m条边，r个内部面， 则将G从G中移出后得到的子图G-G中，有n-n个顶点，m-m条边，r-r个面。这 是因为G的顶点和边都与其它连通分量不相交，而G的外部面在G-G中仍然保留，内部 面则全部移出。于是由归纳假设，G-G为有p-1个连通分量的平面图，有 (n-n,)-(m-m,)+(r-r)=p。而我们知道G是连通平面图，有r+1个面，由欧拉定理有 n-m,+(G+1)=2，于是易得n-m+r=p+1=k+1成立。证毕。 定理12.3改为： 【定理12.3】设G是简单连通平面图，有n个顶点，m条边，r个面，若G的每个面的度 大于等于k,则 ≤m≤km-2) 2 k-2是这样，则不失一般性，设 1 1 ( , ) i a   u v  E 是构造 1 C (G) 时第一条不属于 E2 的边，亦即 1 2 ( ) i a  C G 。令 1 2 { , , } H G i   a a a ，这时 H 是 1 C (G) 和 2 C (G) 的子图。由于构造 1 C (G) 时要加入 i 1 a  ，显然 H 中满足 d(u)  d(v)  n ，但 2 (u, v)C (G) ，与 2 C (G)是G 的 闭合图矛盾。 【定理 11. *】简单图G 是哈密顿图的充要条件是其闭合图是哈密顿图。 证明：设 1 C(G)  G  E , 1 1 2 { , , } E r  e e e ,由上面推论 11.8*和引理 11.*， G 有哈密顿圈  G 1  e 有哈密顿圈 G  E1有哈密顿圈。由于C(G) 唯一，故定理得证。 请在排版时把此定理证明中的推论 11.8*和引理 11.*换成相应编号。 12.2 欧拉公式和极大平面图 将 289 页第 19 行的 “本节以下内容中的 G 均是简单连通可平面图，且共有 n（n  3）个顶 点，m 条边，r 个面。” 删去（因为这句话在本节中只影响到了定理 12.3）。并在此处加上 一个推论 12.2（或者借用习题 12.1 第一题的结论），后面的推论编号相应增加 1。 【推论 12.2】 设 G 是平面图，有 k 个连通分量（若 G 为连通图则 k = 1），n 个顶点，m 条 边，r 个面，则 n – m + r = k + 1。 【证】 对 G 中连通分量的个数 k 用归纳法来证明。当 k = 1 时，G 为连通图，由欧拉定理， 结论显然成立。假设当 k = p – 1 时，n – m + r = k + 1 = p 成立，考虑 k = p 时的情况。易证， 在 G 中一定存在这样的连通分量，它的内部面中没有其它的连通分量，即其它连通分量都 在它的外部面中。任取这样的一个连通分量G1，设G1有 1 n 个顶点， m1 条边， 1r 个内部面， 则将G1从 G 中移出后得到的子图G G1  中，有 1 n  n 个顶点， m m1  条边， 1 r  r 个面。这 是因为G1的顶点和边都与其它连通分量不相交，而G1的外部面在G G1  中仍然保留，内部 面 则 全 部 移 出 。 于 是 由 归 纳 假 设 ， G G1  为 有 p – 1 个 连 通 分 量 的 平 面 图 ， 有 1 1 1 (n  n )  (m  m )  (r  r )  p 。而我们知道G1是连通平面图，有 1r 1个面，由欧拉定理有 1 1 1 n  m  (r 1)  2 ，于是易得 n  m  r  p 1 k 1成立。证毕。 定理 12.3 改为： 【定理 12.3】 设 G 是简单连通平面图，有 n 个顶点，m 条边，r 个面，若 G 的每个面的度 大于等于 k，则 ( 2) 2 2     n k k m kr