圖的邊連通度的一些結果

王曉麗，張國志

（晉中學院數學系，山西榆次，030619）

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

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

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