(1、2.安順學(xué)院數(shù)理學(xué)院, 貴州 安順561000)

設(shè)G是一個(gè)k-連通圖,T?V(G) 是V(G)的一個(gè)子集。如果G-T至少有兩個(gè)連通分支，就稱T為G的一個(gè)點(diǎn)割集，簡(jiǎn)稱點(diǎn)割。進(jìn)一步地，若|T|=k，則稱T為G的一個(gè)k-點(diǎn)割或最小點(diǎn)割。

設(shè)G是一個(gè)k(≥2)-連通圖，e=uv∈E(G)是G中的一條邊。對(duì)邊e進(jìn)行如下操作：先去掉邊e，再將e的兩個(gè)端點(diǎn)u，v合并為一個(gè)頂點(diǎn)，然后將由此產(chǎn)生的所有的“二重邊”用一條“單邊”來(lái)替代，這樣，得到一個(gè)新圖G′。顯然，由此得到的新圖G′仍然是一個(gè)簡(jiǎn)單圖。稱e的這種運(yùn)算為e的收縮(或者稱為“收縮邊e”)。如果收縮k(≥2)-連通圖G中的邊e后仍然得到一個(gè)k-連通圖，那么稱e為G的一條k-可收縮邊，簡(jiǎn)稱可收縮邊。否則，稱e為的一條不可收縮邊。一個(gè)不含任何可收縮邊的非完全k-連通圖稱為收縮臨界k-連通圖。設(shè)G是一個(gè)非完全k(≥2)-連通圖。顯然，若邊e=uv∈E(G)是G的一條不可收縮邊，當(dāng)且僅當(dāng)存在G中的一個(gè)最小點(diǎn)割T使得{u，v}?T。

設(shè)G是一個(gè)k-連通圖，e是G中的一條不可收縮邊，于是存在G中的一個(gè)k-點(diǎn)割T，使得e∈E(G[T])。此時(shí)若C是G-T的一個(gè)連通分支，則稱C為G中一個(gè)關(guān)于e的連通分支。設(shè)Y?E(G)為E(G)的一個(gè)非空子集，T為G中的一個(gè)k-點(diǎn)割，若E(G[T]) 中含有Y中的某一條邊，這時(shí)稱G-T的任一個(gè)連通分支C為G中關(guān)于Y的連通分支。

若一個(gè)圖G沒有子圖同構(gòu)于圖H，稱G是一個(gè)“不含H的圖”。同時(shí)稱H為G的一個(gè)“禁用子圖”。

1 一些相關(guān)結(jié)論

1981年，Thomassen[2]證明了下面的定理：

定理1 一個(gè)不含三角形的k-連通圖含有一條k-可收縮邊。

Ando等[5]證明了如下定理：

(i) 若δ(G)≥k+1，則G中每一個(gè)點(diǎn)都關(guān)聯(lián)一條k-收縮邊；

(ii) 若G中任意兩個(gè)相鄰的點(diǎn)x，y都滿足dG(x)+dG(y)≥2k+1，則G中的每一個(gè)k度點(diǎn)都關(guān)聯(lián)一條k-可收縮邊。

由定理4(ii)，我們立即可推出下面的結(jié)論：

這里需要說明的是，盡管Ando等[5]在證明過程中假定了k≥4為偶數(shù)，實(shí)際上當(dāng)k>4為奇數(shù)時(shí)，該證明(對(duì)命題2)仍然有效，命題2的結(jié)論仍然正確。故在命題2中對(duì)k(≥4)不再限制其奇偶性。實(shí)際上，對(duì)命題 2，可以將整數(shù)考慮到k≥3。于是，進(jìn)一步地，有下面的結(jié)論(在此不妨稱其為定理 5)。

2 定理 5 的證明

斷言1 若dG(x)=3，則|E(x)∩M|≥1。若|E(x)∩M|=1，設(shè)xy∈(E(x)∩M)，則xy是G中的一條3-可收縮邊。

定理 5 的證明。

令F=E(x)∩M。則當(dāng)dG(x)≥4時(shí)，由題設(shè)條件總有|F|≥2。當(dāng)dG(x)=3時(shí)， 若|F|=1，由斷言1可知x關(guān)聯(lián)一條可收縮邊，這時(shí)，結(jié)論正確。于是，當(dāng)dG(x)=3時(shí)，總假定|F|=3。這樣,無(wú)論何種情形，總有|F|≥2。

證明E(x)中至少含有一條3-可收縮邊：

|A∪S|≥|NG(a)∪NG(b)|=|NG(a)|+

|NG(b)|-|NG(a)∩NG(b)|≥3+3-1=5。即,

ASABTBA∩BS∩BA∩BA∩TS∩TA∩TA∩BS∩BA∩B

圖1

首先證明A?T。