王曉麗,張國(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)成的集合。