惠特尼不等式

在图论中，惠特尼不等式 (英：Whitney's connectivity inequalities or Whitney's inequalities)，又称为惠特尼连通性不等式，是关于图的连通度的重要不等式，几乎出现于任何一本图论教科书中。该不等式明确地指出了图的点连通度与边连通度以及与图最小度之间的大小关系。但目前关于该定理的提出者是否是哈斯勒·惠特尼还没有统一定论。

对于任何一个非平凡图${\displaystyle G}$，均满足

由于图${\displaystyle G}$的最小度为${\displaystyle \mathrm{\delta <!--\; \delta \; -->}(G)}$，于是考虑${\displaystyle G}$中度为${\displaystyle \mathrm{\delta <!--\; \delta \; -->}(G)}$的点${\displaystyle v}$，${\displaystyle deg(v)=\mathrm{\delta <!--\; \delta \; -->}(G)}$。从${\displaystyle G}$中删除与${\displaystyle v}$相接的所有边，则${\displaystyle v}$成为孤立点，即与${\displaystyle v}$相接的所有边构成了一个不连通边集${\displaystyle F}$，且该不连通边集的大小${\displaystyle |F|=deg(v)=\mathrm{\delta <!--\; \delta \; -->}(G)}$。根据边连通性的定义，${\displaystyle \mathrm{\lambda <!--\; \lambda \; -->}(G)\le <!--\; \le \; -->|F|=\mathrm{\delta <!--\; \delta \; -->}(G)}$。

考虑图${\displaystyle G}$的最小不连通边集${\displaystyle F}$，只需证明存在图${\displaystyle G}$的一个割集${\displaystyle S}$，它们的大小满足${\displaystyle |S|\le <!--\; \le \; -->|F|}$即可。对于${\displaystyle F}$，${\displaystyle F}$将图${\displaystyle G}$分割成至少两个连通分量${\displaystyle C_1,C_2}$，这里取${\displaystyle C_1}$为连通分量，${\displaystyle C_2}$为剩余部分（不一定为连通分量）。令${\displaystyle T=F\cap <!--\; \cap \; -->C_1}$，显然${\displaystyle T}$中不包含任何边，否则从${\displaystyle F}$中除去该边，则得到比${\displaystyle F}$更小的不连通边集，与${\displaystyle F}$是最小的不连通边集矛盾。

最小不连通边集的分割情况

连通分量中没有其他点的情况

当图${\displaystyle G}$是3正则图时，${\displaystyle \mathrm{\kappa <!--\; \kappa \; -->}(G)=\mathrm{\lambda <!--\; \lambda \; -->}(G)}$。

根据惠特尼不等式，已有${\displaystyle \mathrm{\kappa <!--\; \kappa \; -->}(G)\le <!--\; \le \; -->\mathrm{\lambda <!--\; \lambda \; -->}(G)}$，只需证明${\displaystyle \mathrm{\kappa <!--\; \kappa \; -->}(G)\ge <!--\; \ge \; -->\mathrm{\lambda <!--\; \lambda \; -->}(G)}$。

考虑图${\displaystyle G}$的最小割集${\displaystyle G}$，由于图${\displaystyle G}$是3正则图，则${\displaystyle S}$与余下被分隔的部分之间的连接只有最多三种类型。

显然，${\displaystyle |F|=|S|}$，且${\displaystyle F}$是图${\displaystyle G}$的不连通边集。于是${\displaystyle \mathrm{\lambda <!--\; \lambda \; -->}(G)\le <!--\; \le \; -->|F|=|S|=\mathrm{\kappa <!--\; \kappa \; -->}(G)}$。

一方面，该不等式提供了三个图的基本量之间的大小关系，为其他不等式以及定理提供了放缩方向；另一方面，该不等式也反映了“高连通性需要图较为稠密”的组合直观。