惠特尼不等式

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

右半边

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

左半边

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

• 如果${\displaystyle C_{1}-T\neq \varnothing }$ ，即${\displaystyle C_{1}}$ 除去${\displaystyle T}$ 中的点外还有其他点${\displaystyle v}$ ，则${\displaystyle T}$ 可以作为分离${\displaystyle v}$ 与${\displaystyle C_{2}}$ 的割集。考虑${\displaystyle T}$ 的大小，断言${\displaystyle |T|\leq |F|}$ 。这是因为根据上述分析，${\displaystyle T}$ 中不包含任何边，而${\displaystyle T\subseteq F}$ ，所以${\displaystyle T}$ 中任意一点均与${\displaystyle F}$ 中至少一条边相接。于是${\displaystyle \kappa (G)\leq |T|\leq |F|=\lambda (G)}$ 。

• 如果${\displaystyle C_{1}-T=\varnothing }$ ，即${\displaystyle C_{1}}$ 除去${\displaystyle T}$ 中的点外没有其他点，此时${\displaystyle T}$ 并不能直接作为割集。任取一点${\displaystyle u\in T}$ ，考虑${\displaystyle u}$ 的邻居组成的集合${\displaystyle N(u)}$ 。显然${\displaystyle N(u)}$ 分割了${\displaystyle u}$ 与其他部分，所以${\displaystyle N(u)}$ 可以作为图${\displaystyle G}$ 的割集，断言${\displaystyle |N(u)|\leq |F|}$ 。这是因为，若${\displaystyle u}$ 的邻居为${\displaystyle F\cap C_{2}}$ 中的点，则它们之间的边即为${\displaystyle F}$ 中的边，所以对于这样的邻居，${\displaystyle N(u)}$ 中一个点对应了${\displaystyle F}$ 中一条边；若${\displaystyle u}$ 的邻居也是${\displaystyle F\cap C_{1}}$ 中的点，则一定存在与该邻居相接的在${\displaystyle F}$ 中的边，所以对于这样的邻居，${\displaystyle N(u)}$ 中一个点对应了${\displaystyle F}$ 中至少一条边。于是${\displaystyle \kappa (G)\leq |N(u)|\leq |F|=\lambda (G)}$ 。
• 惠特尼不等式的左半边证明
•  

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

•  

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

当图${\displaystyle G}$ 是3正则图时，${\displaystyle \kappa (G)=\lambda (G)}$ 。^[3]

推论证明

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

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

1. 对于第一种类型，${\displaystyle S}$ 中的点与连通分量${\displaystyle C}$ 相连1条边，与剩余部分相连2条边，则取与连通分量${\displaystyle C}$ 相连的1条边加入集合${\displaystyle F}$ ；
2. 对于第二种类型，${\displaystyle S}$ 中的点与连通分量${\displaystyle C}$ 相连2条边，与剩余部分相连1条边，则取与剩余部分相连的1条边加入集合${\displaystyle F}$ ；
3. 对于第三种类型，${\displaystyle S}$ 中的点与连通分量${\displaystyle C}$ 相连1条边，与剩余部分相连1条边，与${\displaystyle S}$ 中的另一点相连一条边，则取与连通分量${\displaystyle C}$ 相连的1条边加入集合${\displaystyle F}$ 。

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

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

1. ^ Whitney, Hassler. Congruent Graphs and the Connectivity of Graphs.. American Journal of Mathematics. 1932, 54: 150–68 [2021-12-10]. doi:10.2307/2371086. （原始内容存档于2022-05-21）. 
2. ^ 程钊. 关于惠特尼不等式的历史注记. 第三届数学史与数学教育国际研讨会. 中国北京. 2009 [2021-12-10]. （原始内容存档于2021-12-10）. 
3. ^ West, Douglas Brent. Introduction to Graph Theory. Prentice Hall. 2001: 153-154. ISBN 81-7808-830-4.