圖的邊連通度的一些結(jié)果

王曉麗，張國(guó)志

（晉中學(xué)院數(shù)學(xué)系，山西榆次，030619）

G是一個(gè)簡(jiǎn)單圖，用V(G)和E(G)分別表示圖G的頂點(diǎn)集和邊集。用n=|V(G)|和m=|E(G)|分別表示圖G的頂點(diǎn)數(shù)（也叫階）和邊的數(shù)目。G的頂點(diǎn)v的度d(v)指G中與v相關(guān)聯(lián)的邊的條數(shù)。δ是圖G的最小度。設(shè)V(G)={v1,v2,…,vn}，則稱為圖G的度序列。G的邊連通度λ(G)是產(chǎn)生一個(gè)平凡圖或不連通圖需要移去的邊的最少數(shù)目,移去的最少數(shù)目的邊稱為最小邊割。不連通圖的λ(G)=0。由邊連通度的定義有λ≤δ。文中沒(méi)給出的記號(hào)和術(shù)語(yǔ)參見(jiàn)文獻(xiàn)[1]。

證明設(shè)F 是G 的最小邊割。若G 不連通，則F=?。因F 是G 的最小邊割，故|F|=λ 且G-F 至少包含兩個(gè)連通分支。設(shè)G-F 的連通分支為G1,G2,…,Gp(p ≥2)。

斷言1p=2。假設(shè)p ≥3。[V(G2),V(G3)]表示兩個(gè)端點(diǎn)分別在V(G2)和V(G3)中的所有邊構(gòu)成的集合，則F[V(G2),V(G3)]是G 的比F 邊數(shù)更少的邊割，與F是G的最小邊割矛盾，所以G -F只有兩個(gè)連通分支 G1,G2。記 S=V(G1)，，且，即兩個(gè)端點(diǎn)分別在S 和中的所有邊構(gòu)成的集合。