圍長為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.