1、点连通度和边连通度

\quad一张连通图G最少删除多少个顶点后使得G不连通，设删除顶点数为m，则称图G的点连通度为$K(G)=m$。删除顶点集$V^{\prime }$后$G-V^{\prime }$不连通，则$V^{\prime }$为G的顶点割集，点数最少的顶点割集为最小顶点割，其顶点个数即为刚刚所说的点连通度。
\quad在G中，若存在顶点割，称G的最小顶点割的顶点数称为G的点连通度；否则称n-1为其点连通度。G的点连通度记为k(G), 简记为k。若G不连通，k(G)=0。如下图所示：

\quad一张连通图G最少删除多少条边后使得G不连通，设删除边数m，则称图G的边连通度为$\lambda (G)=m$。若G不连通或G是平凡图，则定义$\lambda (G)=0$。如下图所示：

\quad在G中，若k (G)≧ k, 称G是k连通的；若λ(G)≧k，称G是k边连通的。如下图：

二、连通度性质

1、惠特尼定理：对任意图G，有$k(G)\le \lambda (G)\le \delta (G)$
2、设G是(n,m)连通图，则$k(G)\le [\frac{2m}{n}]$。存在一个(n, m) 图G，例如，完全图、超立方体等，使得$k(G)=[\frac{2m}{n}]$。
3、设G是（n，m）单图，若$\delta (G)\ge [\frac{n}{2}]$，则G连通
证明：若G不连通，则G至少有两个连通分支，至少有一个分支H，使得：$\delta (G)\le [\frac{n}{2}]-1<[\frac{n}{2}]$，与条件矛盾。
4、设G是（n，m）图，若对任意正整数k，有$\delta (G)\ge \frac{n+k-2}{2}$，则G是k连通的。
5、设G是n阶单图，若$\delta (G)\ge [\frac{n}{2}]$，则：$\lambda (G)=\delta (G)$

三、敏格尔定理

\quad作用：敏格尔定理是图的连通性问题的核心定理之一，它描述了图的连通度与连通图中不同点对间的不相交路的数目之间的关系。
\quad定义：设u与v是图G的两个不同顶点，S表示G的一个顶点子集或边子集，如果u与v不在G-S的同一分支上，称S分离u和v。（点u与v的点分离集或边分离集），举个例子，如下图所示：

\quad敏格尔定理引理（最小最大定理）

• 设x和y是图G中的两个不相邻点，则G中分离点x和y的最小点数等于独立的(x,y)路的最大数目
• 设x和y是图G中的两个不相邻点，则G中分离点x和y的最小边数等于G中边不重的(x,y)路的最大数目

\quad敏格尔定理

• 一个非平凡的图G是k (k≧2)连通的，当且仅当G的任意两个顶点间至少存在k条内点不交的(u ,v)路。
• 一个非平凡的图G是k (k≧2)边连通的，当且仅当G的任意两个顶点间至少存在k条边不重的(u ,v)路。