惠特尼连通性定理

图论中，惠特尼连通性定理（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连通性的具体证明方向。