惠特尼不等式

在圖論中，惠特尼不等式 (英：Whitney's connectivity inequalities or Whitney's inequalities)，又稱為惠特尼連通性不等式，是關於圖的連通度的重要不等式，幾乎出現於任何一本圖論教科書中。該不等式明確地指出了圖的點連通度與邊連通度以及與圖最小度之間的大小關係。但目前關於該定理的提出者是否是哈斯勒·惠特尼還沒有統一定論。

敘述

對於任何一個非平凡圖$G$，均滿足

$$\kappa (G)\leq \lambda (G)\leq \delta (G)$$其中$\kappa (G)$表示圖$G$的點連通度，$\lambda (G)$表示圖$G$的邊連通度，$\delta (G)$表示圖$G$的最小度。

證明

惠特尼不等式的右半邊證明

右半邊

由於圖$G$的最小度為$\delta (G)$，於是考慮$G$中度為$\delta (G)$的點$v$，$deg(v)=\delta (G)$。從$G$中刪除與$v$相接的所有邊，則$v$成為孤立點，即與$v$相接的所有邊構成了一個不連通邊集$F$，且該不連通邊集的大小$|F|=deg(v)=\delta (G)$。根據邊連通性的定義，$\lambda (G)\leq |F|=\delta (G)$。

左半邊

考慮圖$G$的最小不連通邊集$F$，只需證明存在圖$G$的一個割集$S$，它們的大小滿足$|S|\leq |F|$即可。 對於$F$，$F$將圖$G$分割成至少兩個連通分量$C_{1},C_{2}$，這裏取$C_{1}$為連通分量，$C_{2}$為剩餘部分（不一定為連通分量）。令$T=F\cap C_{1}$，顯然$T$中不包含任何邊，否則從$F$中除去該邊，則得到比$F$更小的不連通邊集，與$F$是最小的不連通邊集矛盾。

• 如果$C_{1}-T\neq \varnothing$，即$C_{1}$除去$T$中的點外還有其他點$v$，則$T$可以作為分離$v$與$C_{2}$的割集。考慮$T$的大小，斷言$|T|\leq |F|$。這是因為根據上述分析，$T$中不包含任何邊，而$T\subseteq F$，所以$T$中任意一點均與$F$中至少一條邊相接。於是$\kappa (G)\leq |T|\leq |F|=\lambda (G)$。

• 如果$C_{1}-T=\varnothing$，即$C_{1}$除去$T$中的點外沒有其他點，此時$T$並不能直接作為割集。任取一點$u\in T$，考慮$u$的鄰居組成的集合$N(u)$。顯然$N(u)$分割了$u$與其他部分，所以$N(u)$可以作為圖$G$的割集，斷言$|N(u)|\leq |F|$。這是因為，若$u$的鄰居為$F\cap C_{2}$中的點，則它們之間的邊即為$F$中的邊，所以對於這樣的鄰居，$N(u)$中一個點對應了$F$中一條邊；若$u$的鄰居也是$F\cap C_{1}$中的點，則一定存在與該鄰居相接的在$F$中的邊，所以對於這樣的鄰居，$N(u)$中一個點對應了$F$中至少一條邊。於是$\kappa (G)\leq |N(u)|\leq |F|=\lambda (G)$。
• 惠特尼不等式的左半邊證明
• 
  最小不連通邊集的分割情況
• 
  連通分量中沒有其他點的情況

關於3正則圖的推論

當圖$G$是3正則圖時，$\kappa (G)=\lambda (G)$。

推論證明

3正則圖的割集與不連通邊集

根據惠特尼不等式，已有$\kappa (G)\leq \lambda (G)$，只需證明$\kappa (G)\geq \lambda (G)$。

考慮圖$G$的最小割集$G$，由於圖$G$是3正則圖，則$S$與餘下被分隔的部分之間的連接只有最多三種類型。

1. 對於第一種類型，$S$中的點與連通分量$C$相連1條邊，與剩餘部分相連2條邊，則取與連通分量$C$相連的1條邊加入集合$F$；
2. 對於第二種類型，$S$中的點與連通分量$C$相連2條邊，與剩餘部分相連1條邊，則取與剩餘部分相連的1條邊加入集合$F$；
3. 對於第三種類型，$S$中的點與連通分量$C$相連1條邊，與剩餘部分相連1條邊，與$S$中的另一點相連一條邊，則取與連通分量$C$相連的1條邊加入集合$F$。

顯然，$|F|=|S|$，且$F$是圖$G$的不連通邊集。於是$\lambda (G)\leq |F|=|S|=\kappa (G)$。

影響及意義

一方面，該不等式提供了三個圖的基本量之間的大小關係，為其他不等式以及定理提供了放縮方向；另一方面，該不等式也反映了「高連通性需要圖較為稠密」的組合直觀。