围长为5的3-正则有向图的不交圈

蔡晓霞 何志红

摘 要：2017年Ngo Dac Tan提出了一个猜想：对每一个整数g≥3，只有有限多个围长为g的3-正则有向图不含不同长度的不交圈。g=3和g=4的情况在2017年和2020年分别被证明。本文主要证明了围长为5的3-正则有向图具有两个不同长度的不交圈的存在性问题，给出了几个充分条件。

关键词：3-正则有向图;围长;不交圈

中图分类号：O175.5  文献标识码：A  文章编号：1673-260X（2021）04-0001-05

1 引言与预备知识

在整篇文章中，只考虑有限的简单的有向图，特殊标注的地方除外。本文提到的有向图的其他定义可以参考J. Bang-Jensen[1]的论述。

令D是一个有向图。V（D）和A（D）分别表示它的点集合和弧集合，通常情况下也可以简记为V和A。如果（u，v）∈A，则称v是u的一个出邻点，记u的所有出邻点为ND+（u），u的出度是|ND+（u）|，记为dD+（u），即dD+（u）=|ND+（u）|，D的最小出度min{dD+（u）|u∈V}。类似地，称u是v的一个入邻点，记v的所有入邻点为ND-（v），v的入度是|ND-（v）|，记为dD-（v），即dD-（v）=|ND-（v）|，D的最小入度为min{dD-（v）|v∈V}。如果U？哿V，那么由U生成的D的子有向图记为D[U]。

令D=（V，A）是一个有向图。弧（u，v）∈A简记为uv，D中的圈和路通常指有向圈和有向路，D中的不交圈指点不交圈，如果C=v0，v1，…，vm-1，v0是D中长度为m的一个圈，那么viCvj的序列为vi，vi+1，vi+2，…，vj。viCvj既可以理解为是一条路，也可以理解为是一个点集合。围长是指D中最短圈的长度。如果有向图D中有dD+（v）=dD-（v）=k，且对V中任意的点都成立，那么我们称D是k-正则图。有向图D=（V，A）的最小出度为d，如果对于弧集合A中的每一条弧uv都存在一个度为d的点x（x∈V）使得xu∈A，xv∈A，那么称有向图D为d-弧控制图。如果有向图D中不包含圈，那么我们称D是无圈图。

近几年，有向图中不交圈的存在条件是有向图中的研究热点。Thomassen[2]证明了最小出度至少是3的有向图包含两个不交圈。Henning和Yeo[3]提出了三个猜想，第一个猜想是最小出度至少是4的有向图包含两个不同长度的不交圈，第二个猜想是一个阶数足够大的3-正则有向图包含两个不同长度的不交圈，第三个猜想是每3-正则二部有向图包含两个不同长度的不交圈。Henning， Gao[3-5]在文献中分别用不同的有向图证明了第一个猜想。后来，Lichiardopol[6]完全证明了第一个猜想。第二个猜想Ngo Dac Tan[7]在文献中有反例证明是不成立的，但这篇文章中构造了一类无限的，不包含不同长度的不交圈的3-正则有向图，定义如下：对任意的整数n≥2，点集合V（D2n2）={ui，vi|i=0，1，…，n-1}，弧集合A（D2n2）={uivi，viui，uiui+1，uivi+1，viui+1，vivi+1|i=0，1，…，n-1}，有向图记为D2n2=（V（D2n2），A（D2n2））。同样在这篇文献中证明了第三个猜想对于不包含哈密尔顿路3-正则有向图是成立的。Ngo Dac Tan[8]对3-弧控制有向图包含两个不同长度的不交圈进行了证明。Ngo Dac Tan[9，10]在文献中又分别对围长为3和围长为4的3-正则有向图就行研究，给出了不交圈的存在条件。本文主要对围长为5的3-正则有向图进行研究，假设有向图D不包含不同长度的不交圈，证明了他在某些条件下的一般性结论，对研究围长为5的3-正则有向图不交圈的存在条件具有重要意义。

2 主要结论

定理2.1 D是一个围长为5的3-正则有向图，并且D中不包含不同长度的不交圈。令C′是D中长度为5的圈。D1=D-V（C′），P=p1，…，ps是D1中一条路。若ps在V（P）中有出邻点，则ps-4（s≥5）是ps在V（P）中唯一的出邻点。类似地，若p1在V（P）中有入邻点，则p5（s≥5）是p1在V（P）中唯一的入邻点。

证明 如果ps有一个出邻点pi，pi∈V（P）且i≠s-4，则C1=pi，pi+1，…，ps，pi是D1中长度不同于5的一个圈。因此C′和C1是D中两个不同长度的不交圈，与假设矛盾。因此，p4（s≥4）是p1在V（P）中唯一的出邻点。类似地，也能证明p5（s≥5）是p1在V（P）中唯一的入邻点。

定理2.2 D是一个围长为5的3-正则有向图，并且D中不包含不同长度的不交圈。令C′=x，y，z，u，w，x是D中的一个5-圈。D1=D-V（C′）。并且D1中没有点的三个出邻点都在都在V（C′）中，则

（1）D1中恰有五个点在V（C′）中分别恰有两个出邻点。

（2）D1中拥有出邻点在V（C′）中的点在D1中构成一个五圈。

证明 令T是D1中有出邻点在V（C′）中的所有点的集合。因为D是围长为5的3-正则有向图，所有很显然T≠？覫。令P=a1，a2，…，as是D1中起点a1∈T的最长的一条路。由|V（P）|的最大性，as在D1中的所有出邻点一定都在V（P）中。再由定理2.1可知，as最多有一个出邻点在V（P）中，所以as在V（C′）中最少有兩个出邻点。因为D1中没有点的三个出邻点都在V（C′）中，所以as恰有两个出邻点在V（C′）中。也就是说，as-4一定是as的一个出邻点。因此，C′0=as-4，as-3，as-2，as-1，as，as-4是D中的一个圈。

因为a1∈T，所以a1至少有一个出邻点在V（C′）中。不失一般性，我们可以假设x是a1的一个出邻点，由定理2.1我们知道a1至多有一个入邻点在V（P）中。因此，a1至少有两个入邻点在V（D）＼V（P）中。

假设a1≠as-4。如果a1有两个入邻点在V（C′）中，记这两个点为n1和n2，则有C3=a1xC′n1，a1，C4=a1xC′n2，a1，可以看出C3和C4是两个不同长度的圈，前面得到C′0=as-4，as-3，as-2，as-1，as，as-4，显然C3和C4都不与C′0相交。所以，要么C3和C′0是D中两个不同长度的不交圈，要么C4和C′0是D中两个不同长度的不交圈。与假设矛盾。如果a1有至多一个入邻点在V（C′）中，那么它一定有一个入邻点在V（D）＼（V（P）∪V（C′））中。令X=x1，x2，…，xt是D2（D2=D-（V（P）∪V（C′）））中终点xt是a1的入邻点的最长的一条路。由定理2.1得x1至多有一个入邻点在V（P）∪V（X）中。因此，x1至少有两个入邻点在V（C′）中，我们记这两个点为m1，m2，那么我们有C5=a1，xC′m1，a1，C6=a1，xC′m2，a1。可以看出C5和C6是两个不同长度的圈，并且C5和C6都不与C′0相交。因此，要么C5和C′0是D中两个不同长度的不交圈，要么C6和C′0是D中两个不同长度的不交圈，与假设矛盾。

因此，a1？芊as-4。这也就意味着D1中起点在T的最长路的长度为4。因为as∈T，A1=as，as-4，as-3，as-2，as-1是D1中长度为4的路并且起点as在T中，所以A1是D1中起点在T中的最长的路。因此，as-1一定有两个出邻点在V（C′）中，通过对路A2=as-1，as，as-4，as-3，as-2;A3=as-2，as-1，as，as-4，as-3;A4=as-3，as-2，as-1，as，as-4做重复类似的论证我们可以得到as-2，as-3，as-4在V（C0）中有两个出邻点。从而as，as-1，as-2，as-3，as-4是D1中有出邻点在V（C0）中的所有点（因为恰有10条弧从D1到V（C′）），并且他们中的每一个点都恰有两个出邻点在V（C′）中。由前面我们知道C′0=as-4，as-3，as-2，as-1，as，as-4是一个圈，所以他们构成一个5-圈。

由定理2.2马上得到下面的定理2.3。

定理2.3 D是一个围长为5的3-正则有向图，并且D中不包含不同长度的不交圈。令C′=x，y，z，u，w，x是D中的一个5-圈。D1=D-V（C′）。并且D1中没有点的三个入邻点都在V（C′）中，则

（1）D1中恰有五个点在V（C′）中分别恰有两个入邻点。

（2）D1中拥有入邻点在V（C′）中的点在D1中构成一个5-圈。

若D1中有一个点x1的三个入邻点都在V（C′）中。令xj（xj∈V（D1），xj≠x1）有一个入邻点在V（C′）中。记A1，j={x1，xj}。假设r1，r2是D1中仅有的有三个出邻点在V（C′）中的点。记B={r1，r2}。

定理2.4 D是一个围长为5的3-正则有向图，并且D中不包含不同长度的不交圈。令C′=x，y，z，u，w，x是D中的一个5-圈。D1=D-V（C′）。D1中有一个点x1，它的三个入邻点都在V（C′）中。那么对任意的不动子集A1，j，D1中有两条从A1，j到B的不交路。

证明 已知r1，r2是D1中僅有的有三个出邻点在V（C′）中的点，因为恰有10条弧从V（D1）到V（C′），所以D1中有出邻点在V（C′）中的点可以分为下面三种情况：（1）r3，r4各恰有两个出邻点在V（C′）中。（2）r3，r4，r5，r6各恰有一个出邻点在V（C′）中。（3）r3有两个出邻点在V（C′）中，r4，r5各恰有一个出邻点在V（C′）中。我们假设在（1）中r3不是r4的出邻点，r4也不是r3的出邻点且r3的入邻点不是r4的入邻点。同样地，r4的入邻点不是r3的入邻点。假设在（3）中r3不是r4，r5的出邻点。要证对任意的不动子集A1，j，D1中有两条从A1，j到B的不交路，那么先来证对于任意的点x∈D1，D1中有条从A1，j到B的路是避开x的。

首先假设x=x1。令P=a1，a2，…，dl且d1=xj是D1中起点为xj的最长的一条路。因为D的围长为5，不难发现xj至少有一个出邻点在V（D1）中。因此，l≥2。由定理2.1可知，dl一定至少有两个出邻点在V（C′）中。因此，要么dl∈B，要么dl是情况（1）中的r3（或者r4，不失一般性，我们假设dl=r3）或者情况（3）中的r3。因为x1的三个入邻点都在V（C′）中，所以x1？埸V（P）。如果dl∈B，则P是D1中从A1，j到B避开x1的一条路。现在我们考虑情况（1）中的r3即dl=r3，这种情况下先来看dl-1，因为dl-1≠r1，r2，r3且由已知条件dl-1≠r4，所以dl-1没有出邻点在V（C′）中。因为dl-1至多有两个出邻点在V（P）中，所以它一定有一个出邻点g∈V（D1＼V（P）。则P′=d1，d2，…，dl-1，g是D1中起点为xj的最长的一条路。因此g一定有至少两个出邻点在V（C′）中。因为g≠r3，由已知条件g≠r4，所以g∈B。因此，P′是D1中从A1，j到B避开x1的一条路。

下面我们考虑情况（3）中的r3即dl=r3（r3有两个出邻点在V（C′）中，r4，r5各恰有一个出邻点在V（C′）中）。同样先来看dl-1，由已知dl-1≠r4，r5，因为dl-1至多有两个出邻点在V（P）中，所以dl-1一定有一个出邻点g′∈V（D1＼V（P）。那么P"=d1，d2，…，dl-1，g′是D1中起点为xj的最长的一条路。因此，g′一定至少有两个出邻点在V（C′）中，因为g′≠r3，所以g′∈B。因此，P"是D1中从A1，j到B避开x1的一条路。

接下来假设x≠x1。D2=D-（V（C′）∪{x}），则x1∈V（D2）。令T是D1中起点为x1的所有路的集合。因为x1至少有一个出邻点在D2中，所以显然T≠？覫。现在我们来证明T中至少有一条路包含B＼{x}中的一个点。

采用反证法，假设T中没有路包含B＼{x}中的一个点，令V′={v∈V（D2）|v是D2中能从x1到达的点}。接下来需要先证明D2[V′]是无圈的。选择一个点r∈B＼{x}，那么r至少有两个出邻点在V（C′）中，记这两个点为s1，s2。因为T中没有路包含B＼{x}中的一个点，所以一定有r？埸V′。假设Y=y1，y2，…，ys是D2中终点ys=r的最长的一条路。因为r至少有两个入邻点在D2中，所以显然s≥2。由定理2.1可知y1至少有两个入邻点在V（C′）∪{x}中。因此，y1至少有一个入邻点在V（C′）中，记这个点为s3。令P1=r，s1，C′，s3;P2=r，s2，C′，s3，y1，记C1=Y∪P1，C2=Y∪P2，则C1，C2是V（Y）∪V（C′）中两个不同长度的圈。因为x1到不了Y中的点，否则x1能到达r，与前提条件矛盾，所以V′∩V（Y）∪V（C′））=？覫。因此，若D2[V′]中有个圈C3，则要么C1和C3是D中两个不同长度的不交圈，要么C2和C3是D中两个不同长度的不交圈，与假设矛盾。因此，D2[V′]是无圈的。

假设E=e1，e2，…，ei是T中最长的一条路，其中e1=x1，显然i≥2。由定理2.1可知，至少有两个出邻点在V（C′）中，因为S中没有路包含B＼{x}中的点，且D2[V′]是无圈的，所以不难发现ei？埸B＼{x}，ei有两个出邻点在V（C′）中并且ei是x的一个入邻点。因此，由前面提到的情况（1）和情况（3），下面需要考虑关于ei的两种情况。（I）：ei=r3（r3，r4各恰有两个出邻点在V（C′）中）。因为r1，r2有3个出邻点在V（C′）中，所以他们不在V（E）中，又因为r4不是r3的出邻点，所以ei-1≠r1，r2，r3，r4，这意味着ei-1没有出邻点在V（C′）中。此外，如果ei-5是ei-1的一个出邻点，那么我们能在D2[V′]中得到一个圈ei-5，ei-4，ei-3，ei-2，ei-1，ei-5，与D2[V′]是无圈的矛盾。因此，ei-5不是ei-1的出邻点，那么ei-1一定有一个出邻点s∈V（D2）＼V（E），则E′=e1，e2，…，ei-1，s是T中最长的一条路。因为D2[V′]是无圈的，所以s没有出邻点在V（E′）中。那么s一定有三个出邻点在V（C′）∪{x}中。又因为s≠r4并且s≠r3，由此断定s∈B＼{x}，这与前面假设的T中没有路包含B＼{x}中的一个点矛盾。再来看（II）：ei=r3（r3有两个出邻点在V（C′）中，r4，r5各恰有一个出邻点在V（C′）中）。同样地，因为r1，r2有3个出邻点在V（C′）中，所以他们不在V（E）中。又因为r4，r5不是r3的出邻点，所以ei-1≠r1，r2，r3，r4，r5，这意味着ei-1没有出邻点在V（C′）中。因为D2[V′]是无圈的，所以ei-5不是ei-1的出邻点。那么ei-1一定有一个出邻点s∈V（D2）＼V（E），则E′=e1，e2，…，ei-1，s是T中最长的一条路，并且s的出邻点没有在V（E′）中的。那么s一定有三个出邻点在V（C′）∪{x}中，所以s∈B＼{x}，这与假设的T中没有路包含B＼{x}中的一个点矛盾。因此，假设T中没有路包含B＼{x}中的一个点是错误的，这也就意味着存在一条路是从x1到B且避开x的。

综上证明出对于任意的點x∈V（D1），V（D1）中都有一条从A1，j到B避开x的一条路。再由Menger's Theorem，V（D1）中有两条从A1，j到B的不交路。

由定理2.3可知，D1中有5个点x1，x2，x3，x4和x5，他们有入邻点在C′中，并且他们中每个点都恰有两个入邻点在C′中。此外，他们还构成一个5-圈。不失一般性，假设这个5-圈为C=x1，x2，x3，x4，x5，x1，我们记Ai，j={xi，xj}（i，j∈{1，2，3，4，5}）。

引理2.1[10] D是一个围长为4的3-正则有向图，并且D中不包含不同长度的不交圈。令C0=a0，b0，c0，d0，d0是D中的一个四圈。D′=D-V（C0）。假设={xi，xj}和B={r1，r2}是D′的子集合，且在V（D′）中有两条从Ai，j到Q1的不交路。则D-A（D′）不包含从Ai，j到Q1的路Q1，Q2，Q3，Q′1，Q′2，Q′3，这六条路具有以下性质：

（a）Q1和Q2不同长度且都不与Q3相交。

（b）Q′1和Q′2不同长度且都不与Q′3相交。

（c）Q1和Q2的起点都是u1，终点都是xi，而Q3的起点是u2，终点都是xj。

（d）要么Q′1和Q′2的起点都是u1，终点都是xj，而Q3的起点是u2，终点都是xi，要么Q′1和Q′2的起点都是u2，终点都是xi，而Q3的起点是u1，终点都是xj。

引理2.1的结果同样适用于围长为5的情况，证明过程不在这里赘述。

定理2.5 D是一个围长为5的3-正则有向图，并且D中不包含不同长度的不交圈。令C′=x，y，z，u，w，x是D中的一个5-圈且D1=D-V（C′）。D1中有一个点x1，它的三个入邻点都在V（C′）中。则如果D1中有一个点的三个出邻点都在V（C′）中，那么D1中这样的点是唯一的。

证明 假设D1中有一个点r1的三个出邻点都在V（C′）中，此外D1还拥有另一个点r2，它的三个出邻点也都在V（C′）中。由定理2.4可知剩下的D1中有出邻点在V（C′）中的点可以分为三种情况，并且对任意的不动子集A1，j，D1中有两条从A1，j到B的不交路。

下面对V（C′）中的点重新命名，C′=a0，b0，c0，d0，e0，a0。不失一般性可以假设ND+（r1）={a0，b0，c0}。此外，根据r2出邻集中的点和x1入邻集中的点，选择D1中一个合适的点xj（xj≠x1），且xj有入邻点在V（C′）中，x1，xj构成集合A1，j。则可以证明在D-A（D1）中存在从B到A1，j的路H1，H2，H3，H′1，H′2，H′3，这六条路具有以下性质：

（a）H1和H2不同长度且都不与H3相交。

（b）H′1和H′2不同长度且都不与H′3相交。

（c）H1和H2的起点都是r1，终点都是x1，而H3的起点是r2，终点都是xj。

（d）H′1和H′2的起点都是r1，终点都是xj，而H3的起点是r2，终点都是x1。

情况一 ND+（r2）={a0，b0，c0}（resp.，ND+（r2）={b0，c0，d0}，ND+（r2）={b0，c0，e0}。

如果ND-（x1）={a0，c0，d0}或ND-（x1）={b0，c0，d0}或ND-（x1）={c0，d0，e0}，那么我们从D1中选b0的一个出邻点xj（xj≠x1），x1，xj构成集合A1，j，并且能够得到：H1=r1，c0，x1;H2=r1，c0，d0，x1;H3=r2，b0，xj;H′1=r1，b0，xj;H′2=r1，a0，b0，xj;H′3=r2，c0，x1。

如果ND-（x1）={a0，b0，d0}或ND-（x1）={a0，d0，e0}，那么我們从D1中选a0的一个出邻点xj（xj≠x1），x1，xj构成集合A1，j，并且能够得到：H1=r1，a0，x1;H2=r1，c0，d0，x1;H3=r2，b0，xj;H′1=r1，b0，xj;H′2=r1，a0，b0，xj;H′3=r2，c0，x1。

如果ND-（x1）={a0，b0，c0}或ND-（x1）={b0，c0，e0}，那么我们从D1中选a0的一个出邻点xj（xj≠x1），x1，xj构成集合A1，j，并且能够得到：H1=r1，b0，x1;H2=r1，b0，c0，x1;H3=r2，d0，e0，a0，xj（resp.，H3=r2，e0，a0，xj;H3=r2，a0，xj）;H′1=r1，a0，xj;H′2=r1，c0，d0，e0，a0，xj;H′3=r2，b0，x1。

如果ND-（x1）={a0，c0，e0}或ND-（x1）={a0，b0，e0}，那么我们从D1中选b0的一个出邻点xj（xj≠x1），x1，xj构成集合A1，j，并且能够得到：H1=r1，a0，x1;H2=r1，c0，d0，e0，x1;H3=r2，b0，xj;H′1=r1，b0，xj;H′2=r1，a0，b0，xj;H′3=r2，c0，d0，e0，x1。

如果ND-（x1）={b0，d0，e0}，那么我们从D1中选b0的一个出邻点xj（xj≠x1），x1，xj构成集合A1，j，并且能够得到H1=r1，c0，d0，x1;H2=r1，c0，d0，e0，x1;H3=r2，b0，xj;H′1=r1，b0，xj;H′2=r1，a0，b0，xj;H′3=r2，c0，d0，x1。

情况二 ND+（r2）={a0，b0，d0}（resp.，ND+（r2）={a0，b0，e0}。

如果ND-（x1）={a0，b0，c0}或ND-（x1）={a0，b0，d0}或ND-（x1）={a0，b0，e0}，那么我们从D1中选e0的一个出邻点xj（xj≠x1），x1，xj构成集合A1，j，并且能够得到：H1=r1，a0，x1;H2=r1，a0，b0，x1;H3=r2，d0，e0，xj（resp.，H3=r2，e0，xj）;H′1=r1，c0，d0，e0，xj;H′2=r1，b0，c0，d0，e0，xj;H′3=r2，a0，x1。

如果ND-（x1）={a0，d0，e0}或ND-（x1）={b0，d0，e0}或ND-（x1）={c0，d0，e0}，那么我们从D1中选b0的一个出邻点xj（xj≠x1），x1，xj构成集合A1，j，并且能够得到：H1=r1，c0，d0，x1;H2=r1，c0，d0，e0，x1;H3=r2，b0，xj;H′1=r1，b0，e0，xj;H′2=r1，a0，b0，xj;H′3=r2，d0，x1（resp.，H′3=r2，e0，xj）。

如果ND-（x1）={a0，c0，d0}或ND-（x1）={a0，c0，e0}，那么我们从D1中选e0的一个出邻点xj（xj≠x1），x1，xj构成集合A1，j，并且能够得到：H1=r1，c0，x1;H2=r1，b0，c0，x1;H3=r2，d0，e0，xj（resp.，H3=r2，e0，xj）;H′1=r1，c0，d0，e0，xj;H′2=r1，b0，c0，d0，e0，xj;H′3=r2，a0，x1。

如果ND-（x1）={b0，c0，d0}或ND-（x1）={b0，c0，e0}，那么我们从D1中选a0的一个出邻点xj（xj≠x1），x1，xj构成集合A1，j，并且能够得到：H1=r1，b0，x1;H2=r1，b0，c0，x1;H3=r2，a0，xj;H′1=r1，a0，xj;H′2=r1，c0，d0，e0，a0，xj;H′3=r2，b0，x1。

情况三 ND+（r2）={a0，c0，d0}（resp.，ND+（r2）={a0，c0，e0}）。

如果ND-（x1）={a0，b0，c0}或ND-（x1）={a0，b0，d0}或ND-（x1）={a0，b0，e0}，那么我们从D1中选c0的一个出邻点xj（xj≠x1），x1，xj构成集合A1，j，并且能够得到H1=r1，a0，x1;H2=r1，a0，b0，x1;H3=r2，c0，xj;H′1=r1，c0，xj;H′2=r1，b0，c0，xj;H′3=r2，a0，x1。

如果ND-（x1）={a0，d0，c0}或ND-（x1）={b0，d0，e0}或ND-（x1）={c0，d0，e0}，那么我们从D1中选b0的一个出邻点xj（xj≠x1），x1，xj构成集合A1，j，并且能够得到：H1=r1，c0，d0，x1;H2=r1，c0，d0，e0，x1;H3=r2，a0，b0，xj;H′1=r1，b0，xj;H′2=r1，a0，b0，xj;H′3=r2，c0，d0，x1。

如果ND-（x1）={a0，c0，d0}或ND-（x1）={b0，c0，d0}，那么我们从D1中选b0的一个出邻点xj（xj≠x1），x1，xj构成集合A1，j，并且能够得到：H1=r1，c0，x1;H2=r1，c0，d0，x1;H3=r2，a0，b0，xj;H′1=r1，b0，xj;H′2=r1，a0，b0，xj;H′3=r2，c0，x1。

如果ND-（x1）={a0，c0，e0}或ND-（x1）={b0，c0，e0}，那么我们从D1中选b0的一个出邻点xj（xj≠x1），x1，xj构成集合A1，j，并且能够得到：H1=r1，c0，x1;H2=r1，c0，d0，e0，x1;H3=r2，a0，b0，xj;H′1=r1，b0，xj;H′2=r1，a0，b0，xj;H′3=r2，c0，x1。

情况四 ND+（r2）={a0，d0，e0}（resp.，ND+（r2）={b0，d0，e0}，ND+（r2）={c0，d0，e0}）。

如果ND-（x1）={a0，d0，c0}或ND-（x1）={a0，d0，d0}或ND-（x1）={a0，d0，e0}，那么我们从D1中选d0的一个出邻点xj（xj≠x1），x1，xj构成集合A1，j，并且能夠得到：H1=r1，a0，x1;H2=r1，a0，b0，x1;H3=r2，d0，xj;H′1=r1，c0，d0，xj;H′2=r1，b0，c0，d0，xj;H′3=r2，e0，a0，x1。

如果ND-（x1）={a0，c0，d0}或ND-（x1）={b0，c0，d0}或ND-（x1）={c0，d0，e0}，那么我们从D1中选b0的一个出邻点xj（xj≠x1），x1，xj构成集合A1，j，并且能够得到H1=r1，c0，x1;H2=r1，c0，d0，x1;H3=r2，e0，a0，b0，xj;H′1=r1，b0，xj;H′2=r1，a0，b0，xj;H′3=r2，d0，x1。

如果ND-（x1）={b0，c0，e0}或ND-（x1）={b0，d0，e0}，那么我们从D1中选d0的一个出邻点xj（xj≠x1），x1，xj构成集合A1，j，并且能够得到：H1=r1，b0，x1;H2=r1，a0，b0，x1;H3=r2，d0，xj;H′1=r1，c0，d0，xj;H′2=r1，b0，c0，d0，xj;H′3=r2，e0，x1。

如果ND-（x1）={a0，c0，e0}，那么我们从D1中选d0的一个出邻点xj（xj≠x1），x1，xj构成集合A1，j，并且能够得到：H1=r1，a0，x1;H2=r1，b0，c0，x1;H3=r2，d0，xj;H′1=r1，c0，d0，xj;H′2=r1，b0，c0，d0，xj;H′3=r2，e0，x1。

当ND-（x1）={a0，d0，e0}，ND+（r2）={a0，d0，e0}时，我们从D1中选e0的一个出邻点xj（xj≠x1），x1，xj构成集合A1，j，并且能够得到：H1=r1，c0，d0，x1;H2=r1，b0，c0，d0，x1;H3=r2，e0，xj;H′1=r1，c0，d0，e0，xj;H′2=r1，b0，c0，d0，e0，xj;H′3=r2，a0，x1。

当ND-（x1）={a0，d0，e0}，ND+（r2）={b0，d0，e0}时，我们从D1中选b0的一个出邻点xj（xj≠x1），x1，xj构成集合A1，j，并且能够得到：H1=r1，a0，x1;H2=r1，c0，d0，x1;H3=r2，b0，xj;H′1=r1，b0，xj;H′2=r1，a0，b0，xj;H′3=r2，e0，x1。

当ND-（x1）={a0，d0，e0}，ND+（r2）={c0，d0，e0}时，从B到A1，j的路H1，H2与H3会存在交点，所以结论成立必须当ND+（r2）={c0，d0，e0}时，ND-（x1）≠{a0，d0，e0}。

参考文献：

〔1〕J. Bang-Jensen， G. Gutin， Digraphs： Theory， Algorithms and Applications[M]. Springer， London， 2001.

〔2〕C.Thomassen， Disjoint cycles in digraphs[J]. Combinatorica， 1983， 3： 393-396.

〔3〕M.A. Henning， A.Yeo， Vertex disjoint cycles of different length in digraphs[J]. SIAM J. Discrete Math， 2012， 26： 687-694.

〔4〕Y.Gao， D.Ma， Disjoint cycles with different length in 4-arc-dominated digraphs[J]. Oper.Res.Lett， 2013， 41： 650-653.

〔5〕Ngo Dac Tan， Vertex disjoint cycles of different length in d-arc-dominated digraphs[J]. Oper.Res.Lett， 2014， 42： 351-354.

〔6〕N.Lichiardopol， Proof of a conjecture of Henning and Yeo on vertex-disjoint directed cycles[J]. SIAM J. Discrete Math， 2014， 28： 1618-1627.

〔7〕Ngo Dac Tan， On vertex disjoint cycles of different lengths in 3-regular digraphs[J]. Discrete Math， 2015， 338： 2485-2491.

〔8〕Ngo Dac Tan， 3-arc-dominted digraphs [J]. SIAM J. Discrete Math， 2010， 24： 1153-1161.

〔9〕Ngo Dac Tan， On 3-regular digraphs without vertex disjoint cycles of different lengths[J]. Discrete Math， 2017， 340： 1933-1943.

〔10〕Ngo Dac Tan， On 3-regular digraphs of girth 4[J]. Discrete Math， 2020， 343： 1-13.