8.5 惠特尼不等式

8.5 惠特尼不等式

  在介绍惠特尼不等式之前，我先说几个概念。首先是边连通性，边连通性，就是至少删除多少条边，才能增加图连通分量component的数量，形象地说，删除多少条边才能分裂一个图。边连通性符号为 λ ( G ) \lambda(G) λ(G)。
  点连通性，就是删除多少个点才可以增加组件component的数量，点连通性符号为 κ ( G ) \kappa(G) κ(G)。
  而最小度数，符号为 δ ( G ) \delta(G) δ(G)。
  惠特尼不等式的内容是，对于任意图， κ ( G ) ≤ λ ( G ) ≤ δ ( G ) \kappa(G)\leq\lambda(G)\leq\delta(G) κ(G)≤λ(G)≤δ(G)。也就是说，点连通性小于等于边连通性，边连通性小于等于最小度数。
  现在我给出证明。
  首先证明边连通性小于等于最小度数。利用分类归纳法，如果图G没有边，那么 λ = 0 \lambda=0 λ=0并且 δ = 0 \delta=0 δ=0。这满足惠特尼不等式。剩下的就是不为0的情况了。这个时候，我们把所有最小度数点的所有边移除，那么这个点肯定就孤立了，不需要删除更多的边，这就可以证明边连通性 λ ≤ δ \lambda\leq\delta λ≤δ。
  上面的证明都是等于的例子，虽然已经能证明小于等于，但是我们需要找个小于的例子，来相信会有小于的情况。下图就是个例子，删除e，就变成了两个连通分量component，所以边连通性为1，但是最小度数为2。所以 λ ( G ) ≤ δ ( G ) \lambda(G)\leq\delta(G) λ(G)≤δ(G)不能改成等号。

  再证明 κ ( G ) ≤ λ ( G ) \kappa(G)\leq\lambda(G) κ(G)≤λ(G)。因为 λ \lambda λ为边连通性，所以存在一个割边集cut set，姑且叫它S吧。割边集的概念，我用印度理工学院的《Group Theory》中的图说明一下，图中 e 2 , e 5 , e 9 , e 10 e_2,e_5,e_9,e_{10} e2​,e5​,e9​,e10​组成了一个割边集：

  割边集S含有 λ \lambda λ条边，这个割边集把图拆成了两个连通分量component V 1 V_1 V1​和 V 2 V_2 V2​。把 V 1 V_1 V1​或 V 2 V_2 V2​中S的端点全部删除就把图分成了两半。而如果这 λ \lambda λ条边，如果多条边指向一个点，那么删除点的数量就小于删除边的数量。所以证明了 κ ( G ) ≤ λ ( G ) \kappa(G) \leq \lambda(G) κ(G)≤λ(G)。
  不等式的两部分都证明完了，连起来，Q.E.D.