惠特尼不等式

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

叙述

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

$$\kappa (G)\le \lambda (G)\le \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)\le |F|=\delta (G)$。

左半边

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

• 如果$C_1-T\ne \varnothing$，即$C_1$除去$T$中的点外还有其他点$v$，则$T$可以作为分离$v$与$C_2$的割集。考虑$T$的大小，断言$|T|\le |F|$。这是因为根据上述分析，$T$中不包含任何边，而$T\subseteq F$，所以$T$中任意一点均与$F$中至少一条边相接。于是$\kappa (G)\le |T|\le |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)|\le |F|$。这是因为，若$u$的邻居为$F\cap C_2$中的点，则它们之间的边即为$F$中的边，所以对于这样的邻居，$N(u)$中一个点对应了$F$中一条边；若$u$的邻居也是$F\cap C_1$中的点，则一定存在与该邻居相接的在$F$中的边，所以对于这样的邻居，$N(u)$中一个点对应了$F$中至少一条边。于是$\kappa (G)\le |N(u)|\le |F|=\lambda (G)$。
• 惠特尼不等式的左半边证明
• 
  最小不连通边集的分割情况
• 
  连通分量中没有其他点的情况

关于3正则图的推论

当图$G$是3正则图时，$\kappa (G)=\lambda (G)$。

推论证明

3正则图的割集与不连通边集

根据惠特尼不等式，已有$\kappa (G)\le \lambda (G)$，只需证明$\kappa (G)\ge \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)\le |F|=|S|=\kappa (G)$。

影响及意义

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