吳麗蕓，田應(yīng)智

(新疆大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，新疆 烏魯木齊 830017)

0 引言

本文主要研究的是無自環(huán)和平行邊的有限無向圖.設(shè)G 是一個點集為V(G),邊集為E(G)的圖.對于V(G)中的每一個點v ∈V(G),N(v)=NG(v) 表示與點v 相鄰的所有的點的集合,并且dG(v)=|NG(v)| 稱為圖G 中點v 的度數(shù).δ(G) 表示圖G 的最小度.若對V(G) 中任意一點v 都有dG(v)=k,那么圖G 是k-正則的.此外,若V′?V(G),那么G[V′] 是G 的由V′導(dǎo)出的子圖.未定義的術(shù)語和符號可參閱文獻(xiàn)[1].

設(shè)S 是點集V(G)的一個子集,如果G-S 不連通,那么稱S 是圖G 的點割.圖G 的連通度κ(G) 是最小非負(fù)整數(shù)k,使得有S ?V(G) 滿足|S|=k 且G-S 不連通或G-S 是平凡圖K1.眾所知周,κ(G)≤δ(G).因此,當(dāng)κ(G)=δ(G) 時,我們稱G 是極大點連通的.若圖G 的每一個最小點割都是某個點的鄰點集,那么G 是超點連通的,或者簡稱為是super-κ 的.由定義可知,若圖G 是超點連通的,則G 一定是極大點連通的;反過來不一定成立,比如對于整數(shù)k ≥3,C2k是極大點連通的但不是超點連通的.

圖G1與G2的Kronecker 積圖是一個點集為V(G1×G2)=V(G1)×V(G2),邊集為E(G1×G2)={(u1,v1)(u2,v2):u1u2∈E(G1),v1v2∈E(G2)} 的圖.文獻(xiàn)[2] 研究了兩個完全圖的Kronecker 積圖的點連通度.文獻(xiàn)[3] 給出了二部圖和完全圖的Kronecker 積圖的點連通度.文獻(xiàn)[4] 和文獻(xiàn)[5] 分別獨立地證明了文獻(xiàn)[3] 中所提出的關(guān)于非平凡圖與一個完全圖的Kronecker 積圖的點連通度的猜想是成立的,即:κ(G×Kn)=min{nκ(G),(n-1)δ(G)},其中n ≥3.文獻(xiàn)[6] 證明了若G 是一個極大連通二部圖,那么G×Kn(n ≥3) 是超點連通的.文獻(xiàn)[7] 證明了兩個完全圖,路和完全圖,圈和完全圖的Kronecker 積圖是超點連通的.進(jìn)一步,文獻(xiàn)[8]證明了對任一極大連通圖G,除了G×Kn～=Km,m×K3(m ≥1),G×Kn(n ≥3) 是超點連通的.之后,文獻(xiàn)[9] 證明了G×Kn(n ≥3)不是超點連通的當(dāng)且僅當(dāng)κ(G×Kn)=nκ(G),其中n ≥3 或G×Kn～=Kl,l×K3(l>0).與Kronecker 積圖相關(guān)的其他結(jié)論可以參閱文獻(xiàn)[10-11].

除了Kronecker 積圖,乘積圖中受到關(guān)注最多的是笛卡爾積圖.與笛卡爾積圖相關(guān)的連通性的研究結(jié)果可以參閱文獻(xiàn)[12-18].

現(xiàn)在,列出一些關(guān)于Kronecker 積圖的性質(zhì)及結(jié)論.

性質(zhì)1[19]設(shè)G=G1×G2=(V(G),E(G)),那么

(1) |V(G)|=|V(G1)|·|V(G2)|,

(2) |E(G)|=2|E(G1)|·|E(G2)|,

(3) 對任一頂點(u,v)∈V(G),dG(u,v)=dG1(u)·dG2(v).

定理1[20]若G1與G2是連通圖,那么G1×G2是連通的當(dāng)且僅當(dāng)G1與G2中至少有一個圖包含奇圈.

1 主要結(jié)果

對于兩個圖G1和G2的Kronecker 積圖,記V1=V(G1)={u1,u2,···,um},V2=V(G2)={v1,v2,···,vn}.記Si={ui}×V2,i=1,2,···,m.將點(ui,vj) 簡記為ωij,i=1,2,···,m,j=1,2,···,n.那么Si={ωi1,ωi2,···,ωin},i=1,2,···,m.因此,很容易得到記Pm是有m 個點的路,Cn是有n 個點的圈.

引理1對于整數(shù)m ≥2 和奇數(shù)n ≥3,有κ(Pm×Cn)=2.

證明令G=Pm×Cn.當(dāng)m=2 時,可驗證G=P2×Cn～=C2n,所以κ(G)=κ(C2n)=2.

當(dāng)m ≥3 時.顯然,κ(G)≤δ(G)=δ(Pm)·δ(Cn)=2.

假設(shè)S 是G 的一個點割集且|S|<2,即|S|=1.不妨假設(shè)S={ωij}.

當(dāng)i=1 (或i=m) 時.因為Pm[{u2,···,um}]×Cn是連通的(當(dāng)i=m 時,Pm[{u1,···,um-1}]×Cn是連通的),并且S1-S 中的每一個點在S2中都存在鄰點(當(dāng)i=m 時,Sm-S 中的每一個點在Sm-1中都存在鄰點),那么G-S 是連通的,與假設(shè)矛盾.

當(dāng)i=2 (或i=m-1) 時.若m=3,由于P3[{u1,u2}]×Cn-S 與P3[{u2,u3}]×Cn-S 都是連通的,并且V(P3[{u1,u2}]×Cn-S)∩V(P3[{u2,u3}]×Cn-S)=S2-S,所以通過S2-S 可知P3×Cn-S 是連通的,與假設(shè)矛盾.若m ≥4,由于Pm[{u1,u2}]×Cn-S 與Pm[{u3,···,um}]×Cn都是連通的(當(dāng)i=m-1,Pm[{um-1,um}]×Cn-S與Pm[{u1,···,um-2}]×Cn都是連通的),并且S2-S 中的點在S3中都存在鄰點(當(dāng)i=m-1 時,Sm-1-S 中的點在Sm-2中都存在鄰點),那么G-S 是連通的,與假設(shè)矛盾.

當(dāng)3 ≤i ≤m-2 時,則m ≥5.由于Pm[{u1,···,ui-1}]×Cn與Pm[{ui+1,···,um}] ×Cn都是連通的,并且Si-S 中的每一個點在Si-1與Si+1中都存在鄰點,那么G-S 是連通的,與假設(shè)矛盾.

分析上述所有情況,得到的都是與假設(shè)矛盾的結(jié)論,所以G 中不存在點割集S 滿足|S|<2.因此,κ(G)≥2.

又因為已經(jīng)證明了κ(G)≤2,所以可得κ(G)=2.

接下來,要證明路和圈的Kronecker 積圖的超點連通性.當(dāng)m=2 時,P2×Cn同構(gòu)于C2n不是超點連通的.當(dāng)整數(shù)m ≥3,n=3 時,由文獻(xiàn)[7]中定理2.4 知Pm×C3是超點連通的.當(dāng)m=3,n 是大于等于5 的奇數(shù)時,取S={ω2j,ω2(j+1)} (當(dāng)j=n 時,j+1=1),此時P3×Cn-S (n ≥5) 是不連通且不包含孤立點的.因此,P3×Cn(n ≥5) 不是超點連通的.所以,下面主要考慮整數(shù)m ≥4 且奇數(shù)n ≥3 時的情況.

定理2若整數(shù)m ≥4,奇數(shù)n ≥3,那么G=Pm×Cn是超點連通的.

證明若整數(shù)m ≥4,n=3,由文獻(xiàn)[7] 中定理2.4 知Pm×C3是超點連通的.接下來,只需考慮整數(shù)m ≥4 且奇數(shù)n ≥5 時的情況.

假設(shè)G 不是超點連通的,則存在G 的一個點割集S 滿足|S|=2,使得G-S 不連通且不包含孤立點.不妨假設(shè)S={ωij,ωkl},且i ≤k.

情形1i=k.

當(dāng)i=1 (或i=m) 時.因為Pm[{u2,···,um}]×Cn是連通的(當(dāng)i=m 時,Pm[{u1,···,um-1}]×Cn是連通的),并且S1-S 中的每一個點在S2中都存在鄰點(當(dāng)i=m 時,Sm-S 中的每一個點在Sm-1中都存在鄰點),所以G-S 是連通的,與假設(shè)矛盾.

當(dāng)i=2 (或i=m-1) 時.由于Pm[{u3,···,um}]×Cn是連通的(當(dāng)i=m-1 時,Pm[{u1,···,um-2}]×Cn是連通的),并且S2-S 中的每一個點在S3中都存在鄰點(當(dāng)i=m-1 時,Sm-1-S 中的每一個點在Sm-2中都存在鄰點),那么Pm[{u2,u3,···,um}]×Cn-S 是連通的(當(dāng)i=m-1 時,Pm[{u1,···,um-2,um-1}]×Cn-S 是連通的).因為G-S 不包含孤立點,所以S1中的每一個點在S2-S 中都存在鄰點(當(dāng)i=m-1 時,Sm-S 中的每一個點在Sm-1中都存在鄰點).因此,G-S 是連通的,與假設(shè)矛盾.

當(dāng)3 ≤i ≤m-2 時,則m ≥5.由于Pm[{u1,···,ui-1}]×Cn與Pm[{ui+1,···,um}] ×Cn都是連通的,并且Si-S 中的每一個點在Si-1與Si+1中都存在鄰點,那么G-S 是連通的,與假設(shè)矛盾.

情形2i

此時|Si∩S|=1,|Sk∩S|=1.

當(dāng)i=1 時.由于κ(Pm×Cn)=2,且|Sk∩S|=1,那么Pm[{u2,···,um}]×Cn-ωkl是連通的.若k=2,因為S1-{ωij}中的每一個點在S2-{ωkl}中都存在鄰點,所以G-S 是連通的,與假設(shè)矛盾.若k ≥3,由于S1-{ωij}中的每一個點在S2中都存在鄰點,那么G-S 是連通的,與假設(shè)矛盾.

當(dāng)2 ≤i ≤m-2 時.由于κ(Pm×Cn)=2,且|Si∩S|=1,|Sk∩S|=1,那么Pm[{u1,···,ui}]×Cn-ωij與Pm[{ui+1,···,uk,···,um}]×Cn-ωkl都是連通的.若k=i+1,因為Si-{ωij} 中的每一個點在Sk-{ωkl} 中都存在鄰點,所以G-S 是連通的,與假設(shè)矛盾.若k ≥i+2,由于Si-{ωij} 中的每一個點在Si+1中都存在鄰點,那么G-S 是連通的,與假設(shè)矛盾.

當(dāng)i=m-1 時.因為i

引理2對于整數(shù)m ≥3 和奇數(shù)n ≥3,有κ(Cm×Cn)=4.

證明令G=Cm×Cn.當(dāng)m=3 或n=3 時,由文獻(xiàn)[7] 中引理2.5 知κ(Cm×Cn)=4.所以,接下來主要考慮大于等于4 的整數(shù)m 以及大于等于5 的奇數(shù)n 的情況.顯然,κ(G)≤δ(G)=δ(Cm)·δ(Cn)=4.

假設(shè)S 是G 的一個點割集且|S|<4,即|S|≤3.

由于Pm×Cn是G 的生成子圖,則κ(G)≥κ(Pm×Cn)≥2,從而|S|≥2.

當(dāng)|S|=2 時,若G-S 不連通,則Pm×Cn-S 也不連通.由定理2 可知S 一定是Pm×Cn中某個最小度點的鄰點集,那么G-S 是連通的,與G-S 不連通矛盾.因此,|S|>2,進(jìn)而|S|=3.

情形1|Si∩S|=|S|=3.

記Cm-ui～=因為是連通的，并且Si-S 中的每一個點在Si-1與Si+1(當(dāng)i=1 時,i-1=m;當(dāng)i=m 時,i+1=1) 中都存在鄰點,那么G-S 是連通的,與假設(shè)矛盾.

情形2|Si∩S|=1,|Sk∩S|=2.

不妨假設(shè)i

情形3|Si∩S|=1,|Sk∩S|=1,|Sp∩S|=1.

不妨假設(shè)i

由于m ≥4,那么uiuk,ukup,upui不可能都是Cm中的邊,不妨假設(shè)upui/∈E(Cm),則Pm[{uk+1,···,up,···,um,u1,···,ui-1}]×Cn-ωpq是連通的.

子情形3.1k=i+1.

若vjvl∈E(Cn),那么Pm[{ui,uk}]×Cn-{ωij,ωkl} 是連通的.當(dāng)p=k+1 時,因為Sp-{ωpq} 中的每一個點在Sk-{ωkl} 中都存在鄰點,所以G-S 是連通的,與假設(shè)矛盾.當(dāng)k+2 ≤p ≤i-2 時,由于Sk-{ωkl} 中的每一個點在Sk+1中都存在鄰點,那么G-S 是連通的,與假設(shè)矛盾.

若vjvl/∈E(Cn),那么Pm[{ui,uk}]×Cn-{ωij,ωkl} 不連通且不包含孤立點.因為Pm[{ui-1,ui}]×Cn-ωij是連通的,且Sk-{ωkl} 中的每一個點在Si-{ωij} 中都存在鄰點,所以Pm[{ui-1,ui,uk}]×Cn-{ωij,ωkl} 連通.由于Sk-S 中的每一個點在Sk+1-S (當(dāng)k=m 時,k+1=1) 中都存在2 個鄰點,而|Sk+1-S|=0 或1,那么G-S 是連通的,與假設(shè)矛盾.

子情形3.2k ≥i+2.

當(dāng)k=i+2 時,此時i+1=k-1.因為κ(Pm×Cn)=2,且|Si∩S|=1,|Sk∩S|=1,所以Pm[{ui,ui+1}]×Cn-ωij和Pm[{ui+1,uk}]×Cn-ωkl都是連通的.由于V(Pm[{ui,ui+1}]×Cn-ωij)∩V(Pm[{ui+1,uk}]×Cn-ωkl)=Si+1,那么通過Si+1可知Pm[{ui,ui+1,uk}]×Cn-{ωij,ωkl}是連通的.當(dāng)k ≥i+3 時,由定理2 可知Pm[{ui,···,uk}]×Cn是超點連通的,因為{ωij,ωkl}不是Pm[{ui,···,uk}]×Cn中某個最小度點的鄰點集,所以Pm[{ui,···,uk}]×Cn-{ωij,ωkl}是連通的.因此,當(dāng)|Pm[{ui,···,uk}]|≥3 時,Pm[{ui,···,uk}]×Cn-{ωij,ωkl} 是連通的.

若p=k+1.因為Sp-{ωpq} 中的每一個點在Sk-{ωkl} 中都存在鄰點,所以G-S 是連通的,與假設(shè)矛盾.

若k+2 ≤p ≤i-2.由于Sk-{ωkl} 中的每一個點在Sk+1中都存在鄰點,那么G-S 是連通的,與假設(shè)矛盾.

分析上述所有情況,得到的都是與假設(shè)矛盾的結(jié)論,所以G 中不存在點割集S 滿足|S|<4.因此,κ(G)≥4.

又因為已經(jīng)證明了κ(G)≤4,所以可得κ(G)=4.

接下來,刻畫的是圈和圈的Kronecker 積圖的超點連通性.當(dāng)m=3,n=3 時,由文獻(xiàn)[7] 中定理2.6 可知C3×C3是超點連通的.當(dāng)m=4,n=3 時,由文獻(xiàn)[9] 可知C4×C3～=K2,2×K3不是超點連通的.當(dāng)m=4,奇數(shù)n ≥5 時,取S=V(C4)×{vj},那么C4×Cn-S (n ≥5) 不連通且不包含孤立點.因此,C4×Cn(n ≥5) 不是超點連通的.所以,下面主要考慮大于等于5 的整數(shù)m 以及大于等于3 的奇數(shù)n 的情況.

定理3若整數(shù)m ≥5,奇數(shù)n ≥3,那么G=Cm×Cn是超點連通的.

證明若整數(shù)m ≥5,n=3,由文獻(xiàn)[7] 中定理2.6 知Cm×C3是超點連通的.接下來,只需討論整數(shù)m ≥5 且奇數(shù)n ≥5 時的情況.

假設(shè)G 不是超點連通的,則存在G 的一個點割集S 滿足|S|=4,使得G-S 不連通且不包含孤立點.

情形1 |Si∩S|=4.

記Cm-ui～=因為×Cn是連通的，并且Si-S 中的每一個點在Si-1與Si+1(當(dāng)i=1 時,i-1=m;當(dāng)i=m 時,i+1=1) 中都存在鄰點,那么G-S 是連通的,與假設(shè)矛盾.

情形2 |Si∩S|=1,|Sk∩S|=3.

不妨假設(shè)i

情形3 |Si∩S|=2,|Sk∩S|=2.

不妨假設(shè)i

子情形3.1 uiuk∈E(Cm).

記Cm-ui-uk～=因為×Cn是連通的,Si-S 中的每一個點在Si-1(當(dāng)i=1 時,i-1=m) 中都存在鄰點,且Sk-S 中的每一個點在Sk+1(當(dāng)k=m 時,k+1=1) 中都存在鄰點,那么G-S 是連通的,與假設(shè)矛盾.

子情形3.2 uiur,uruk∈E(Cm).

若Sr中存在某個點ωrt,該點在Si與Sk中的鄰點集恰巧分別是Si∩S 與Sk∩S,那么G-S 存在孤立點,與假設(shè)矛盾.因此,Sr中的每個點在Si∪Sk-S 中至少存在一個鄰點.因為|Si∩S|=2,|Sk∩S|=2,所以Sr中至多存在一個點ωrt′,該點在Si-S 或Sk-S 中不存在鄰點,不妨假設(shè)該點在Si-S 中不存在鄰點,那么該點在Sk-S 中存在鄰點.由于×Cn-(Si∩S)∪{ωrt′} 是連通的,Sk-S 中的每一個點在Sk+1(當(dāng)k=m 時,k+1=1) 中都存在鄰點,而且Sk-S 中存在ωrt′的鄰點,那么G-S 是連通的,與假設(shè)矛盾.若Sr中的每一個點在Si-S 中都存在鄰點,那么×Cn-(Si∩S) 是連通的.由于Sk-S 中的每一個點在Sk+1(當(dāng)k=m 時,k+1=1) 中都存在鄰點,那么G-S 是連通的,與假設(shè)矛盾.

子情形3.3 在Cm中,ui到uk的最短路長大于2.因為Pm[{ui+1,···,uk-1}]×Cn與Pm[{uk+1,···,um,u1,···,ui-1}]×Cn都是連通的,并且Si-S 中的每一個點在Si-1與Si+1(當(dāng)i=1 時,i-1=m;當(dāng)i=m 時,i+1=1)中都存在鄰點,Sk-S 中的每一個點在Sk-1與Sk+1(當(dāng)k=1 時,k-1=m;當(dāng)k=m 時,k+1=1) 中都存在鄰點,所以G-S 是連通的,與假設(shè)矛盾.

情形4 |Si∩S|=1,|Sk∩S|=1,|Sp∩S|=2

不妨假設(shè)i

情形5 |Si∩S|=1,|Sk∩S|=1,|Sp∩S|=1,|Sx∩S|=1.

不妨假設(shè)i

由于m ≥5,那么uiuk,ukup,upux,uxui不可能都是Cm中的邊,不妨假設(shè)uxui/∈E(Cm),則Pm[{up+1,···,ux,···,um,u1,···,ui-1}]×Cn-ωxy是連通的.

子情形5.1 k=i+1,p=k+1.

若vjvl∈E(Cn) 或vlvq∈E(Cn),那么Pm[{ui,uk}]×Cn-{ωij,ωkl} 或Pm[{uk,up}]×Cn-{ωkl,ωpq} 是連通的.因為Sp-{ωpq} 中的每一個點在Sk-{ωkl} 中都存在鄰點,且Si-{ωij} 中的每一個點在Sk-{ωkl} 中都存在鄰點,所以Pm[{ui,uk,up}]×Cn-{ωij,ωkl,ωpq} 是連通的.

當(dāng)x=p+1 (或i-1) 時,因為Sp+1-{ωxy} 中的每一個點在Sp-{ωpq} 中都存在鄰點(當(dāng)x=i-1 時,Si-1-{ωxy} 中的每一個點在Si-{ωij} 中都存在鄰點),所以G-S 是連通的,與假設(shè)矛盾.

當(dāng)p+2 ≤x ≤i-2時,因為Sp-{ωpq}中的每一個點在Sp+1中都存在鄰點,所以G-S是連通的,與假設(shè)矛盾.

若vjvl/∈E(Cn),且vlvq/∈E(Cn),那么Pm[{ui,uk}]×Cn-{ωij,ωkl} 和Pm[{uk,up}]×Cn-{ωkl,ωpq} 均不連通且不包含孤立點.當(dāng)j=q 時,Pm[{ui,uk,up}]×Cn-{ωij,ωkl,ωpq} 不連通且不包含孤立點.當(dāng)j/=q 時,因為Sp-{ωpq} 中的每一個點在Sk-{ωkl} 中都存在鄰點,并且Sp-{ωpq} 可將Pm[{ui,uk}]×Cn-{ωij,ωkl} 中的各連通分支連接起來,所以Pm[{ui,uk,up}]×Cn-{ωij,ωkl,ωpq} 是連通的.

由于已經(jīng)討論了Pm[{ui,uk,up}]×Cn-{ωij,ωkl,ωpq} 是連通時的情況,所以接下來我們分析j=q 時,Pm[{ui,uk,up}]×Cn-{ωij,ωkl,ωpq} 不連通且不包含孤立點的情況.

當(dāng)x=p+1(或x=i-1)時,因為Pm[{ui-1,ui}]×Cn-ωij是連通的(當(dāng)x=i-1 時,Pm[{up,up+1}]×Cn-ωpq是連通的),所以通過Si-1可將Pm[{ui,uk,up}]×Cn-{ωij,ωkl,ωpq}中的各連通分支連接起來(當(dāng)x=i-1 時,通過Sp+1可將Pm[{ui,uk,up}]×Cn-{ωij,ωkl,ωpq}中的各連通分支連接起來),從而可以得到Pm[{ui-1,ui,uk,up}]×Cn-{ωij,ωkl,ωpq} 是連通的(當(dāng)x=i-1 時,可以得到Pm[{ui,uk,up,up+1}]×Cn-{ωij,ωkl,ωpq} 是連通的).由于Si-1將連通的Pm[{up+1,···,ux,···,um,u1,···,ui-1}]×Cn-ωxy與Pm[{ui-1,ui,uk,up}]×Cn-{ωij,ωkl,ωpq} 連接起來(當(dāng)x=i-1 時,Sp+1將連通的Pm[{up+1,···,ux,···,um,u1,···,ui-1}]×Cn-ωxy與Pm[{ui,uk,up,up+1}]×Cn-{ωij,ωkl,ωpq} 連接起來),那么G-S 是連通的,與假設(shè)矛盾.

當(dāng)p+2 ≤x ≤i-2 時,因為Pm[{up,up+1}]×Cn-ωpq是連通的,所以通過Sp+1可將Pm[{ui,uk,up}]×Cn-{ωij,ωkl,ωpq} 中的各連通分支連接起來.因此,Pm[{ui,uk,up,up+1}]×Cn-{ωij,ωkl,ωpq} 是連通的.由于V(Pm[{ui,uk,up,up+1}]×Cn-{ωij,ωkl,ωpq})∩V(Pm[{up+1,···,ux,···,um,u1,···,ui-1}]×Cn-ωxy)=Sp+1,那么通過Sp+1可得G-S 是連通的,與假設(shè)矛盾.

子情形5.2 k=i+1,p ≥k+2.

此時|Pm[{uk,···,up}]|≥3,由引理2 的證明中的子情形3.2 可知,此時|Pm[{uk,···,up}]|≥3,由引理2 的證明中的子情形3.2 知Pm[{uk,···,up}] ×Cn-{ωkl,ωpq} 是連通的.由于Si-{ωij} 中的每一個點在Sk-{ωkl} 中都存在鄰點,那么Pm[{ui,uk,···,up}]×Cn-{ωij,ωkl,ωpq} 是連通的.

若x=p+1 (或i-1),因為Sp+1-{ωxy} 中的每一個點在Sp-{ωpq} 中都存在鄰點(當(dāng)x=i-1 時,Si-1-{ωxy} 中的每一個點在Si-{ωij} 中都存在鄰點),所以G-S 是連通的,與假設(shè)矛盾.

若p+2 ≤x ≤i-2,因為Sp-{ωpq} 中的每一個點在Sp+1中都存在鄰點,所以G-S 是連通的,與假設(shè)矛盾.

子情形5.3 k ≥i+2,p=k+1.

由Cm的對稱性,類似于子情形5.2,可得G-S 是連通的,與假設(shè)矛盾.

子情形5.4 k ≥i+2,p ≥k+2.

此時|Pm[{ui,···,uk}]|≥3,|Pm[{uk,···,up}]|≥3,那么Pm[{ui,···,uk}]×Cn-{ωij,ωkl}與Pm[{uk,···,up}]×Cn-{ωkl,ωpq} 都是連通的.因為V(Pm[{ui,···,uk}]×Cn-{ωij,ωkl})∩V(Pm[{uk,···,up}]×Cn-{ωkl,ωpq})=Sk-{ωkl},所以通過Sk-{ωkl} 可知Pm[{ui,···,uk,···,up}]×Cn-{ωij,ωkl,ωpq} 是連通的.

若x=p+1 (或i-1),因為Sp+1-{ωxy} 中的每一個點在Sp-{ωpq} 中都存在鄰點(當(dāng)x=i-1 時,Si-1-{ωxy} 中的每一個點在Si-{ωij} 中都存在鄰點),所以G-S 是連通的,與假設(shè)矛盾.

若p+2 ≤x ≤i-2,因為Sp-{ωpq} 中的每一個點在Sp+1中都存在鄰點,所以G-S 是連通的,與假設(shè)矛盾.

通過上述情形討論可得到與假設(shè)矛盾的結(jié)論,所以假設(shè)不成立.因此,G 是超點連通的.