惠特尼不等式

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

 叙述 
对于任何一个非平凡图，均满足

其中表示图的点连通度，表示图的边连通度，表示图的最小度。

 证明 
替代=惠特尼不等式的右半边证明|缩略图|惠特尼不等式的右半边证明

 右半边 
由于图的最小度为，于是考虑中度为的点，。从中删除与相接的所有边，则成为孤立点，即与相接的所有边构成了一个不连通边集，且该不连通边集的大小。根据边连通性的定义，。

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

 如果，即除去中的点外还有其他点，则可以作为分离与的割集。考虑的大小，断言。这是因为根据上述分析，中不包含任何边，而，所以中任意一点均与中至少一条边相接。于是。

 如果，即除去中的点外没有其他点，此时并不能直接作为割集。任取一点，考虑的邻居组成的集合。显然分割了与其他部分，所以可以作为图的割集，断言。这是因为，若的邻居为中的点，则它们之间的边即为中的边，所以对于这样的邻居，中一个点对应了中一条边；若的邻居也是中的点，则一定存在与该邻居相接的在中的边，所以对于这样的邻居，中一个点对应了中至少一条边。于是。

 关于3正则图的推论 
当图是3正则图时，。

 推论证明 
替代=3正则图的割集与不连通边集|缩略图|3正则图的割集与不连通边集
根据惠特尼不等式，已有，只需证明。

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

 对于第一种类型，中的点与连通分量相连1条边，与剩余部分相连2条边，则取与连通分量相连的1条边加入集合；
 对于第二种类型，中的点与连通分量相连2条边，与剩余部分相连1条边，则取与剩余部分相连的1条边加入集合；
 对于第三种类型，中的点与连通分量相连1条边，与剩余部分相连1条边，与中的另一点相连一条边，则取与连通分量相连的1条边加入集合。

显然，，且是图的不连通边集。于是。

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

 参考文献 

Category:图论
Category:组合数学
Category:理论计算机科学
Category:数学定理