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

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

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

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

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

File:Whitney's connectivity inequalities left proof1.png|alt=最小不连通边集的分割情况|最小不连通边集的分割情况
File:Whitney's connectivity inequalities left proof2.png|alt=连通分量中没有其他点的情况|连通分量中没有其他点的情况

关于3正则图的推论
当图G是3正则图时，\kappa(G)= \lambda(G)。

推论证明
根据惠特尼不等式，已有\kappa(G)\leq \lambda(G)，只需证明\kappa(G)\geq \lambda(G)。

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

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

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

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

显然，|F|=|S|，且F是图G的不连通边集。于是\lambda(G)\leq |F|=|S|=\kappa(G)。

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

参考文献