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|<3,不妨设1B|=2,则1B11Z。|+(|B引-|B'1(8-4)≥52|≥5×7=35即： 3|2。|≤4×4，亦即3(2n-7)≤16，矛盾。当n≥9时，由于对任意u∈B'有dc(u)≥2n-6 ≥n+8可知G〔B勹为完全图，从而G〔Z,UB门为完全图。显然对V4∈B-B',有dc(u)=6, 否则，若设d。(4o)=7,由于4，至少与Z。中一点不相邻，这时类似于引理6的证明可以得出矛 盾。因此G〔B-B门为完全图由K(G)≥2.可知存在u,“1∈B',yo,y1∈(B-B)U{xo}使 得40yo,“1y1∈E(G)且uo卡u1,yo卡y1分别选取G〔ZoUB门和G〔(B-B)U{x})中的H -路P1=Pot:ovn')(u0,4)和Pg=Pct(-Bu{*0}】(yo,y1),令C0=P,UP2U{uoyo, y1“}且G1=G-Co,不难证明G1有1-因子，令G。=G1-V.这时G〔ZUB)为完全 图。从C0的取法可知在N中有两条边2122,2324使得2：∈Z。(i=1,2,8,4)且21,22， zs24∈N,于是有d元0(z:)≥d(z)≥2n-3,而6(G)≥3，故da。（2o)≥2n-1(i=1, 2,3,4)即K(G)≥4，而a(Go)≤4≤K(G),由引理1可知G有H-圈。于是命题得证。 命题3。设X=中，6(G)≥7且n≥10，则G具有边不交的两个H-圈和一个1一因子。 证：因X=p,故d(G)≥n+1,取G中的1一因子N,令G1=G-N,则G1是Ore-0望 图，由引理3可知G:中有边不交的两个H-图。从而命题得证。 命题4。设YUZ:牛中，X￥中且8(G)≥7，则G具有边不交的两个H-圈和一个1-因子。 证：若命题不成立，则可选取G使得G是具有边数最多的且满足已知条件的反例。此时 由(6)可知G〔Z]为完全图.设xo∈X,Z。={2zx,∈E(G)}.则1Z|=2n-d(xo)-1 ≥n-1. 显然对Fx∈X,y∈YUZ1,有xy∈E(G) (7) 由引理6可知对yy∈YUZ1,Z∈Z。有yz∈E(G),于是由n+2≥d(y)≥|X|+1Z。| IX|+2n-d(xo)-1(其中y∈YUZ:)可知|XI≤3，且当y∈Y时有|X|≤2且|XUy1 ≤3 (8) (1)V卡中则」XUY|≤3，从而引Z|>≥2n-3,取GC2。]中长为3的路p=(z12223 24),由引理6可知在G中存在一个H圈C。一P,令G1=G-C0,不难证明G,有H-圈.取G1 189图 的 生 成子 图的 示 意图 王 江 由 可知 〔 。 〕 为 完全图 。 对于 任何一点 任犷 ， 若 “ ， 则 “ 在 中与 。 中所有点都相邻 设与 。 相 邻点的 集合为 ， 设 ‘ 二 夕 任 夕 任 ， 对于 任何 任 。 ， 则 ‘ 】 ， 否 则若 ‘ ， 不妨 设 ， ， 则 尹 。 一 ’ 一 。 即 。 ， 亦即 一 毛 ， 矛盾 。 当 时 ， 由于对任意 任 产有 。 一 。 可知 〔 勺为完全图 ，从而 〔 。 口 勺 为完全图 。 显然对 “ 任 一 矛， 有 。 “ ， 否则 ，若设 。 。 二 ， 由于 “ 。 至少 与 。 中一点不 相邻 ， 这时类似于引理 的 证明 可以得 出矛 盾 。 因此 〔 一 〕 为完全图 。 由 。 可知存在 。 ， ， 任 产， 夕 。 ， 夕 ， 任 一 尹 。 使 得 。 。 夕。 ， 。 少 任 且 。 。 今 ， 夕 。 姜夕 。 分别选取 〔 。 尹 〕和 〔 一 ‘ 口 。 〕中的 一 路 〔 。 。 。 ‘ 〕 “ 。 ， ， 和 。 〔 刀 一 ， 毛 二 。 〕 夕 。 ， 夕 ， ，令 。 ， 口 口 。 ， 夕 且口 ， 二 一 。 ， 不难证明口 有 一 因子 ， 令 ‘ 。 二 口 一 这 时 。 〔 。 勺 为 完全 图 。 从 。 的取法 可知在 中有两 条边二 ，二 ， 使得 ‘ 任 。 ， ， ， 且 ， 二 ， “ 任万 ， 于是有 “ ‘ “ ‘ 一 ， 而 占 。 ， 故 。 ” 一 “ ， ， ， 即 妻 ， 而 。 镇 ， 由引理 可知 。 有 一 圈 。 于是命 题得证 。 命 题 。 设 功 ， 且 ， 则 具有边不交 的两 个 一 圈和 一个 一 因子 。 证 因 功 ， 故截 ， 取 中的 一 因子 ， 令‘ ， 一 万 ， 则夕 是 。 一 。 丝 图 ， 由引理 可知 中有边不交的两 个 一 圈 从而命题得 证 。 命题 。 设 日 姜功 ， 粉 少且乙 ， 则 具有边不交的两 个 一 圈和 一个 一 因子 。 证 若命题不成立 ， 则 可选取 使得 是具有边数最多 的且满足 已知条件的 反 例 。 此 时 由 可知 〔 〕 为完全图 。 设 。 任 ， 。 川 。 任 。 则 】 。 卜 一 。 一 一 。 显然对 任 ， 夕 任 口 ， 有二 任 由引理 可知对 任犷 口 ， 任 。 有 任 ， 于是 由 十 李 卜 。 一 。 一 其 中 任 ， 可知 ， 且当 任 时有 毛 且 日 今功则 〔 ， 从而 一 ， 取 〔 。 〕 中长 为 的路 二 勺 ， 由引 理 可知在‘ 中存在一个 圈 。 ， 令 一 。 不 难 证明‘ ，有 一 圈 取