关于Ore-3型图-Win猜想的部分结果

D0I:10.13374/j.issm1001-053x.1991.02.016 北京科技大学学报 第13卷第2期 Vol.13 No.2 1991年3月 Journal of University of Science and Technology Beijing March 1991 关于Ore-3型图-Win猜想的部分结果 李明楚*李忠祥* 摘要：证明了Win猜想对：=3成立。实际上，且得到了更好的结论：2n(n>10)阶 Orc-3型图中存在边不交的两个Hxmi1ton圈和一个1-因子，且对8(G)=5而言，结论是 最好可能的。 关键词：Hamilton图，Orc-3型图，因子 On the Graphs of Ore-Type-(3)-A Result of Win's Conjecture Li Mingchu'Li Zhongxiang' ABSTRACT:It is proved that Win's conjecture is true for k=3.A better conclusion is obtained.There exist two Hamilton cycles and a 1-factor which are edge-disjoint in a Ore-type-(3)graph of order 2n (n>10).Moreover,this result is best possible for 6(G)=5. KEY WORDS:Hamilton cycle,Ore-type-(3)graph,factor 本文所讨论的图均为无向的简单图。设G是一个简单图，用G表示G的闭包，用6(G) 和a(G)分别表示G的最小度和独立数，用G〔R)表示点集R在G中的导出子图，用Pc(u1, “k)=“1u2…u:表示G中以41和4：为端点的一条路，设A,B2V(G),Rc(A)=V(G) -〔AU(UNc(@)门，ec(A:B)=I{uv∈E(G)lu∈A,v∈Bl.其余没有说明的符号见文 EA 献E1). 给定非负整数k,若图中每一对不相邻顶点u和v,都有d(u)+d(w)≥IV(G)|+k,则 称G为Ore-k型图。Ore-k型图有许多性质，比如Ore-k型图是k-Path-Hamilton图等 1990-09-11收稿 ·数力系(Department of Mathematics and Mechanics) 186

第 卷第 期 年 月 北 京 科 技 大 学 学 报 。 关于 一 型图一 猜想的部分结果 李明楚 ‘ 李忠祥 ‘ 摘 要 证明 了 猜想对 二 成立 。 实际上 ， 且得 到 了更好 的 结 论 。 。 。 阶 一 型 图中存在边 不交 的两个 圈和一 个卜因子 ， 且对 占 句 而言 ， 结论 是 最好可 能的 。 关健词 圈 ， 一 型 图 ， 因 子 一 一 一 ‘ ‘ 夕 “ ’ 夕劣 夕 。 ， 吞 一 一 一 一 五 ， · ， 一 一 ， 本文所讨论的图均为无向的简单图 。 设 是一个简单图 ， 用 表示 的闭包 ， 用 和 分别表示 的最小度和独立数 ， 用 〔 〕表示点集 在 中的导 出子图 ， 用 ‘ 。 ，， 。 。 … 表示 中以 和 为端点的一条 路多 设 ， 只 犷 ， 。 厂 一 〔 ‘ 〕 ， 。 。 〔 任 ， ‘ 任 其余没有说明的符号见文 任 献〔 夕 。 给定非负整数 ， 若 图 中每一对不相邻顶点。 和 ， 都有 十 川 乡 存， 则 称 为 一 型 图 一 型 图有 许多性质 ， 比 如 一 舟型 图是 卜 一 图 等 一 一 收稿 数 力系 皿 DOI ：10．13374／j ．issn1001－053x．1991．02．016

等。对于具有偶然点的0re-k型图，1982年Win.S给出了下列猜想： 若G是2阶Ore-k型图，则G具有边不交的k+2个1-因子，其中0≤k≤2n一4。 1987年刘振宏【2)证明了对k=2Win猜想成立。本文证明了Win猜想对=3成立。 以下分别简称Hamilton圈和Hamiltoni连通为H-圈和H-连通。 1引 理 为了证明本文的定理，首先介绍一些引理。 引理1【3】设a(G)≤k(G),则简单图G有H-圈。 引理2【4】设G是n阶连通度为(G)(k(G)≥1)的简单图且a(G)≤6(G),则对Ha- milton性质而言，闭包运算的稳定度为n-(K(G)-1)。 引理3r5)设G是Ore-k型图，k≥0，IV(G)I≥3，则G是k-Path-Hamilton图. 引理4e】设G是n(m≥20)阶Ore-0型图，且6(G)≥5，则G具有两个边不交的Ha- milton圈， 引理5设G是2n阶0re一3型图，令Z={2∈V(G),d(z)≥n+2},则|Z1≥n+1. 引理6设G是2n阶0re-3型图且6(G)≥7，x。∈V(G),d(x)≤n,Z。={z|zE V(G),x。2EE(G)},如果G中还存在一点y。∈V(G)使得d(y。)≥d(x)+1且与Z。中至少 一点不相邻，则G具有边不交的两个H-圈和一个1一因子。 证：设22∈Z。且之2y。EE(G)。因d(x)≤n故 |Z。|=2n-d(x。)-1≥n-1,从而对任意一点2∈Z。有：d(2)≥(2n+?-d(x。)≥n+3,于是 在G〔Z]中有dccz。)(2)≥n+3-d(x)≥3，故在G〔Z,]中存在长为3的路p=(z1z223z4), 由引理4可知在G中存在H~圈C。Pp(这里C,与p均表示边之集合)。令G1=G-C。,这时 不难证明G,中有H-圈，取G1中的一个1-因子N。令G。=G1~N。现在证明G。中有H-圈。 事实上，考虑闭包Go。由da。(z)≥n(2∈2，)可知G。〔Z〕为完全图，从而d后，(z:)-1 (i=2,3)且d,(2,)≥d(z,)-2(i=1,4)。由已知条件有a.(y)≥d(x)-2,又由 d(xg)+d(22)≥2n+3可知dā，(y)+d后。(z2)≥2n,从而y,22∈E(Go),而yz2∈E(G), 故da。(22)≥d(22)且da,(y)≥d(×)-1,从而da,(22)+dan(x,)≥2n,于是x。22∈ E(G),从而推出了da。(x)>d(x)-2且da。(zz)≥d(z2)+1,因此d后(xg)+d后。(z)> d(x)-2+d(23)-1≥2n,故×oz3∈E(Go),推出了d元。(xo)≥d(xo)-1且da。(z3)≥d(23)。 了 同理可证xo2;∈E(G,)(j=1,4)且d元。(xo)≥d(xo)+1,da。(2;)d≥(2，)-1(j= 1,4)。由此可知xo2∈E(G0)(对任意2∈Z),于是得到了d元。(xo)≥d(x0)-3+2n- d(x)-1≥2n-4,由6(G。)≥4可知在G。中x。与所有点都相邻，从而G。〔Z。U{x}门为完 全图且|Z。U{xo}I≥n,于是 da。(2)≥d(2,)(=2,3) (1) 不难证明对于任意z∈Z。有2yo∈E(G),这时G〔Z。U{xoya}门为完全图且 dao(yo)≥n (2) 现在证明2：(i=2,3)在G。中与所有点都相邻 (3) 187

等 对于具有偶然点的 一 吞型 图 ， 年 给 出了下列 猜想 若 是 阶 一 型图 ， 则口具 有边不交 的 十 个 一 因子 ， 其 中 毛 一 。 年刘振 宏 〔 “ 〕 证明 了对 猜想 成立 。 本文 证明 了 猜想对 成立 。 以下分 别简称 圈和 连通为 一 圈和 一 连通 。 引 理 为 了证 明本文的定理 ， 首先介绍 一些 引理 。 引理 〔 “ ’ 设 毛 ‘ ， 则 简单 图 ‘ 有 一 圈 。 引理 〔 ‘ ’ 设 是 阶连通 度为秃 庵 ‘ 的 简单 图且 簇 ， 则 对 性 质而 言 ， 闭包运算的稳定 度为。 一 一 。 引理 ‘ ” ’ 设口是 一 掩型 图 ， ， 厂 ， 则 是 一 一 图 引理 〔 “ ’ 设 是 。 阶 一 。 型 图 ， 且 ， 则 具 有两 个边不交的 。 圈 。 引理 设 是 阶 一 型 图 ， 令 ‘ 任 犷 ， ， 则 多 。 引理 设 是 阶 一 型 图且 ， 。 任 犷 ， 。 毛 ， 。 二 二 」二 任 犷 ， 二 。 吞 ， 如果 中还存在一点 。 任犷 使 得 。 异 二 。 且与 。 中至少 一点 不 相邻 ， 则 具有边不交 的两 个 一 圈和一个 一因子 。 证 设 二 任 。 且 翔 。 乙 。 因 。 故 。 卜 一 。 一 。 一 ， 从而对任意 一点 任 。 有 的 一 。 。 十 ， 于 是 在 〔 。 〕 中有 ‘ 〔 。 〕 ‘ 一 “ 。 ， 故在 〔 。 〕 中存在长 为 的 路 ， 由引理 可知在 中存在 一 圈 。 这 里 。 与 均表示边 之集合 。 令 ， “ 一 。 ， 这时 不 难证明 ， 中有 一 圈 。 取口 、 中的一个卜 因子 。 令 。 一 。 现 在 证明 。 中有 一 圈 。 事实上 ， 考虑闭包刁 。 。 由 。 。 任 。 可知 讯 〔 。 〕 为完全图 ， 从而 气 ‘ 一 ‘ ， 且 。 “ ， ， 一 ， 由已知条件有 万。 。 。 一 ， 又 由 。 “ 可知 。 。 歹。 ‘ ， ， 从而 。 “ 任 。 ， 而 。 “ “ 乙 ， 故 。 “ ‘ 且 。 夕 。 。 一 ， 从 而 。 “ 。 ， 。 ， 于 是 ‘ 。 ‘ 任 。 ， 从而推出 。 。 。 一 且 。 “ ， 因此 。 。 。 ‘ ‘ 。 一 ‘ 一 ， 故‘ “ 任 “ ，推出 。 ‘ 妻 一 且 。 ‘ ， “ 。 同理可证 。 ， ，〔 。 ， 且 。 。 。 妻 。 ， 。 “ ， “ ， 一 二 ， 。 由此可知 。 二 任 。 对 任意 二 任 。 ， 于是得到 。 一 二 。 一 一 ， 由 。 可知在 。 中二 。 与所有点都相邻 ， 从而 。 〔 。 二 。 〕 为完 全图且 。 二 。 ， 于是 ‘ 之 ‘ ， 不 难证明对于 任意 任 。 有二 。 〔 。 ， 这 时 。 〔 。 二 。 ， 。 〕为完全 图且 。 。 。 现在 证明 ‘ ， 在 。 中与 所有点都相邻

事实上，若x2,E(G)(i=2,3),则d(x)+d(z:)≥2n+3,由(1)可知dan(x)+da。(2) ≥2n,故x2:EE(G。),从而d,(2)≥2n-4(i=2,3)。由6(Go)≥4可知(3)成立。 这时G。为3-连通。由(2)可知d。(2)≥n+1(2∈Zo),而任意一点u∈Z-Z。(2={z2∈ V(G),d(2)≥n+2})有da。(u)≥n-1,故uz∈E(Go)(2∈Z),由Z,U{xo}1≥n和(2)可知 石〔ZU{x}门为完全图，于是a(G,)≤d(G),由于对任意u2,EE(G)有d。(2)+d。 ()≥2n-1(j=1,4),从而uz,∈E(G。),故z,(j=1,4)在G,中与所有点都相邻，于是(G) ≥5。这时有α(G,)≤42n-5 +2n-5≥2n,故u,“;∈E(Go),从而G〔B1为完全图。又因da。(x:)+d元，(u;)≥2m-5+2n -8≥2n+1,故x:u,∈E(G),从而da。(x:)≥2n-6,于是x,xx∈E(G0)(牛k),(i=1,2, ,5；j=1,2,…,2n-6),故GCB1UB2〕为完全图，从而G是完全图，故G,有H-圈。 (2)3≤n≤6当n=3时，G为完全图，显然命题成立。当n=4,5,6时，G分别含有 如图所示的生成子图（见图1），从图中可知命题成立。且结论是最好可能的。 命题2。设6(G)=6且n≥9，则G具有边不交的两个H-圈和一个1-因子. 证：设d(xo)=6(G),Z。={2|2∈V(G),xo2EE(G)},则|Z,|=2n-7且对任意点 2∈Z。有d(2)≥2n-3。这时G具有边不交的两个H-圈和一个1-因子，否则，则选取一个边 数最多且满足已知条件的反例G,使得对任何uEE(G),G+4v具有边不交的两个H-圈 和一个1-因子。这时还可以证明： 对任何u,v∈E(G),uvEE(G),则d(u)+d(v)2n+5 (5) 188

事实上 ， 若 “ ‘ 乙 ， ， 则 “ ， 由 可知 。 。 “ ‘ ， 故二 二 ‘ 任 。 ， 从而 。 二 ‘ 一 ‘ ， 。 由‘ 。 可知 成立 。 这时 。 为 一 连通 。 由 可知 。 “ “ “ 任 。 ， 而 任意 一点 “ 任 一 。 仕 任 厂 ， “ ” 有 。 一 ， 故 “ 任 。 “ 任 。 ， 由 ‘ 。 乡 和 可知 仇 〔 以 ， 。 〕为完 全图 ， 于是 。 落 。 ， 由于对任 意 “ “ ， 吞 有 。 “ ， 。 “ 一 ， ， 从而 “ 之 ， 任 。 ， 故 “ ， ， 在 。 中与所有点都相邻 ， 于是耘 。 。 这时 有 云 。 镇 壳必 。 。 由引理 可知瓦有 一 圈 ， 故 。 有 一 圈 ， 因此 引理得 到 了证明 。 引理 设 是简单 图 ， “ ， 乙 且 十 时 犷 ‘ 一 ， 则 有 一 因 子 且仅 当 口 四 有 一 因子 。 关于 猜想 的 部分结 果 在 以 下 证明 中均 设口是 阶 一 型 图 。 设 川 任 ， 镇 ， 川 任 ， 夕 ， 二 任 ， 二 ， 二 任 犷 ， 二 ， 二 二 二 〔 厂 ， 二 ， 则 ， 日 且 口〔 〕为完全图 。 为 了证明定理 ， 首先给出 个命题 ， 然后 由这 个命题 ， 就证明 了定理是对的 。 定理的 内 容在本 节后 。 命 题 。 设 ， 则 口具有边不交的两 个 一 圈和一个 一 因子 ， 且这 个结论 是 最好 可能的 。 证 设 劣 。 二 ， 则 中有 一 个点与 二 。 在 中不 相邻 ， 设为 ， 。 ， ， 幻 ” · ， 。 一 ， 由 二 。 ‘ 妻 作 可知 ， ‘ 一 ， ， 一 ， ， 一 ， 从而 。 。 一 。 设 。 ， 二 ， … ， 二 ， 则 ‘ 一 ， 且 ‘ 与 中每 点都相邻 。 显然 ‘ 中有边不交 的 一个 一 圈 。 与一个 一 因子 令 。 二 一 。 一 万 ， 这时 有 。 “ 。 ， 。 劣 ‘ ” 一 ￡ ， ， ， ， 且 。 ‘ 一 ， ， … 一 。 ” 由于 中任意两 点 ‘和 ， 今 ， 在 。 中有 。 “ ‘ 。 ， 一 一 乡 ， 故 ， 任 。 ， 从而 。 〔 〕为完全图 。 又 因 。 ‘ 。 ， “ 一 一 ， 故 ‘ ， 任 。 ，从而 。 ‘ 一 ， 于 是“ ‘ 、 任 今 ， ， ， ” · ， ， ， ” · ， 一 ， 故 。 〔 日 〕为完全图 ， 从而 。 是完全 图 ， 故 。 有 一 圈 。 毛 当 二 时 ， 为完全图 ， 显 然命题成立 。 当 。 二 ， ， 时 ， 分 别含有 如图所示 的生成子 图 见 图 ， 从图 中可知命题成立 。 且结论是最好 可能 的 。 命题 设 ‘ 且 。 ， 则‘ 具有边不交 的两个 一 圈和一个卜 因子 证 设 。 ， 。 二 任 犷 ， 二 。 〔 ， 则 】 。 一 且对任意 点 任 。 有 幻 一 这时 召具有边不交的两个 一 圈和 一个 一 因子 ， 否则 ， 则选取一个边 数最多且满足 已知 条件的 反例 口 ， 使得对任何训 吞 ， 十 “ 具有边不交的两个 一 圈 和一个 一 因子 。 这时还可以 证 明 对任何 “ ， 。 任 ， 。 乙 ， 则 。 。 成

0 2,我=4 b.n-5 c. =6 图1G的生成子图的示意图 Fig.1 The spaning subgraph of G 由(6)可知G〔Z,)为完全图。 对于任何一点u∈V(G),若d(u)≥9，则u在G中与Z。中所有点都相邻 (6) 设与x。相邻点的集合为B,设B′={y∈B|yz∈E(G),对于任何z∈Z。},则IBI≥3，否 则若1B|≥2n-3,取GC2。]中长为3的路p=(z12223 24),由引理6可知在G中存在一个H圈C。一P,令G1=G-C0,不难证明G,有H-圈.取G1 189

图 的 生 成子 图的 示 意图 王 江 由 可知 〔 。 〕 为 完全图 。 对于 任何一点 任犷 ， 若 “ ， 则 “ 在 中与 。 中所有点都相邻 设与 。 相 邻点的 集合为 ， 设 ‘ 二 夕 任 夕 任 ， 对于 任何 任 。 ， 则 ‘ 】 ， 否 则若 ‘ ， 不妨 设 ， ， 则 尹 。 一 ’ 一 。 即 。 ， 亦即 一 毛 ， 矛盾 。 当 时 ， 由于对任意 任 产有 。 一 。 可知 〔 勺为完全图 ，从而 〔 。 口 勺 为完全图 。 显然对 “ 任 一 矛， 有 。 “ ， 否则 ，若设 。 。 二 ， 由于 “ 。 至少 与 。 中一点不 相邻 ， 这时类似于引理 的 证明 可以得 出矛 盾 。 因此 〔 一 〕 为完全图 。 由 。 可知存在 。 ， ， 任 产， 夕 。 ， 夕 ， 任 一 尹 。 使 得 。 。 夕。 ， 。 少 任 且 。 。 今 ， 夕 。 姜夕 。 分别选取 〔 。 尹 〕和 〔 一 ‘ 口 。 〕中的 一 路 〔 。 。 。 ‘ 〕 “ 。 ， ， 和 。 〔 刀 一 ， 毛 二 。 〕 夕 。 ， 夕 ， ，令 。 ， 口 口 。 ， 夕 且口 ， 二 一 。 ， 不难证明口 有 一 因子 ， 令 ‘ 。 二 口 一 这 时 。 〔 。 勺 为 完全 图 。 从 。 的取法 可知在 中有两 条边二 ，二 ， 使得 ‘ 任 。 ， ， ， 且 ， 二 ， “ 任万 ， 于是有 “ ‘ “ ‘ 一 ， 而 占 。 ， 故 。 ” 一 “ ， ， ， 即 妻 ， 而 。 镇 ， 由引理 可知 。 有 一 圈 。 于是命 题得证 。 命 题 。 设 功 ， 且 ， 则 具有边不交 的两 个 一 圈和 一个 一 因子 。 证 因 功 ， 故截 ， 取 中的 一 因子 ， 令‘ ， 一 万 ， 则夕 是 。 一 。 丝 图 ， 由引理 可知 中有边不交的两 个 一 圈 从而命题得 证 。 命题 。 设 日 姜功 ， 粉 少且乙 ， 则 具有边不交的两 个 一 圈和 一个 一 因子 。 证 若命题不成立 ， 则 可选取 使得 是具有边数最多 的且满足 已知条件的 反 例 。 此 时 由 可知 〔 〕 为完全图 。 设 。 任 ， 。 川 。 任 。 则 】 。 卜 一 。 一 一 。 显然对 任 ， 夕 任 口 ， 有二 任 由引理 可知对 任犷 口 ， 任 。 有 任 ， 于是 由 十 李 卜 。 一 。 一 其 中 任 ， 可知 ， 且当 任 时有 毛 且 日 今功则 〔 ， 从而 一 ， 取 〔 。 〕 中长 为 的路 二 勺 ， 由引 理 可知在‘ 中存在一个 圈 。 ， 令 一 。 不 难 证明‘ ，有 一 圈 取

中的一个1-因子N,令G。=G1-N,则G〔Z)为完全图，从而d后，(2)≥n+2(i=2,3), d后。(2》≥n+1(j=1,4).由于da。(2)≥n-1(z∈Z),故有22，∈E(G)(i=1,2, 3,4),从而da。(2)≥2n-4(j=1,2,8,4),故x2,∈E(G0),从而da。(x) ≥d(xo)-3+4=d(xo)+1.由此可知xo2∈E(G)(对于2∈Zo),因此da。(xa)≥2n-4 d后。(u)≥n+1(u∈Zo),从而对于任意u∈Z。在G,中与所有Z中点都相邻。由此可知 da(u)≥2n-4(u∈Z),而|ZgU{x}l=n,故8(G)≥"，从而G。有H-圈，故G。有 H-圈. (2)Y=中这时Z,卡中。类似于上面的证明可得出矛盾于是命题得证。 命题5.设YUZ1=中，8(G)≥7且X牛，则G具有边不交的两个H-圈和一个1-因子。 证：如果|X1≤3，则很容易证明命题成立。设引X≥4，若命题不成立，则选取边数最 多且满足已知条件的反例G,此时由(6)可知G〔Z)为完全图。显然IZ1≥n+2且|X引≤n-2 (否则，如果|Z1=n+1,则由1X|≥n-1有ec(Z,X)≥3(n+1),而与ec(X,Z)≤2 (n-1),矛盾)又因K(G)≥2故ec(Z,X)≥2且有z1,z2∈Z,x1,x2∈X使得z:x:∈E(G) 且x1卡x2,21卡22(=1,2).显然在G〔Z幻和GCX)中分别存在H-路P1=P。c2,(21,22)和 P2=Pccx)(x1,x2)。令C,=P1UP2U{21x1,22x2}则C。是G中的H-圈，不难证明G-C。 中有1-因子N.令G。=G-C。-N。由|Z1≥n+2可得在N中存在一条边e=u使得“1v∈Z 且u中2，v丰z,(i=1,2)。显然G〔Z)为完全图，于是d后o(w)≥d()且da(w)≥d(w). 而对任意x∈V(G),有da。(x)≥d(x)-3。 (10) 若ux∈E(G),则由do(u)+dao(x)≥d(u)+d(x)-3≥2n可知x∈E(G).从而 d后。(4)≥2n-1。同理可证da(w)≥2m-1,故K(G)≥2，由G。〔Z)及G〔X)为完全图可 知a(G。)≤8(G)。由于对任意z∈Z-{21,22}有d后。(2)≥d(2)-1,由引理2及上面的证 明可得d:。(2)≥2n-2,而|Z-{21,z2}1≥n,故K(G)≥n.因此G。是完全图，于是命题得证。 定理：设G是2n(n≥10)阶Ore-3型图，则G具有边不交的两个H-圈和一个1-因子， 且对6(G)=5而言结论是最好可能的。 证：由命题1至命题5可知定理成立。 参考文献 1 Bondy J.A.and Murty U S R.Graph Theory with Applications,The macmi- llan press,Londen,1976 2刘振宏。关于Win猜想的部分结果，数学学报，1987：5 3 Win S.,A Sufficient Condition for A Graph to Contain Three Disjoint 1- Factors,J.Graph Theory,1982:6 4朱永津，李洁。图论中的Hamilton问题，曲阜师范大学学报，1985，(2) 5 Kronk H V.A Note on K-Path-Hamilton Graphs,J.Comb.Theory, 1969,7:977 6 Li Hao and Zhu Yongjin,Edge-Disjoint Homilton Cycles in Graphs, 科学院系统所，PH.D Thesis,1988 190

中的一个 一 因子 ，令 。 ， 一 ， 则 。 〔 。 〕 为完全图 ， 从而 。 ‘ ， ’ ， ， 。 ’ ， · 由于 。 一 “ 任 ， 故有“ ‘ ， 〔 。 ， ， ， ， 从而 。 “ ， 一 ， ， ， ， 故 ，任 ， 从 而 。 。 。 一 。 · 由此 可知 任 对于‘ 〔 。 ， 因此 。 ， 。 一 。 ” 十 〔 。 ， 从 而 对 于 任 意 “ 任 。 在 。 中与所有 中点都相邻 由此 可 知 。 一 “ 任 。 ， 而 。 ， 故 占 。 ， 从而 。 有 一 圈 ， 故 。 有 一 圈 巾这时 ，等毋 。 类似于上面的 证明可得 出矛盾于是命题得证 。 命题 设 巾 ， 己 了且 簧万 ， 则‘ 具有边不交的两个 一 圈和一个 一 因子 。 证 如果 尤 ， 则很容易证明命题成立 。 设 ， 若命题不成立 ， 则选取边数最 多且满足 已知条件的反例 ， 此时 由 可知 〔 〕为完全图 显然 且 一 否 则 ， 如 果 。 ， 则 由 一 有 ‘ ， 李 ， 而 与 ‘ ， 。 一 ， 矛盾 又 因 尤 ‘ 故 。 。 ， 李 且有 二 ， 二 任 ， ， ， 〔 使得 二 ，二 ‘ 〔 ‘ 且二 姜二 ， 今 二 ， 。 显然在 〔 〕和 〔 〕 中分别存在 一 路 。 〔 〕 二 ，， 二 和 。 〔 〕 ， 。 令 。 ， 则 。 是 中的 一 圈 ， 不难证明 一 。 中有 一 因子 令 。 一 。 一 。 由 可得在 中存在一条边 二 “ “ 使得 “ 任 且 。 今二 ‘ ， 。 今 ‘ ‘ ， 。 显然 万 。 〔 〕 为完全图 ， 于是 。 “ 。 且 。 。 。 而对任意二 任 犷 ， 有 若。 二 一 。 若 〔 ， 则 由 子。 。 万。 一 可 知 “ 二 任 。 从而 若。 一 。 同理可证 若。 一 ， 故 ， 由 。 〔 〕及 〔 〕 为完全图可 知 。 瓦 叔 凤 。 由于对任意 任 一 二 ， 好有 。 习 幻 一 ， 由引理 及上面的 证 明 可得 于。 习 一 ， 而 一 二 ， 幻 ， 故 ‘ 。 。 因此 。 是完全图 ， 于是 命题得证 。 定 理 设 是 叮 阶 一 型 图 ， 则 具有边不交的两个 一 圈和一个 一 因子 ， 且对 占 而言结论是最好可能的 。 证 由命题 至命题 可知定理成立 。 参 考 文 献 · 五 ， ， ， 刘振 宏 。 关于 猜想 的部分结果 ， 数学学报 ， 。 ， 五 ， 。 ， 朱永津 ， 李洁 图论中的 向题 ， 曲阜师范大学学报 ， ， 一 一 ， 。 ， ， ， 一 ， 中国 科学 院系统所 ， ， 马