惠特尼定理

图论中，惠特尼定理（英语：Whitney's theorem），又称为惠特尼连通性定理（Whitney's theorem on connectivity），是美国数学家哈斯勒·惠特尼于1932年提出的关于2连通图等价性质的定理，该定理提供了关于2连通图的不同点对之间的连通性质刻画，描述了2连通图的特殊性质。

对一个图${\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 <!--\; \in \; -->V(G)}$，能找到至少两条连接${\displaystyle u,v}$的内部不相交路径。

下面通过对${\displaystyle u,v}$之间的距离${\displaystyle d(u,v)}$进行归纳来由数学归纳法证明：

于是根据数学归纳法，当${\displaystyle G}$是2连通图时，对于任意两点${\displaystyle u,v\in <!--\; \in \; -->V(G)}$，能找到至少两条连接${\displaystyle u,v}$的内部不相交路径。

根据惠特尼定理的结论，可以得到关于2连通图的等价描述的推论：

令${\displaystyle G^{\prime }=G\cup <!--\; \cup \; -->\{w,z\}\cup <!--\; \cup \; -->\{uw,vw,xz,yz\}}$。首先${\displaystyle G^{\prime }}$仍然是2连通的，这是因为，${\displaystyle G^{\prime }}$的构造过程是加入两个点且两个点均与原图${\displaystyle G}$中两个点相连，则考虑${\displaystyle G^{\prime }}$中的割集${\displaystyle S}$。若割集中含有新加入的点${\displaystyle \{w,z\}}$，则除去新加入的点，${\displaystyle S-<!--\; -\; -->\{w,z\}}$是原图${\displaystyle G}$的割集，而根据描述1，${\displaystyle G}$本是2连通的，则${\displaystyle |S|\ge <!--\; \ge \; -->2+1=3}$或${\displaystyle |S|\ge <!--\; \ge \; -->2+2=4}$；若割集中不含有新加入的点，如果割集取自${\displaystyle \{u,v,x,y\}}$，则${\displaystyle |S|\ge <!--\; \ge \; -->2}$，否则${\displaystyle S}$实际上是原图${\displaystyle G}$的割集，所以同样，${\displaystyle |S|\ge <!--\; \ge \; -->2}$。所以无论如何，对于${\displaystyle G^{\prime }}$的任意割集，其大小至少为2，故${\displaystyle G^{\prime }}$仍然是2连通的。实际上，关于向${\displaystyle k}$-连通图加入辅助点的更一般的结论称为“扩展引理”（expansion lemma），它也在证明门格尔定理中发挥了作用。

那么根据描述3，对于${\displaystyle G^{\prime }}$，一定存在环${\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连通性的具体证明方向。