图的边连通度的一些结果

王晓丽，张国志

（晋中学院数学系，山西榆次，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 和中的所有边构成的集合。