关于Ore-(1)型图中的Hamilton圈

D0I:10.13374/j.issn1001-053x.1992.04.031 第1卷第4期 北京科技大学学报 Vol.14 No.4 1992年7月 Journal of University of Science and Technology Beijing Ju1y1992 关于0re-(1)型图中的Hamilton圈 李明楚李忠祥 摘要：1982年Win证明了：2n阶Orc-(i)型图G有边不交的一个Hami1ton圈和一个 1-因子。本文证明了：在几乎与Win定理的条件相同的情况下，Or-(1)型图有边不交的两 个Hami1ton圈和一个1-因子。 关键词：Hamilton圈，l-因子，0re-(1)型阳 Hamilton Cycles in the Graphs of Ore-Type-(1) Li Mingchu'Li Zhongxiang' ABSTRACT:It was proved by S.Win in 1982 that if the sum of the degree of nonadjacent vertices of a simple graph G of order 2n is at least 2n+1,then G has a Hamilton cycle and a 1-factor which are edge-disjoint.In this paper,it is proved that,under almost the same condition as Win's theorem,has at least two Hamilton cycles and a 1-factor which are edge-disjoint, KEY WORDS:Hamilton cycle,1-factor,Ore-type-(1) 本文所讨论的图均为无向简单图。用6(G)和a(G)分别表示图G中的最小度和点独立数， 用△(G)表示G的最大度。设A二V(G),B二P(G),令R.(A)=V(G)-〔AU(UN。(a)门， eG(A,B)={uv:u∈A,v∈B,uD∈E(G)‖。设Pc(u1,4)=41424,表示G中从41到u4 的一条路，令P。'(u,“1)=““:-1“1。一个图G称为Ore-(k)型图，如果对任何一对不 相邻顶点u和v都有d(u)+d(v)≥V(G)‖+k(k为整数)。其它没有说明的术语和记号参见文 1991-08-29收稿 敦学力学系(Department of Mathematics and Mechanics) 483

第 卷第 期 北 京 科 技 大 学 学 报 。 。 年 月 刀 。 。 关于 一 型图 中的 圈 李 明楚 李忠祥 摘 要 年 证 明 了 ，阶 一 型 图‘ 有边不交的一个 圈和 一 个 一 因子 。 本文证明 了 在几乎与 定理 的条件相同的情况 下 ， 一 型 图有边不交的 两 个 圈和一个 一 因子 。 关健词 。 圈 ， 一 因子 ， 。 一 型 图 一 一 “ 犷 口口 。 召 ， 一 一 。 ， ， ， 一 一 ， 一 ， 一 一 本文所讨论 的图均为无 向简单图 。 用叔 和 分别表示图 中的最小度和 点独立数 ， 用△ 表示 的最大度 。 设 二犷〔 ， 二 犷 ， 令 。 。 ， 丈。 。 任 ， 任 ，。 任 。 设 ‘ ，。 。 一 〔 。 〕 ， 。 〔 。 …“ 表示 中从。 到 。 的一条路 ， 令尸万’ 。 。 ， 。 ， 二 ，价一 二 ， 。 一个图 称为 一 型 图 ， 如果 对 任 何 一对不 相邻顶点 。 和， 都有 ， 犷 为整数 。 其它 没 有说明 的术语和记号参 见文 一 一 收稿 · 数学 力学系 五 瓜 几 通 城 萦 DOI ：10．13374／j ．issn1001－053x．1992．04．031

献〔1〕。 关于Hamilton圈的研究已有很多结果，但关于边不交的Hamilton圈的研究却不算多。 刘振宏r3)证明了偶数阶Ore-(2)型图有两个边不交的Hamilton圈。本文作者c4)证明了偶数 阶Ore-(3)型图有边不交的两个Hamilton圈和一个1-因子。最近本文作者之一c5)证明了： n阶(n≥40)Ore-(-1)型图G(6(G)≥7)有两个边不交的Hami1ton圈除了3类图外。 Win()证明了偶数阶Ore-(1)型图有边不交的-一个Hami1ton圈和一个1-因子。本文将证明： 2n阶(n≥13)Ore-(1)型图G(6(G)≥7)有边不交的两个Hamilton圈和-一个1-因子。 1引 理 为了证明本文的主要定理，先介绍一些引理。 引理1e)设G是具有a(G)≤6(G)的简单图，u,v∈V(G)且uvEE(G)。令Bo(u,v)= V(G)川-d(u)-d(v),R&(u,v)={s∈Rc(u,v):d(x)≥0e(u,v)+2}。如果|R6(u,o)川 0a(u,v),或者|R&(u,v)月=9c(4,o)且.r(G)≥2，则G是Hamilton图当且仅当G+uv是n Homiiton图。 引理2：8)设G是具有a(G)≤(G)且k(G)1的简单图，u,v∈v(G)且uv∈E(G)。如 果d(u)+d(w)≥IV(G川-(k(G)-1),那么G是Hamilton图当且仅当G+uv是Hamilt o 图。 图G在引理1和2下的闭包仍用G表示。 引理3设G是2n阶Ore-(1)型图，令X={x:d(x)≤n,￥∈V(G)》,则X1≤n-1 引理3证明是比较简单的，略证。 引理4设G是2n(n≥13)阶Ore-(1)型图且6(G)≥7，则G具有边不交的一个Hamilton 圈H和一个1-因子N使得k(G-H-N)≥2 证明：显然G中含有边不交的一个Hamilton圈H和一个1-因子N。令G'=G-H-N, H1=G-H,H2=G-N,X={x:x∈V(G),d()≤m},Y=V(G)-X。由引理8可知 X1≤n-1。如果G'是2-连通，则引理成立。因此设G'不是2-连通。下面分两种情形来证 明。 (1)G'不连通 这时，由已知条件可知G'恰好含有两个分支G:和G2且V(G,)川≥5(i=1,2)。如果G,中 含有Y中点，则V(G:)1≥n-1。下面分两种情况进行讨论 ①G1和G2同时含有Y中点。 这时1V(G,)≥n-1(=1,2)。如果G:和G2同时含行X中点，则G:(i=1,2)至多含有 X中3个点，且G:和G2不能同时含有X中3个点。现在再分两种情况来讨论。 (a)设V(G:)l=n-1,则1V(G2)|=n+1 这时Y中任何一点∈V(G:),都与V(G:)中所有点（在G,中）相邻。对于X中任一点 x∈V(G1),如果V(G:)中有一点y使得￥yEE(G),那么d。(x)≥2n+1-3-(n+1)= H-3,否则有d。(x)≥m-4,从而6(G,)≥n-4>V(G1+3,同理可证(G≥n-3> 2 严(G:)1+3,因此G,(任=1,2)为Hamilton连通。这时不难证明H:中有至少4条边莲结G: 2 484

献〔 〕 。 关于 圈的研究已有很多结果 ， 但关于边不交 的 圈的研究却不算多 。 刘振 宏 〔 “ ’ 证明 了偶数 阶 一 型 图有两个边不交 的 圈 。 本文 作者 ‘ ’ 证明 了偶 数 阶 一 型图有边不交 的两个 。 立 圈和一个 一 因子 。 最 近本文 作者之 一 亡 ” ’ 证 明 了 阶 一 一 型图 有两个边不 交 的 圈 除 类 图外 。 〔 ，证 明 了偶 数阶 。 一 型 图有边 不交的一个 。 圈和一个 一 因子 。 本文将证明 阶 一 型图口 ‘ 李 有边不 交 的两个 圈和 一 个 一 因子 。 引 理 为 了证 明本文 的主 要定理 ， 先 介绍 一 些 引理 。 引理 〔 “ 〕 设 是具 有 占 的简单图 ， ，‘ ， 任 口 且 。 。 〔 ‘ 。 令口 。 。 ， ， 二 犷 一 。 一 ， 二 “ ， “ 任 。 ， “ 。 ， ， 。 如果 乙 ， 李 。 。 ， ， 或者 囚乙 。 ， 。 ， “ 且 、 ， 则 是 图 当 且仅 当 是 乞 图 。 引理 匕 ” 设 是具 有 镇 且 尺 口 、 的简单图 ， ， 。 任。 ‘ 且。 〔 。 如 果 。 一 伙 一 ， 那 么 是 图当且仅 当口 。 是 。 图 。 图 在 引理 和 下 的闭包仍 用 表示 。 引理 设‘ 是 。 阶 一 型图 ， 令 二 “ ‘ ， ‘ 〔 犷 ， 则 成 一 引理 证 明是 比较简单的 ， 略 证 。 引理 设 是 阶 一 型图且占 ， 则口具有边不交的一 个 。 圈 和 一个 一 因子 使得‘ 一 一 证 明 显然 中含有边不交的一个 “ 。 “ 圈 和一个 一 因子 。 令 ‘ 二 一 一 ， ， 一 ， 二 一 ， 二 ‘ 任 口 ， 幻 《 玛 ， 犷 一 。 由 引 理 可知 成 。 一 。 如果 ‘ 是 一 连 通 ， 则引理 成立 。 因此设 ‘ 不是 一 连通 。 下 面分两种情形 来 证 明 。 产 不连 通 这时 ， 由已知 条件可知 ‘ 恰好含有两个分支 ，和 ， 且 川 ‘ 二 ， 。 如果 ‘ 中 含 有 中点 ， 则 ‘ 一 。 下面分 两种情况 进行讨 论 ① 诊 和 ‘ 同时含有 中点 。 这时 犷 、 一 了二 ， 。 如果 和 同时含有 中点 ， 则 口 ‘ 二 ， 至 多含有 中 个点 ， 且 ‘ 和 不能 同时 含有 中 个 点 。 现 在再分 两种情况来讨论 。 设 犷 一 ， 则 厂 口 卜 ， 这时 中任何一点 任厂 ， 都与 ， 中所有点 在 ， 中 相邻 。 对于 中任一点 二 〔 厂 ， 如 果 中 有一点 使得 二 夕 任 口 ， 那 么 ‘ ， 幻 十 一 一 二 ， ， 二 厂 ‘ ， 一 ， 否则有 。 ， 川 。 一 从而 ‘口 一 ” 、 诀匕 一 十 。 同理 可证叔 ‘ 一 李 ” 曰 乃 切 ’ 廿 、 ” 一 ， ， 、 ’ ‘ “ 一 、 一 土 产 一 ’ 一 ‘ 一 ’ “ 。 ’叫 ’ 切 跳 一 、 一 乙 产 一 ‘ ’ 。 夕 州 ， 因 此 ， “ ， 为 。 连 通 。 这时不难证明 中有至少 、 条边连 结

和G2,从而容易证明在H2中可选取适当的Hamilton圈C使k(H。-C)≥2即k(G-C-N) ≥2，故引理成立。 (b)设1V(G:)1=n,则1V(G2)l=n 对于任一点v∈V(G1),显然V(G2)巾有一点u使得uvEE(G),从而dc,()≥2n+1-3 -(n+2》=n-4,因此有6(G≥P(G,)1+1+2,同理有6(G)严(G)1+1+2。故 2 2 G:(=1,2)是Hamilton连通。由于|Y|n+1且dc,(w)n-2(i=1,2)(v∈Y),故不 难证明在H2中有至少4条边连结G,和G2,这时容易可证在H2中可选取适当的Hamilton圈 C使得K(G-C-N)22。故引理成立。 ②G'中只有一个分支含有Y中点（不妨设是G2) 由引理3，可知V(G2)川>n+1且G〔V(G:)门为完金图。显然G2中不含有X中任何点 且6(G)≥V(G:)引-4。不难证明6(G2)≥2n+1-3-(V(G:)儿+2)≥V(G2)引-4≥ V(Gl+3,故G,为Hamilton连通。如果V(G,!≤6，则不难证明引理成立，因此设 2 V(G)引≥7，下面分两种情况来讨论。 (a)设V(G1)川=7。 如果在H2中H有至少4条边连结G,和G2,则不难证明可选取适当的Hamilton圈C使得 《(H2-C)≥2，否则，在H,中N至少有8条边连结G,和G2,这时可选取适当的1-因子N' 使得k(H1-N')≥2，于是引理成立。 (b)设V(G1)引8。 如果N中（在H1中)有至少3条边连结G1和G2,则同上一样可证引理成立，故设在 H,中N有至多2条边连结G,和G2,由此可以推出H中（在H2中）至少有4条边连结G1和 G2(否则，就有u∈V(G1)和v∈V(Gz),使得uw∈E(G)且d。(u)≤IV(G,)川，dc(v)≤ V(G2)川，从而有d(u)+d(v)≤2n,矛盾)。这时不难证明引理成立。 (2)G′是连通但非2-连通。 此时将割点或割边删除，这时与情形(1)一样可证引理成立。 引理5设G是2n(n≥13)阶Ore-(1)型简单图，H和W分别是G中的Hamilton圈和1-因 子且H和N是边不交的。如果a(G-H-N)≥9，那么k(G-H-N)≥2 从引理4的证明过程中可知此引理成立。 2主要定理 定理：设G是2n(n≥13)阶Orc-(1)型图且d(G)≥7，则G具有边不交的两个Hamilton圈 和一个1-因子。 证明：由引理4可知G中有边不交的Hamilton圈C和1-因子N使得k(G-C-N)≥2：设 G。=G-C-N,X={x:x∈V(G)且d(x)≤n),Y=V(G)-X。由引理3可知IX|≤n-1, 且Y[≥n+1,现在分两种情形来证明。 情形1a(Go)≤6(G,) 这时考虑在引理1和2下所定义的闭包G。 485

和 口 ， 从而容易证 明在 中可选 取 适当 的 圈 使双 一 ， 故引理 成立 。 设 厂 二 ， 则 二 对 于任一点 ” 任 工 ， 显然 ‘ 。 中有一点 “ 使得 “ ” 任 ， 从而 心 即此 夕 一 一 。 一 一 二 ，卜 ， 因此有咨 ， ， 同理 有‘ ‘ 卜 ’夕鱼 一 巨工 十 。 故 “ 二 ， 是 连 通 。 由于 ” 一 且 。 ‘ ” 〕 、 ，， 一 ， “ 任 ， 故 不 难 证 明在 中有至少 条边 连 结 ，和 ， 这时容 易可 证在 。 中可选 取适当 的 圈 使得以 一 一 。 故 引理 成 立 。 ② ’ 中只 有一个分支含有 中点 不妨设是 由引理 ， 可知 厂 。 且 〔犷 〕为 完全图 。 显然 中不含 有 中任何 点 且 占 召 ， 异 一 。 不难 证明 一 一 厂 一 犷 ， 二 、 二 二 二 、 一 ， 一 ， ， 二 、 ， 。 、 。 ， 、 」 ” 。 叮气巡 十 “ ， 故 为 “ “ ，。 ” 连通 。 如果 、 ， 镇“ ， 则不难 证明引 理 成 立 ， 因 此 设 犷 、 ， 下 面分两 种情况来讨论 。 设 犷 ， 二 。 如果在 中 有至少 条边连结 ，和 ， 则不难 证 明可选取 适当 的 圈 使 得 、 〔 一 ， 否则 ， 在 中 至少 有 条边连 结 和 召 ， 这时可选取 适当的 一 因子 ’ 使 得以 ， 一 ‘ ， 于是 引理 成立 。 设 厂 。 如果 中 在 中 有至少 条边连 结 和 ， 则 同上一样 可证 引 理 成 立 ， 故设 在 中 有至 多 条边连 结 和 ， 由此可以推 出 中 在 中 至少 有 条边连 结 和 否则 ， 就有 任 ‘ 和 任厂 “ ， 使得 。 。 毛甲右 且 。 。 簇 ， 。 簇 犷 ， 从而 有 镇 ， 矛盾 。 这时不难证 明引理 成立 。 产 是连通但非 一 连通 。 此时将割点或割边 删除 ， 这时与情形 一样 可证引理 成立 。 引理 设 是 ” 阶 一 型简单图 ， 和 分别 是 中的 圈和 一 因 子且 和 是边 不交的 。 如果 一 一 ， 那 么 袱 一 一 从 引理 的 证 明过程 中可知 此 引理 成立 。 主要定理 定理 设 是 阶 。 一 型 图且 口 ， 则 具有边 不交 的两个 圈 和一个 一 因子 。 证 明 由引 理 可知 中有边不交的 圈 和 一 因子 使得《 一 一 。 设 ‘ 。 二 一 一 ， 二 引 名 任 且 叼 镇 ， ， 二 厂 一 。 由引理 可知 毛 。 一 ， 且 酬 。 十 ， 现在分 两种情形来证 明 。 情形 。 。 这时考虑在 引理 和 下所定 义 的闭包

(1)6(G)≥7 对于Y中任意两点u和v,若uuEE(G),则0c。(“,)≤2n-(dc。(u)+dc。(U)≤4，故 对任一点xERc,(u,v),有dc。(x)≥6≥0c。(,v)+2,从而x∈R:。(u,0),放R。(“,) =R。,(u,),于是由引理1可知uw∈E(Go),从而G,(Y门为完全图。再由引理3可知 d。(x)≥n(x∈Y)。对任意一点x,∈X,设Z。={y1y￥。EGE(G)}。由于d(￥o)+d(y)≥ 2n+1(y∈Zo),故do。(￥g)+dc。(y)≥2n-5,从而0c,(xg,y)=2n-dc,(xo)-dc。(y)≤ 5,从而dc,(v)≥7≥6c,(x,y)+2(对任意∈Rc。(x,y),于是∈R台。(x,y),从而 Ro。(xo,y)=Rc。(x,y)。由引理1可知xy∈E(G)。而1Z。l=2n-1-d(x)≥n-1 且2二Y,故da。(x)≥n-1。再由引理2可知对于任一点4∈Y,有x,u∈E(Gg),于是G, 是完全图，故G。有Hamilton圈。从而定理成立。 (2)6(G。)≤6 设dc(w)=d(G),则dc(w)≤9且IRc(w)川≥2n-10≥n+3。由于Rc()中任一点u有 de(u)≥2n-8,故da,(u)≥2n-11,从而GCRc(w)门为完全图。对任意y∈Y,u∈Rc(w),若 vyEE(Ga),则d后。(v)≥2n-11且da。(y)≥n-2,从而de。(o)+da,(y)≥2n,故uy∈ E(G。)于是GCY)为完全图。下面分4种情形来讨论。 ①IX1≥9 在这情形下，G,cX)为Hamiltoni连通，由k(Ga)≥2可知G。为Hamilton图，故G。有 Hamilton圈，于是定理成立。 ②1X1=8,则IYT=2n-8 令Z1=《xdc(x)≥10}，与情形(1)一样可证G〔Z,)为完全图 (1) (a)X中至少有两点u,和u2使得d。(u)≥10(i=1,2)。 这时、对任一点y∈Y,0c。(u1,y)≤2，而6(G0)≥4，故R6(u1,y)=Rc。(“,y), 由引理1可知u,y∈E(G。),因此dn(u,)≥n+6(i=1,2),这时G,〔YU{u1,42}门为完全 图，从而Y中任意一点y,da(y)≥2n-7 (2) 不难证明X-{u1,u2}中至少有一点u3使得d(u3)≥8 (3) 否则：设d(x,)=7(x。∈X-{u1,u2}).令2=ylyx,年E(G)},则d。(y)≥2n-6(y∈ Z),而Zl=2n-8,故ec(X,Y)≤2(n-7),而ec(Y,X)≥3(2n-8),矛盾，因此(3)式成 立。由引理1及(2)、(3)可知u3y∈E(Gg)(对于任一y∈Y).因此，G,〔YU{“1,42,“}〕为 完全图，这时da,(y)≥2n-6（y∈Y),再由引理1可知G,为完全图，故G。有Hamilton圈。 (b)X中至多有一点u。使得c(u,)≥10 这时d(G)≥8（否则若6(G)=7,设d(w)=7,那么|R。(w)川=2n-8,dc(y)≥2n-6 (y∈Rc(w).由于|Y1=2n-8,故ec(Y,X)≥3(2n-8),ec(Y,X)≤n-7+12+1=n+6,矛 盾)，从而d(G。)≥5.由k(G,)≥2，可知Y中至少有两点y:和yz使得do(y:)≥2n-8(i= 1,2).由引理1可证明y,在G。中与所有点都相邻，因此(G。)≥6，再由引理1可知G。为 完全图，故定理成立。 ③5≤X!≤？这情形类似于(b)可证定理成立。 ④1X≤4则1Y1≥2n-4.由6(G,)≥4及引理2可知G。为完全图。故定理成 立。 486

。 对于 中任意 两点“ 和 ， 若 “ ， 百 ， 则 。 。 ‘ ， 镇 一 。 。 “ 。 。 ” ， 故 对任一点“ 任 。 。 ， “ ， 有 。 。 。 “ ， “ ， 从而‘ 任 丢 。 “ ，” ， 故 丢。 ， “ 二 凡 。 ， “ ， 于是 由 引理 可知 。 。 〔 瓦 ， 从而万 。 〔 〕为完全图 。 再 由 引 理 可 知 心 。 幻 ” “ 任 。 对任意一点二 。 任 ， 设 。 二 沙 气 任 。 由于 二 。 夕 任 。 ， 故 。 。 ‘ 。 。 一 ， 从而 。 。 “ 。 ， 二 ” 一 ‘ 。 。 一 。 。 ， 从而 。 。 “ 。 。 。 ， 对任意 任 。 。 。 ， ， 于是“ 任 丢 。 。 ， ，从而 。 。 ‘ 。 ， 二 。 。 。 ， ， 。 由引理 可知 〔 。 。 而 二 “ “ 一 少 。 二 且 。 二 ， 故心 。 ‘ 。 ” 一 再由引理 可知对于任一点“ 〔 ， 有 “ 任 。 ， 于是 。 是完全图 ， 故 。 有 圈 。 从而定 理 成立 。 。 落 设 ‘ 。 二 ， 则 ‘ 。 且 。 二 一 ” 。 由于 。 〔二 中任一点 有 。 》 卜 ， 故 。 一 ， 从而 。 〔 。 〕为完全图 。 对任意 任 ， ” 任 。 “ ，若 ，百 。 ， 则 〔 ， 一 且 妻 。 一 ， 从而 叮 。 。 。 。 ， 故 任 。 于是 。 〔 〕为完全图 。 下 面分 种情形 来讨论 。 ① 川 在 这情形下 ， 。 〔 〕为 连 通 ， 由‘ 。 可知 。 为 图 ， 故 。 有 圈 ， 于是定 理成立 。 ② ， 则 二 ” 一 令 谧 。 ， 与情形 一样可证 。 〔 〕为完全图 中至少 有两点 “ 和。 使得 ‘ 。 ‘ ‘ ， 。 这时 · 对任一点 夕 〔 ， 。 。 。 ， ， 夕 ， 而 ‘ 。 ， 故 吕 。 “ ‘ ， 。 。 “ ‘ ， ， 由引理 可知“ ‘ ‘ 。 ， 因此 。 “ ‘ ， ， 这 时 ‘ 。 〔 口 “ ，， “ 〕为完全 图 ， 从而 中任意一点’ 。 妻 “ 一 不难 证 明 一 。 ， 中至少 有一点 使得 。 否则 设 。 。 〔 一 ， ， 。 。 令 孟二 伽 夕 。 去 ， 则 。 一 少 任 孟 ， 而 孟 一 ， 故 。 ， 成 一 ， 而 。 ， 一 ， 矛盾 ， 因此 式 成 立 。 由引理 及 、 可知 夕 任 。 对于 任一夕 任 。 因此 ， 。 〔 ， 。 ， 。 〕 为 完全图 ， 这时 。 一 任 ， 再 由引理 可知 。 为 完全图 ， 故 。 有 “ 。 “ 圈 。 中至多 有一点 “ 。 使得 苗。 。 。 这时 否则若 ， 设 二 ， 那么 。 。 一 ， ‘ 夕 妻 。 一 夕 〔 。 。 由于 一 ， 故 ， 一 ， 。 ， 一 二 ， 矛 盾 ，从而 。 由以 。 ， 可知 中至少 有两点 和 使得 心 。 ， 一 ‘ 二 ， 。 由引理 可证 明 ‘ 在 。 中与所有点都相邻 ， 因此叔 。 ， 再 由引理 可知 。 为 完全图 ， 故定理 成立 。 ③ 这情形类似于 可证定理成立 。 ④ 镇 则 州 。 一 由 叔 。 及 引理 可知 。 为完全 图 。 故 定 理 成 立

惰形2a(G,)≥0(G。)+1 在这种情形下，分两种情况来讨论。 (1)6(G)≤n-4 设dc(w)=6(G),由于对于任意一点v∈R。(w)有dc(u)≥n+5。且dG,(v)≥n+2, 故G〔RG(w)门为完全图。因为|R:(w)川≥n+3,故任意一点v∈Rc(w),da,(v)≥n+2, 而da,(y)≥n-2(y∈Y),故"y∈E(G。)(这里的G。表示Bondy定义下的闭包)，这时 GCY)为完全图，又G〔X)为完全图，因此，(G,)≤4≤(G).这时和情形1一样可 证G。有Hamilton圈，故G,有Hamilton圈。 (2)6(G)≥n-3,则6(G。)≥n-5≥8 在这种情形下，考虑G的扩充闭包G。首先给出扩充闭包G。的定义：“设G。是简单图， 如果G,中有Hamiltor加圈，则定义G,的扩充闭包G:为K1to1,如果G,没有Hamilton圈，则定 义G,的扩充闭包为G:且G。满足：(a)V(G:)川=1V(G。)川且E(G。)三E(G).(b)G: 不是Hamilton图，但对于任何uu年E(G),G;+uv是Hamilton图。 如果“(G。)≤d(G。),这时用情形1一样的方法，不难证明定理成立。因此设a(G。)≥ 0(G。)+1,从而a(G。)≥n-4≥9 (4) 令h=a(G。)。如果G,有Hamilton圈，则已证明，故设G,中没有Hamilton圈。设T={u1, 42,,“}是G中的最大独立点集；令S=V(G)-T.不妨设d:(u1)=max{dc:(u)u∈ T},d6:(u)=max{dc:(u)引u∈T-{u:},由h≥n-4≥9，而T中最多有3个度数在G中 小于n+1的点，因此dc:(“)≥n-2且cg(“)≥n-2。由扩充闭包的定义可知，在G:中有 一条Hamiltom Po:(“1,“:)连结u1和u,假设在P6:(u1,4)上点的顺序排列T和S中的点 为S=}01,v2,…,v2m-},T={u1,“2,…,“},不雅得到2n-h≥h-1,故h≤n。现 在证明n≥h≥n-1且G8中有长为2n-1的圈。 (5) 事实上，设A={v,v:∈S,v141∈E(G)》,故|Al≥dcg(“1)-1≥n-3且We: (u)nA≥(dcg(“)+|A|)-INc:()UA|≥n-2+n-3-(2n-)=h-5≥4.由于 Nc:(u)∩A中不存在点U,使得0："1二P。(“1,“),故必有u,∈T,v,∈N6:(u,)∩A使 得dc:(4,)≥#-2且v,“0+2=Pc:(“1,“),因此在G:中有一长为2n-1的圈H=Pc:(u1, v,)U{wu}UP-:(u,v+1)U{知1u},故Nc:(u,)=V(H),这时a(G)≥dc:(u)+ 1≥n-1,故(5)被证。 对于任意u∈T和v∈S,设uv在E(G。),由扩充闭包的定义可知在G。中有一条连结u和 v的Hamilton路Pc:(“,v),不妨设在Ps:(“,0)上从u到v排列T和S中的点为T={u=4,u, …,u》.S={wi,v,",2-s=}。显然若uv∈E(G)(u;∈T),则u在Pc。(u,v)上的下 一个点不能和u相连结 (6) 令D(u)={o:∈Slu使E(Ga)},则lD(u)l=2n-h-dc:(u)。由(6)可知ec:(v, T)≤lD(u)l,不妨设dc:(ui)=min{dcg(w)lu∈T,dct(u)≥n-2},lNc:(o-s)nTl= max{lN:(o)nTl:v∈D(ui)}。记D=D(ui),B-〈u∈TlNo:(u)nD≠}，则ID|≤3 且ec:(v,T)≤3(v∈D) (7) (现在证明当|Di=3时，|B1=5:当|D1≤2时，1B|≤3 (8) 事实上，如果D|≤2，则ec:(v,T)≤|D≤2(v∈D),由(6)和(7)可知1B|≤3。如 果|D|=3且ec8(D,T)≤7，这时有h=n-1,从而不难证明1B≤5。现在设D|=3且 487

情形 。 。 在 这种情形下 ， 分两种情况来讨 论 。 一 设 。 功 二 ， 由于对 于 任意一点 “ 任 。 功 有 ” · 且 ‘ 。 ， ” ， 故 。 〔 。 ‘ 〕 为 完全图 。 因为 。 却 ， 故 任意一点 〔 。 ‘ ， 。 ， 而 。 。 一 ， 故 。 夕 任 瓦 这里的 瓦表 示 定 义 下 的闭包 ， 这 时 ‘ 。 〔 〕为 完全图 ， 又 〔 〕 为 完全图 ， 因此 ， 万 。 镇 叔 瓦 这时和情 形 一 样 可 证 。 有 圈 ， 故 。 有 圈 。 占 李 称 一 ， 则 。 一 在这种情形下 ， 考虑 。 的扩充闭 包 言 。 首先给 出扩充闭 包‘ 言的定义 “ 设 。 是简单图 ， 如果 。 中有 圈 ， 则定 义 。 的扩 充闭包 为 。 。 ， 如果 。 没有 圈 ， 则定 义 。 的扩充闭包为 言且 言满足 厂 言 犷 。 且 。 言 不是 图 ， 但 对于任何 庆 言 ， 言 。 是 图 。 如果 ‘ 言毛 忿 ， 这时用 情形 一样 的方 法 ， 不难 证 明定理成立 。 因此 设 李 言 ， 从而 口言》 一 》 令 言 。 如果 。 有 圈 ， 则已 证 明 ， 故 设 。 中没有 圈 。 设 二 左 ， “ ， … ， 。 是 ‘ 言中的最大独立 点集 令 二 一 · 不妨设 。 言 “ 一 “ 。 言 “ “ 〔 科 ， 心解 “ 。 桃 “ 任 一 恤 ， 由 ” 一 列 ， 而 中最多有 个度 数 在 ‘ 中 小 于 ” 的点 ， 因此 ‘ 七 “ ， ” 一 且心 。 ” 一 由扩充闭 包的定义可知 ， 在 言中有 一条 “ ‘ 言 ， “ 。 连 结 ，和 ， 假设在 。 ， 、 上点的顺序排列 和 中的点 为 。 ， 。 ， … ， 。 。 一 、 ， ， ， ， … ， 。 。 ， 不 难得到 一 》 一 ， 故 。 现 在证 明 》 一 且 忿中有长 为 一 的 圈 。 事实上 ， 设 ” ‘ “ ‘ 任 ， “ ‘ ， 任 忿 ， 故 。 言 “ 一 一 且 万 。 言 。 门 咭 “ 。 一 心 。 一 一 一 一 一 由 于 ‘ 言 “ 、 中不存 在点” ‘ 使得“ ‘ “ ‘ · 、 心 ，， “ 。 ， 故必 有 ，任 ， “ ‘ 任 忿 。 使 得 ‘ 言 “ ， 》 一 且 ， ‘ ， ‘ · 二 ‘ 忿“ ， ， ， ， 因此在 言中有一长为 一 的 圈 ， ， ‘ 日 “ ‘ “ ， 一子岔 “ ， ‘ ， ‘ · ， 故 。 言 ， 犷 ， 这时 言 ‘ 言 “ ， 一 ， 故 被证 。 对于任意 。 任 和 任 ， 设 。 去 ‘ 言 ， 由扩 充 闭包 的定 义 可知 在 言中有一条连 结 。 和 。 的 “ 路 。 言 “ ， ” · 不妨设在尸 ‘ 言 “ ， “ 上从 “ 到 “ 排 列 和 中的点为 丈 “ 二 “ ， “ 二 ， … ， “ 扑 扣 笠 ， “ 熟 “ · ， “ 氛 一 、 二 “ 卜 显 然若衅 ” 任 加 任 ， 则可在尸咭 ， ” 上 的下 一个点不能和 “ 相连 结 令 谧， ‘ 任 ‘ 偌 言 ， 则 一 一 。 七 由 可知 。 七 “ ， ， 不妨设 。 忿“ 。 言 “ 任 ， ‘ 言 ” 一 ， ‘ 言 二 。 一 。 自 ‘ 忿 “ 自 任 笠 。 记 盆 ， “ 任 ‘ 咭 “ 自 笋价 ， 则 且 咭 ， ， ， 任 现在证明当 二 时 ， 当 】 镇 时 ， 簇 事实上 ， 如果 蕊 ， 则 。 忿 ， 蕊 簇 任 ， 由 和 可 知 。 如 果 且‘ 舒刀 ， 簇 ， 这时有 “ 一 ， 从 而 不 难 证 明 簇 。 现在设 二 且