引理1 引理1:设E是边割集,则p(GE)=p(G)+1 证明:如果p(GE)>p(G)+1,则E不是边 割集,因为不满足定义中的极小性.# 癱说明:点割集无此性质 《集合论与图论》第16讲 16
《集合论与图论》第16讲 16 引理1 引理1: 设E’是边割集,则p(G-E’)=p(G)+1. 证明: 如果p(G-E’)>p(G)+1, 则E’不是边 割集, 因为不满足定义中的极小性. # 说明: 点割集无此性质
引理2 引理2:设E是非完全图G的边割集, λ(G)=El,GE的2个连通分支是G1,G2则 存在ueV(G)vEVG2,使得(V)EE(G) 秦证明:(反证)否则入(G)=E =|VG)XNVG2)2(G川+(G2)-1=n-1, 与G非完全图相矛盾!# 说明:a1b≥1→(a-1)(b-1)=ab-a-b+120 ab≥a+b-1 《集合论与图论》第16讲
《集合论与图论》第16讲 17 引理2 引理2:设E’是非完全图G的边割集, λ(G)=|E’|,G-E’的2个连通分支是G1,G2,则 存在u∈V(G1),v∈V(G2),使得(u,v)∉E(G) 证明: (反证)否则λ(G)=|E’| =|V(G1)|×|V(G2)|≥|V(G1)|+|V(G2)|-1=n-1, 与G非完全图相矛盾! # 说明: a≥1∧b≥1⇒(a-1)(b-1)=ab-a-b+1≥0 ⇔ ab≥a+b-1.
Whitney定理(续) 证明(续):(k≤s)设GE的2个连通分支是 G,G2.设ueV(G)vEVG2,使得 uv)glE(G).如下构造V":ve∈E,选择e的 异于u,的一个端点放入V:El GV"GE=GG2,u和V在G-V"中不连 通,所以V中含有点割集V. 所以K≤V|NE|=. # 《集合论与图论》第16讲 8
《集合论与图论》第16讲 18 Whitney定理(续) 证明(续): (κ≤λ) 设G-E’的2个连通分支是 G1,G2. 设u∈V(G1),v∈V(G2),使得 (u,v)∉E(G). 如下构造V’’:∀e∈E’, 选择e的 异于u,v的一个端点放入V’’. |V’’|≤|E’|. G-V’’⊆G-E’=G1∪G2, u和v在G-V’’中不连 通, 所以V’’中含有点割集V’. 所以 κ≤|V’|≤|V’’|≤|E’|=λ. # u v