一類brace中的thin邊

林夢丹, 盧福良

（閩南師范大學數學與統計學院, 福建 漳州 363000）

1 研究背景

只考慮有限簡單圖，除非另有說明，沿用文獻[1]的標號.圖的匹配是指圖的邊子集，其中任意兩條邊都不相鄰.當匹配飽和圖中所有的頂點，稱為完美匹配.設圖G為至少兩個頂點的連通圖，若其任意一邊都屬于某個完美匹配，稱圖G為匹配覆蓋圖.令X是V(G)的非空真子集=V(G) -X，G的邊割是一個端點在X中，另一端點在中的所有邊，記為?(X).

在匹配覆蓋圖中，若邊割C:=?(X)，滿足對任何完美匹配M，都有|M∩C| =1，稱C為緊割.當X或-X只包含一個點時，邊割C總是緊割，稱這樣的緊割為平凡的，其余的稱為非平凡的.假設匹配覆蓋圖G中沒有非平凡緊割，若G是二部圖，稱G為brace，反之稱為brick.對二度點v的雙收縮是指將點集{v,v1,v2}收縮為一個點，再去掉重邊的操作，其中：v1和v2是點v的兩個鄰點.在圖G中重復對二度點的雙收縮得到的圖，記為.若G中無二度點，G即為設圖G是brace，若仍是brace，則e為圖G的thin邊.反之，e為圖G的non-thin邊.特別地，在brickG中，若G-e仍為匹配覆蓋圖，且最多有一個brick，稱邊e為圖G的b-invariant邊.若X和A為圖G的點子集，記X∩A為XA.

Mccuaig[2]證明每個brace 都包含一條thin 邊，進一步證明所有brace 都可以由三種brace 生成.Carvalho等[3]證明每個brace至少包含兩條thin邊.基于上述結果的啟發，進一步研究了brace中的thin邊，證明若C4為一個brace中的一個四圈，且該圈中包含兩個相鄰三度點的，則C4中至少包含一條thin邊.

Carvalho等[3]提出了下列猜想.

猜想1每個頂點數至少為6的brace有兩條不相鄰的thin邊.

猜想2存在正整數c，使得每個braceG有c|V(G)|條thin邊.

類似地，在非二部圖中也有考慮一類特殊thin 邊—b-invariant 邊.若2 邊連通三正則圖G沒有非平凡的3-邊割，稱圖G為基本4連通的.Kothari等[4]證明了除Peterson圖外，每個基本4連通三正則non-near-bipartite brickG至少有|V(G)|條b-invariant邊，并提出猜想：除外，每個4-邊連通三正則near-bipartite brickG有條b-invariant邊.Lu等[5]證明了上述猜想，并證明了該下界是可達的.

對上述兩個猜想，到目前為止，還沒有相關結果.主要原因在于在brace中沒有較好的辦法來找出thin邊，特別在圖的頂點數較多時（Carvalho 等[3]證明每個brace 至少存在兩條thin 邊，但沒有給出如何找到這些thin邊，即使是找到一條thin邊）.在一類特殊的結構中，確定了brace中thin邊在該結構的存在性.

2 預備知識

Hall證明了二部圖中存在完美匹配的充要條件.

定理1[1]設G是具有二分類(A,B)的二部圖，則G存在完美匹配當且僅當|A| =|B|，且|N(S)| ≥|S|，對于所有S?A成立.

關于brace有以下等價條件

定理2[6-7]設G是具有二分類(A,B)的匹配覆蓋二部圖，記為G(A,B)，下列條件等價：

1）G是brace；

2）任意a1,a2∈A，任意b1,b2∈B，G-a1-a2-b1-b2有完美匹配；

3）任意X?A，1 ≤|X| ≤|A| -2，有|N(X)| ≥|X| +2.

根據定理2有以下推論.

推論1若圖G是頂點數至少為6的brace，有δ(G) ≥3.

推論2令G(A,B)是brace，X?V(G),|X∩B| ≤|B| -2，且N(XB) ?XA，

1）若|XA| =|XB|，則X=?，

2）若|XA| =|XB| +1，則XB=?.

設G(A,B)是匹配覆蓋二部圖，X是G的點子集，且|X|為奇數.顯然，|XA|和|XB|不相等，不妨設|XA| ＞|XB|，記XA為X+，記XB為X-.

Lovasz[6]刻畫了匹配覆蓋二部圖中的緊割.

定理2[6]設G(A,B)是匹配覆蓋二部圖，?(X)是圖G中的割，|X|為奇數，則?(X)為緊割當且僅當

1）|X+| =|X-| +1，

2）?(X)中每條邊和X-中的點不關聯.

推論6假設e是braceG中的non-thin 邊，則存在X?V(G)(|X| ≥5,|| ≥5且為奇數)，使得?(X)是G-e的非平凡緊割，且E[XA,B] ={e}，其中：E[XA,B]是一個端點在XA中，另一個端點在B中的所有邊.

由推論3 可知，在braceG(A，B)中，對于每條non-thin 邊e，都存在G中一個邊割?(X)，使得?(X) -e是G-e的一個非平凡緊割，稱這樣的割?(X)為關聯邊e的一個S-割.non-thin 邊e的結構如圖1 所示.涉及的所有圖中，兩個端點都在X的邊不畫出.注意，G中的一條non-thin邊可能關聯許多不同的S-割.

圖1 e是non-thin邊Fig.1 e is non-thin edge

3 主要結果及證明

定理3若C4=u1v1u2v2u1為braceG(A,B)中的一個四圈，且該圈中包含兩個相鄰三度點，則C4中至少包含一條thin邊.

證明下面將采用反證法，利用推論3 中brace 含有non-thin 邊的特殊結構導出矛盾，從而完成對定理的證明.

假設結論不成立.即u1v2,u2v2,u1v1,u2v1都為G中non-thin 邊.不失一般性，設d(u1) =d(v2) =3，{u1,u2}?A，并設?(X),?(Y),?(Z),?(W)分別是關聯u1v2,u2v2,u1v1,u2v1的S-割.

根據N(X2B) ?X2A∪{u2}和N(Y2B) ?Y2A∪{u1},有N(X2Y2B) ?X2Y2A.由定理1，有|N(X2Y2B)|≥|X2Y2B|，從而有|X2Y2A|≥|X2Y2B|.根據式（2）～（3），有|X1Y1A|≥|X1Y1B|.根據d(v2) =3,N(v2){u1}?X2A和N(v2){u2}?Y2A，有N(v2){u1,u2}?X2Y2A，從而有|X2Y2|≠0.根據N(X2Y2B) ?X2Y2A和推論4，有

如圖2所示.

圖2 u1v2,u2v2是non-thin邊Fig.2 u1v2,u2v2are non-thin edges

假設|X2Y2A| ≥|X2Y2B| +3.根據式（2）～（3），有|X1Y1A| ≥|X1Y1B| +1.另一方面，根據N(X1Y1A) ?X1Y1B∪{v1}，有|N(X1Y1A)| ≤|X1Y1B| +1.根據|X1Y1A| +2 ≤|N(X1Y1A)|，可得|X1Y1A| ≤|X1Y1B| -1，矛盾.結合式（4）有以下兩種情況.

情況1|X2Y2A| =|X2Y2B| +2.

根據式（1）～（3），有|X2Y1A| =|X2Y1B| -1，|X1Y1A| =|X1Y1B|和

其中：N(X1Y1A) ?X1Y1B∪{v1}.根據推論2，有|X1Y1| =0.根據N(Z2B) ?Z2A∪{u2}，有N(X2Y2Z2B) ?X2Y2Z2A.根據N(X2Y2Z2B) ?X2Y2Z2A和定理1，有

同理，有|X1Y2Z1A| ≤|X1Y2Z1B|和

根據d(u1) =3,N(u1){v1}?X1B,N(u1){v2}?Y2B,N(u1){v2}?Z1B，有N(u1){v1,v2}?X1Y2Z1B，即|X1Y2Z1| ≠0.根據N(X1Y2Z1A) ?X1Y2Z1B和推論2，可知|X1Y2Z1A| ≠|X1Y2Z1B|，進一步有

根據式（5）和式（8），有

同理，由式（6）可得到|X2Y2Z1A| ≤|X2Y2Z1B| +2和

如圖3所示.

圖3 u1v2,u2v2,u1v1是non-thin邊且|X2Y2 A| =|X2Y2B| +2Fig.3 u1v2,u2v2,u1v1 are non-thin edges and |X2Y2 A| =|X2Y2B| +2

假設|X2Y2Z2A| ≥|X2Y2Z2B| +3.根據|Z2A| =|Z2B| +1 和式（10），有|X1Y2Z2A| ≤|X1Y2Z2B| -1，與式（9）矛盾.故結合式（6）有以下3種情況.

情況1.1|X2Y2Z2A| =|X2Y2Z2B|.

根據N(X2Y2Z2B) ?X2Y2Z2A，由推論4（1），有|X2Y2Z2| =0，從而可得|X2Y2Z1A| =|X2Y2Z1B| +2.假設|X2Y1Z1A| ≤|X2Y1Z1B| -3.根據|Z1A| =|Z1B| -1，得|X1Y2Z1A| ≥|X1Y2Z1B|，與式（8）矛盾.結合式（7）有以下3種情況.

如果|X2Y1Z1A| =|X2Y1Z1B| -2，根據|Z1A| =|Z1B| -1，有|X1Y2Z1A| =|X1Y2Z1B| -1，從而有|X1Y2Z2A| =|X1Y2Z2B|.根據N(X1Y2Z1A) ?X1Y2Z1B和N(X1Y2Z2B) ?X1Y2Z2A，由推論4 知，有|X1Y2Z2| =0和|X1Y2Z1A| =|X1Y2Z1B| -1，進一步有|X1| =1，與推論3矛盾.如果|X2Y1Z1A| =|X2Y1Z1B| -1，則|X2Y1Z2A| =|X2Y1Z2B|.根據N(X2Y1Z1A) ?X2Y1Z1B，由推論2 知，|X2Y1Z1|=|X2Y1Z1B|=1，存在|X2Y1Z2|=0，從而有|Y1|=1，與推論3 矛盾.如果|X2Y1Z1A| =|X2Y1Z1B|，可得|X2Y1Z1| =0 和|X2Y1Z2A| =|X2Y1Z2B| -1.由N(X2Y1Z2A) ?X2Y1Z2B∪{v1}知，|N(X2Y1Z2A)| ≤|X2Y1Z2B| +1，與定理2矛盾.

情況1.2|X2Y2Z2A| =|X2Y2Z2B| +1.

如果|X2Y1Z1A| ≤|X2Y1Z1B| -2，易得|X1Y2Z1A| ≥|X1Y2Z1B| +3，與式（8）矛盾；如果|X2Y1Z1A| =|X2Y1Z1B| -1，易得|Y1| =1，與推論3 矛盾；如果|X2Y1Z1A| =|X2Y1Z1B|，易得|X2Y1Z1A| ≤|X2Y1Z1B| +1，與定理2矛盾.

情況1.3|X2Y2Z2A| =|X2Y2Z2B| +2.

假設|X2Y1Z1A| ≤|X2Y1Z1B| -1.可以得到|X1Y2Z1A| ≥|X1Y2Z1B|，與式（8）矛盾，故|X2Y1Z1A| =|X2Y1Z1B|，從而有|X1Y2Z1A| =|X1Y2Z1B| -1.根據N(X1Y2Z1A) ?X1Y2Z1B，由推論2，有|X1Y2Z1| =|X1Y2Z1B| =1.同理，有|X2Y1Z1| =0.為書寫方便，記K1=X1Y2Z2，K2=X1Y2Z1，K3=X2Y1Z2，K4=X2Y2Z1和K5=X2Y2Z2.

根據N(W1A) ?W1B∪{v2}，有N(K1W1A) ?K1W1B，進一步有

同理，有|K3W1A| ≤|K3W1B|和

根據N(u2){v1,v2}?K3W1B和推論2，有

根據N(u1){v1,v2}?K2B，有|K2| =|K2W2| =|K2W2B| =1.由|W1A| =|W1B| -1，式（11）～（13），有|K4W1A| ≥|K4W1B|.根據N(v2){u1,u2}?K4W1A，得到|K4W1A| ≥|K4W1B| +1.否則|K4W1A| =|K4W1B|，與定理2矛盾，如圖4所示.

圖4 u1v2,u2v2,u1v1,u2v1是non-thin邊且|X2Y2Z2 A| =|X2Y2Z2B| +2Fig.4 u1v2,u2v2,u1v1,u2v1 are non-thin edges and |X2Y2Z2 A| =|X2Y2Z2B| +2

假設|K5W2A| ≥|K5W2B| +2.易證|K1W1A| ≥|K1W1B| +1，與式（11）矛盾.故結合式（12）有以下兩種情況.

情況a|K5W2A| =|K5W2B|.

如果|K4W1A| ≥|K4W1B|，有|K1W1A| ≥|K1W1B| +1，與式（11）矛盾.

如果|K4W1A| =|K4W1B| +1.若|K3W1A| ≤|K3W1B| -3，可以得到|K1W1A| ≥|K1W1B| +1，與式（11）矛盾；若|K3W1A| =|K3W1B| -2，易證|K1| =|X1| =1，與推論6 矛盾；若|K3W1A| =|K3W1B| -1，易證|K3W1| =|K3W1B| =1，從而有|K3| =|Y1| =1，與推論6矛盾.

同理，如果|K4W1A| =|K4W1B| +2，和式（11）或推論6矛盾.

情況b|K5W2A| =|K5W2B| +1.

假設|K4W1A| ≥|K4W1B| +2.可得|K1W1A| ≥|K1W1B| +1，與式（11）矛盾.反之，|K4W1A| =|K4W1B| +1.若|K3W1A| ≤|K3W1B| -2，有|K1W1A| ≥|K1W1B| +1，與式（11）矛盾；若|K3W1A| =|K3W1B| -1，易證|K1| =|X1| =1，與推論3矛盾.

情況2|X2Y2A| =|X2Y2B| +1.

根據式（1）～（3），有|X2Y1A| =|X2Y1B| -1，|X1Y1A| =|X1Y1B| -1和

根據N(X2Y2B) ?X2Y2A，由推論2 知，|X2Y2| =|X2Y2A| =1.根據N(v2){u1,u2}?Z1A，有N(v2){u1,u2}?X2Y2Z1A，從而有|X2Y2| =|X2Y2Z1A| =1.根據N(X1Y2Z2B) ?X1Y2Z2A，由定理1，有

同理，有

根據式（14）～（15），有

同理，有

根據|Z2A| =|Z2B| +1，式（15）和式（18）有

如圖5所示.

圖5 u1v2,u2v2,u1v1是non-thin邊且|X2Y2 A| =|X2Y2B| +1Fig.5 u1v2,u2v2,u1v1are non-thin edges and |X2Y2 A| =|X2Y2B| +1

假設|X2Y1Z2A| ≥|X2Y1Z2B| +2.根據|Z1A| =|Z1B| -1，有|X1Y2Z2A| ≤|X1Y2Z2B| -2，與式（15）矛盾.結合式（19）有以下兩種情況.

情況2.1|X2Y1Z2A| =|X2Y1Z2B| +1.

如果|X1Y1Z1A| ≤|X1Y1Z1B| -2，易證|X1Y2Z1A| ≥|X1Y2Z1B| +1，與式（17）矛盾；如果|X1Y1Z1A| =|X1Y1Z1B| -1，有|X1Y1Z1| =|X1Y1Z1B| =1，從而有|N(X1Y2Z1A)| ≤|X1Y2Z1B| +1，與定理2 矛盾.故|X1Y1Z1A| =|X1Y1Z1B|，可以得到|X1Y1Z1| =0.

易證|X1Y2Z2W2| =|X1Y2Z2W2A| =1 和|X1Y2Z1W2| =|X1Y2Z1W2B| =1.令X1Y2Z1W2B={x}，根據N(X1Y2Z1W2B)?X1Y2Z2W2A∪{u1}，有d(x) ≤2，與推論3矛盾.

情況2.2|X2Y1Z2A| =|X2Y1Z2B|.

根據|N(X2Y1Z2B)| ≤|X2Y1Z2A| +1，由定理2 知，|X2Y1Z2| =0.如果|X1Y1Z1A| ≤|X1Y1Z1B| -3，由|Z1A| =|Z1B| -1，有|X1Y2Z1A| ≥|X1Y2Z1B| +1，與式（17）矛盾；如果|X1Y1Z1A| =|X1Y1Z1B| -1，易證|X1Y1Z1| =|X1Y1Z1B|=1,|X2Y1Z1A| =|X2Y1Z1B|.根據|N(X2Y1Z1A)| ≤|X2Y1Z1B| +1，由推論4（2）知，|X2Y1Z1| =|X2Y1| =|X2| =1，與推論3矛盾；如果|X1Y1Z1A| =|X1Y1Z1B|，易證|X2Y1Z1| =0，從而有|X2Y1| =|X2| =1，與推論3矛盾.

故|X1Y1Z1A| =|X1Y1Z1B| -2.由推論2，易證|X2Y1Z2| =0 和|X1Y2Z2| =0.為書寫方便，記F1=X1Y2Z1，F1=X1Y2Z1,F2=X1Y1Z1,F3=X1Y1Z2,和F5=X2Y2Z1.容易得到|F3W2A| ≤|F3W2B| -1，

如圖6所示.

圖6 u1v2,u2v2,u1v1,u2v1是non-thin邊且|X2Y1Z2 A| =|X2Y1Z2B|Fig.6 u1v2,u2v2,u1v1,u2v1 are non-thin edges and |X2Y1Z2 A| =|X2Y1Z2B|

假設|F4W1A| ≤|F4W1B| -2.從而有|F1W1A| ≥|F1W1B| +1，與式（21）矛盾.故結合式（20）有以下兩種情況.

情況a|F4W1A| =|F4W1B|.

易得|F4W2A| =|F4W2B|.根據N(F4W2B) ?F4W2A，由推論2 知，|F4W2| =0，存在|F4W1| =0，故|X2| =1，與推論3矛盾.

情況b|F4W1A| =|F4W1B| -1.

如果|F3W1A| =|F3W1B|，易證|F3W2| =|F3W2A| =1，存在|F3W1| =0，故|Z2| =1，與推論3矛盾.反之，|F3W1A| ≤|F3W1B| -1，根據|W1A| =|W1B| -1，有|F1W1A| ≥|F1W1B| +1，與式（21）矛盾.

所以，C4中至少包含一條thin邊.

若C4中存在兩個不相鄰的三度點但無兩個相鄰的三度點，則定理7結論不成立.如圖7所示，u1和u2為兩個不相鄰的三度點，且u1v2,u2v2,u1v1,u2v1是non-thin邊.

圖7 一個例子Fig.7 An example