Vol.16 No.3 李明楚等：图中有边不交的3个1一因子的一个新充分条件 291· 好有2条边连结G,和G,(因为G为2-连通)。设这两条边为e,=uv,(4,∈V(G,),:∈V(G) =1,2,如果G,和G2的顶点数为偶数，则类似上面的证明可得到一个1~因子N使 得e,eN,于是G-N'是2-连通的.因此设G,和G,的顶点数为奇数，则对于G中任何 一点u≠4，u。都有u与V(G)中所有点在G中都相邻，否则，若存在一点山≠4,2使得与 G,中某一点不相邻，则d()≤n-3.显然在V(G)中可找到一个点≠，，使得d()≤n 且E(G),于是d()+d()≤2n-3矛盾.同量可证对任何一点v≠，，v必与(G)中 所有点在G中都相邻，因此当，44∈E(G⑤时G[V(G)】和G[V(G)]为完全图.故G就 是附图中的(e)所示的图. (b)IV(GI=n,则IV(G)川=n. 对于任意一点v∈V(G),V(G)中必有一点u使得uwE(G),从而dc(@)≥2n-2-1-d(四 ≥n-3≥V(G)I/2+2,故δ(G)≥1V(G)1/2+2,同理6(G)≥1V(G)川/2+2，因此G1和G2是 Hamilton连通.用类似于(a)的证明方法，可以证明引理成立. 2)G'只有一个分支含Y中点（不妨设为G),. 由引理4可知1V(G)川≤n-1,而且G[V(G)】为完全图.显然V(G)PX.对于G,中任意 一点u,在G,中必找到一上点v使得uv生E(G),从而d(+d()≥2n-2,于是d。,(a)≥2n-2 -1-d()≥2n-3HV(G1V(G)1-3≥1V(G)l/2+1,从而G2为Hamilton连通.因δ(G)≥3，故1V (G)川≥4.如果N中恰好有2条边e,=4,u(u,∈V(G),v,∈V(G),i=1,2)连结G与G2.显然当 442∈E(G)时，G[V(G)]为完全图，否则，若存在一点≠，∈V(G)使得d(u)≤|V(G-2, 那么在G,中必找到一点≠u,4使得E(G,而且d()+d()≤|V(G)-1+V(G)1-2 ≤2n-3矛盾.这时G就是附图中(e)所示的图.如果N中有至少3条边连结G和G,这 时不难证明G中有一个1-因子N使得G-N”为2-连通. 情形2.G'是连通的. 如果G'中有割边，则将割边去掉，就化为情形1的证明，因此设G中不含割边·设哈 是G中的割点，G。=G-,则不难证明G。恰好有两个分支G,和G2用情形1中的证明方 法，可证G,和G2都是Hamiltion连通，且δ(G,)≥V(G,)l/2+1(=1,2).因为G为2-连通，故 在N中必有一条边e=(,∈V(G)∈V(G)连结G,和G,.因G没有割边，故分别 在G,和G,都有两个邻点（设4山，∈V(G),∈V(G,),且44a,hv,,,t5∈E(G).不妨设 4≠4，≠，那么在G,中有一条Hamilton路P,=PG,(u,42)连结4，和4，在G2中有一条 Hamilton路P,-Pc,他，)连结和，于是P=PU{kvoz}UP,是G中的Hamilton路. 在P中选取一个1-因子N,我们得到G-N'是2-连通的.因此情形2被证.故引理被证. 从引理5的证明过程中可知下列引理成立， 引理6.设G是2n(n≥10)阶2-连通Oe-(-2)型图，δ(G≥4，而且G不是图1中所示 的图之一且N是G的一个1-因子，如果x(G-M≥7，则k(G-N)≥2. 2定理的证明 定理：设G是2n(n≥10)阶2-连通Oe-(-2)型图且δ(G)≥4，则G有边不交的一个 Hamilton圈和一个因子除非G是附图中所示的图之一，李 明楚等 图中有边不交 的 个 一 因子 的一个新充分条件 好有 条边连结 ， 和 因为 为 一 连通 。 设这两条边 为 ， ‘ ， 任 ， ‘ 份 ， ， ， 如 果 ， 和 的顶 点 数 为偶 数 ， 则类 似 上 面 的 证 明 可 得 到 一 个 一 因 子 丫 使 得 ， 醉 ， 于 是 一 ‘ 是 一 连通 的 因此设 ， 和 的顶 点数为奇 数 ， 则 对于 中任 何 一点 护 ， “ ， 都有 与 中所有点在 中都相邻 ， 否 则 ， 若存在 一点 。 笋 ， 使得 与 ， 中某 一 点不相邻 ， 则 簇。 一 显 然 在 中可 找到 一 个 点 笋 ， 姚 ， 使得 毛。 且 ’ 句 ， 于是 叼 一 矛 盾 同量 可 证 对 任 何 一 点 。 笋 ， 姚 ， 。 必 与 乡中 所有点在 中都相邻 ， 因此 当 姚 ， 任 句 时 【袱 』和 【 刃 为完 全 图 故 就 是 附 图 中的 所示 的 图 卜 ， 则 对于 任意一点 份 ， 办中必 有 一 点 使得 砖 ， 从而 ‘ 一 一 一 一 ， 故 占 ， 同理 ， 因 此 ， 和 是 而 连通 用类 似于 的证 明方法 ， 可 以 证 明引理 成立 ‘ 只 有 一个分 支含 中点 不妨设 为 由引理 可 知 簇 一 ， 而且 〕 为完全 图 显然 。 对于 中任意 一点 ， 在 ， 中必 找到 一上 点 使得 举 ， 从而 一 ， 于 是 一 一 一 一 一 卜 ， 从而 为 而 连通 因 ， 故 如 果 中恰 好有 条 边 ， ‘叭 任 ， ， ， 任 办 ， ， 连 结 与炕 显 然 当 任￡ 时 ， 为完全 图 ， 否 则 ， 若存在 一 点 笋 ， 姚 任 使得 。 簇 办一 ， 那 么在 ， 中必 找 到一 点 。 护 ， 使得 砖 ， 而且 。 叼簇 一 户一 一 矛盾 这 时 就是 附 图 中 所示 的 图 如 果 中有 至 少 条 边 连 结 ， 和 ， 这 时不难证 明 中有 一 个 一 因子 ’ 使得 一 ， 为 一 连通 情形 ‘ 是连通 的 如果 ’ 中有 割边 ， 则将割边 去掉 ， 就化 为情 形 的证 明 因此设 ’ 中不 含 割 边 设 此 是 ’ 中的割点 ， 。 ’ 一 ， 则不难证 明 恰好有 两个分支 和 用情 形 中 的证 明方 法 ， 可 证 ， 和 都是 连通 ， 且占 ‘ ， 因为 为 一 连 通 ， 故 在 中必有 一 条边 。 。 。 任 ， 任 刃 连结 ，和 乓 因 ’ 没有割边 ， 故 分别 在 和 都有两个邻点 设 ， 任 ， ， 姚任 ， 且 ， 。 ， 。 ， 姚 任 · 不妨设 。 笋 ， 笋 ， 那 么 在 中有 一 条 路 ， ， ， 连 结 ， 和 ， 在 中有 一 条 口 路 凡一 凡 ， 办连 结 ， 和 姚 ， 于 是 一 口 日 是 中 的 路 · 在 尸 中选取 一个 一 因子 从 我 们 得 到 一 ， 是 一连 通 的 因此 情 形 被 证 故 引理 被证 从 引理 的证 明过程 中可 知下列 引理成立 引理 设 是 。 。 阶 一 连通 一 一 型 图 ， 占 叨 〕 ， 而且 不是 图 中所 示 的 图之一且 是 的一个 一 因子 如果 城 一 叼 妻 ， 则 一 定理 的证 明 定 理 设 是 阶 一 连 通 一 卜 型 图且 占 妻 ， 则 有 边 不 交 的 一 个 而 圈和 一个 因子 除非 是 附 图中所示 的 图之一