惠特尼連通性定理

圖論中，惠特尼連通性定理（Whitney's theorem on connectivity）^[1]，簡稱惠特尼定理（英語：Whitney's theorem），是美國數學家哈斯勒·惠特尼於1932年^[2]提出的關於2連通圖等價性質的定理，該定理提供了關於2連通圖的不同點對之間的連通性質刻畫，描述了2連通圖的特殊性質^[3]。

惠特尼定理概述圖

定理陳述

對一個圖${\displaystyle G}$，若${\displaystyle G}$至少存在3個點，則${\displaystyle G}$是2連通的若且唯若對${\displaystyle G}$中任意兩個點${\displaystyle u,v}$，${\displaystyle G}$中至少存在連接${\displaystyle u,v}$的2條內部不相交路徑，即除首尾相同（皆為${\displaystyle u,v}$）外，沒有其他公共頂點的路徑。

定理證明

必要性

因為任意兩點之間均存在路徑，於是${\displaystyle G}$是連通的。

進一步，對於任意兩點之間有至少存在兩條內部不相交路徑，所以考慮刪除${\displaystyle G}$中任意一點，其均不會造成${\displaystyle G}$不連通。於是${\displaystyle G}$是2連通的。

充分性

${\displaystyle G}$是2連通的，希望證明對於任意兩點${\displaystyle u,v\in V(G)}$，能找到至少兩條連接${\displaystyle u,v}$的內部不相交路徑。

下面通過對${\displaystyle u,v}$之間的距離${\displaystyle d(u,v)}$進行歸納來由數學歸納法證明：

1. 對於${\displaystyle d(u,v)=1}$，此時${\displaystyle uv}$是${\displaystyle G}$的一條邊。而由於${\displaystyle \kappa (G)\geq 2}$，根據惠特尼不等式，${\displaystyle \lambda (G)\geq \kappa (G)}$，於是${\displaystyle \lambda (G)\geq 2}$。那麼${\displaystyle G}$至少需要刪兩條邊才會導致不連通，於是${\displaystyle G}$刪一條邊之後仍然還是連通的。則考慮${\displaystyle G-uv}$，其仍然是連通圖，於是對於${\displaystyle u,v}$，${\displaystyle G-uv}$仍然存在一條路徑連接${\displaystyle u,v}$。於是${\displaystyle G}$中至少存在兩條連接${\displaystyle u,v}$的內部不相交路徑。
2. 假設對於${\displaystyle d(u,v)=k-1}$，${\displaystyle G}$中都存在至少兩條連接${\displaystyle u,v}$的內部不相交路徑，則考慮${\displaystyle d(u,v)=k}$；
3. 由於${\displaystyle u,v}$之間距離為${\displaystyle k}$，則${\displaystyle G}$中一定存在一條連接${\displaystyle u,v}$的路徑${\displaystyle P}$，且${\displaystyle P}$的長度（其包含的邊的數量）為${\displaystyle k}$，如圖1所示。此時考慮${\displaystyle P}$中${\displaystyle v}$的鄰居${\displaystyle w}$，${\displaystyle w}$一定滿足${\displaystyle d(u,w)=k-1}$。這是因為對於${\displaystyle w}$在${\displaystyle P}$中已經有${\displaystyle u}$到${\displaystyle w}$長度為${\displaystyle k-1}$的路徑，而如果還存在其他路徑長度小於${\displaystyle k-1}$，那麼也存在${\displaystyle u}$到${\displaystyle v}$的路徑長度小於${\displaystyle k}$，與${\displaystyle d(u,v)=k}$矛盾。於是對於${\displaystyle u,w}$，根據歸納假設，存在至少2條連接${\displaystyle u,w}$的內部不相交路徑${\displaystyle P,P'}$。於是${\displaystyle P\cup P'}$構成了一個環，如圖2所示。

   

   充分性的歸納證明

   • 如果${\displaystyle v\in P\cup P'}$，即${\displaystyle v}$已經在這個環上，如圖3所示，則對於${\displaystyle u}$與${\displaystyle v}$這兩個環上的點，它們之間也存在環上兩條相反的繞行方向的路徑，於是${\displaystyle u}$與${\displaystyle v}$存在兩條內部不相交的路徑。
   • 如果${\displaystyle v\notin P\cup P'}$，那麼由於${\displaystyle G}$是2連通的，則考慮${\displaystyle G-w}$，其仍然是連通的。那麼對於${\displaystyle u,v}$，此時存在另一條連接${\displaystyle u,v}$的路徑${\displaystyle Q}$。此時，如果${\displaystyle Q}$與${\displaystyle P}$以及${\displaystyle P'}$除了${\displaystyle u}$之外沒有其他交點，如圖4所示，則顯然${\displaystyle Q}$與${\displaystyle P\cup wv}$就構成了連接${\displaystyle u,v}$的兩條內部不相交路徑；否則，令${\displaystyle z}$為${\displaystyle Q}$與${\displaystyle P\cup P'}$相交的最後一個交點，根據${\displaystyle P,P'}$的對稱性，不妨假設${\displaystyle z}$就在${\displaystyle P}$上，如圖所示。那麼考慮${\displaystyle \underbrace {(u\rightsquigarrow z)} _{P}\cup \underbrace {(z\rightsquigarrow v)} _{Q}}$和${\displaystyle \underbrace {(u\rightsquigarrow w)} _{P'}\cup wv}$，這兩條路徑則構成了連接${\displaystyle u,v}$的內部不相交路徑。
4. 於是無論如何，當${\displaystyle d(u,v)=k}$時，均能至少找到連接${\displaystyle u,v}$的兩條內部不相交路徑。

於是根據數學歸納法，當${\displaystyle G}$是2連通圖時，對於任意兩點${\displaystyle u,v\in V(G)}$，能找到至少兩條連接${\displaystyle u,v}$的內部不相交路徑。

推論

根據惠特尼定理的結論，可以得到關於2連通圖的等價描述的推論：

1. 圖${\displaystyle G}$是連通且沒有割點（即圖${\displaystyle G}$是2連通的）；
2. 對於圖${\displaystyle G}$中任意兩點${\displaystyle u,v}$，${\displaystyle G}$中存在至少兩條連接${\displaystyle u,v}$的內部不相交路徑；
3. 對於圖${\displaystyle G}$中任意兩點${\displaystyle u,v}$，${\displaystyle G}$中存在一個環${\displaystyle C}$且${\displaystyle u,v}$均在${\displaystyle C}$上；
4. 圖${\displaystyle G}$的最小度至少為1，且對於圖${\displaystyle G}$中的任意兩條邊${\displaystyle e_{1},e_{2}}$，${\displaystyle G}$中存在一個環${\displaystyle C}$且${\displaystyle e_{1},e_{2}}$均在${\displaystyle C}$上。^[4]

推論證明

• 描述1${\displaystyle \Leftrightarrow }$描述2：直接運用惠特尼定理即可。
• 描述2${\displaystyle \Leftrightarrow }$描述3：關係是顯然的。若這兩點之間存在至少兩條連接它們的內部不相交路徑，則這兩條內部不相交路徑的並形成了環且這兩點在環上；若存在這兩點同時位於環上，則這兩點之間在環上的不同繞行方向的路徑形成了連接它們的兩條內部不相交路徑。
• 描述4${\displaystyle \Leftrightarrow }$描述3：對任意的兩點${\displaystyle u,v\in V(G)}$，由於${\displaystyle \delta (G)\geq 1}$，則${\displaystyle u,v}$均存在鄰居，${\displaystyle \exists ux,vy\in E(G)}$。考察${\displaystyle ux,vy}$，
  • 若${\displaystyle ux\cap vy=\varnothing }$即${\displaystyle ux,vy}$兩條邊完全分離，則由於任意兩條邊均位於一個環上，於是${\displaystyle ux,vy}$位於同一個環上，於是${\displaystyle u,v}$也位於該環上。
  • 若${\displaystyle ux\cap vy=z}$即${\displaystyle ux,vy}$兩條邊有一個公共點${\displaystyle z}$，此時${\displaystyle ux,vy}$仍然是兩條不同的邊，則同樣由於任意兩條邊均位於一個環上，於是${\displaystyle ux,vy}$位於同一個環上，於是${\displaystyle u,v}$也位於該環上。
  • 若${\displaystyle ux\cap vy=uv}$即${\displaystyle ux,vy}$實際上只是一條邊${\displaystyle uv}$，此時${\displaystyle uv}$與其他任意一條邊仍然位於同一個環上，所以${\displaystyle u,v}$仍然位於環上。
• 描述123${\displaystyle \Leftrightarrow }$描述4：首先根據描述1，圖${\displaystyle G}$是連通的，所以${\displaystyle \delta (G)\geq 1}$。其次，對於圖${\displaystyle G}$中的任意兩條邊${\displaystyle uv,xy}$，下面證明它們位於同一個環上。

向${\displaystyle G}$中加入兩個輔助點${\displaystyle w,z}$

令${\displaystyle G'=G\cup \{w,z\}\cup \{uw,vw,xz,yz\}}$。首先${\displaystyle G'}$仍然是2連通的，這是因為，${\displaystyle G'}$的構造過程是加入兩個點且兩個點均與原圖${\displaystyle G}$中兩個點相連，則考慮${\displaystyle G'}$中的割集${\displaystyle S}$。若割集中含有新加入的點${\displaystyle \{w,z\}}$，則除去新加入的點，${\displaystyle S-\{w,z\}}$是原圖${\displaystyle G}$的割集，而根據描述1，${\displaystyle G}$本是2連通的，則${\displaystyle |S|\geq 2+1=3}$或${\displaystyle |S|\geq 2+2=4}$；若割集中不含有新加入的點，如果割集取自${\displaystyle \{u,v,x,y\}}$，則${\displaystyle |S|\geq 2}$，否則${\displaystyle S}$實際上是原圖${\displaystyle G}$的割集，所以同樣，${\displaystyle |S|\geq 2}$。所以無論如何，對於${\displaystyle G'}$的任意割集，其大小至少為2，故${\displaystyle G'}$仍然是2連通的。實際上，關於向${\displaystyle k}$-連通圖加入輔助點的更一般的結論稱為「擴展引理」（expansion lemma），它也在證明門格爾定理中發揮了作用。^[5]

那麼根據描述3，對於${\displaystyle G'}$，一定存在環${\displaystyle C}$，${\displaystyle w,z}$均位於${\displaystyle C}$上。而${\displaystyle w,z}$的度均為2，所以${\displaystyle uw,vw,xz,yz}$也位於${\displaystyle C}$上，且${\displaystyle C}$的其他邊均來自原圖${\displaystyle G}$。於是可以將${\displaystyle uwv}$替換成${\displaystyle uv}$，${\displaystyle xzy}$替換成${\displaystyle xy}$，從而${\displaystyle uv,xy}$均位於原圖中的一個環上。

影響及意義

惠特尼定理提供了對於2連通性的更具體的性質刻畫，從而提供了另一種對於2連通性的具體證明方向。