哈恩(1879~1968)德国物理学家，化学家。最大的贡 献是1938年和F.斯特拉斯曼一起发现核裂变现象。哈恩获 得1944年诺贝尔化学奖。 借助于敏格尔定理，数学家惠特尼在1932年的博士论 文中给出了k连通图的一个美妙刻画。这就是人们熟知的 所谓“敏格尔定理” 定理2（惠特尼1932）一个非平凡的图G是kk≥2)连通的， 当且仅当G的任意两个顶点u与v间，至少存在k条内点不交 的(u,v)路。 证明：（必要性）设G是kk≥2)连通的，u与v是G的两个 顶点。 情形1：如果u与v不相邻，U为G的最小u-v分离集，那么有 U≥k(G)≥k,于是由敏格尔定理，结论成立；
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7 哈恩 (1879～1968 ) 德国物理学家，化学家。最大的贡 献是1938年和F.斯特拉斯曼一起发现核裂变现象。哈恩获 得1944年诺贝尔化学奖 。 借助于敏格尔定理，数学家惠特尼在1932年的博士论 文中给出了k连通图的一个美妙刻画。这就是人们熟知的 所谓“敏格尔定理” 定理2 (惠特尼1932) 一个非平凡的图G是k (k≧2)连通的， 当且仅当G的任意两个顶点u与v间，至少存在k条内点不交 的(u ,v)路。 证明: (必要性) 设G是k (k≧2)连通的，u与v是G的两个 顶点 。 情形1：如果u与v不相邻，U为G的最小u--v分离集,那么有 |U| ≧ k (G) ≧ k,于是由敏格尔定理，结论成立；
情形2：若u与v邻接，其中e=uv,那么，容易证明：G-e 是(k-1)连通的。由情形1知：G-e至少包含k-1条内点不交 的u-v路，即G至少包含k条内点不交的u-v路。 (充分性)假设G中任意两个顶点间至少存在k条内部 不交路。设U是G的最小顶点割，即U=k(G)。令x与y是 G-U的处于不同分支的两个点。所以U是x与y的分离集， 由敏格尔定理：U≥k,即证明G是k连通的。 例1设G是k连通图，S是由G中任意k个顶点构成的集 合。若图H是由G通过添加一个新点w以及连接w到S中所 有顶点得到的新图，求证：H是k连通的。 证明：首先，分离G中两个不相邻顶点至少要k个点， 其次，分离w与G中不在S中顶点需要k个顶点。因此H是k 连通的
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 8 情形2：若u与v邻接，其中e=uv,那么，容易证明：G-e 是(k-1)连通的。由情形1知：G-e至少包含k-1条内点不交 的u--v路，即G至少包含k条内点不交的u--v路。 (充分性) 假设G中任意两个顶点间至少存在 k 条内部 不交路。设U是G的最小顶点割，即|U|=k (G)。令x与y是 G-U的处于不同分支的两个点。所以U是x与y的分离集， 由敏格尔定理：|U| ≧ k, 即证明G是 k 连通的。 例1 设G是k连通图，S是由G中任意k个顶点构成的集 合。若图H是由G通过添加一个新点w以及连接w到S中所 有顶点得到的新图，求证：H是k连通的。 证明：首先，分离G中两个不相邻顶点至少要k个点， 其次，分离w与G中不在S中顶点需要k个顶点。因此H是k 连通的
例2设G是k连通图，u,VY2,V为G中k+1个不同顶 点。求证：G中有k条内点不交路(u,)(1≤i至k) 证明：在G外添加一点w,让w与v邻接(1ik)得H, H
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9 例2 设G是k连通图，u , v1,v2,…,vk为G中k+1个不同顶 点。求证：G中有k条内点不交路(u ,vi) (1≦i≦k) 证明：在G外添加一点w,让w与vi邻接(1≦i≦k)得H. G v1 u v2 vk H v1 u v2 vk w
由例1，H是k连通的，于是由定理2，u与w间存在k条 内点不交的u--w路，所以G中有k条内点不交路(u,) (1sisk)。 对于边连通度，有类似定理： 定理3（惠特尼1932）一个非平凡的图G是kk≥2)边连 通的，当且仅当G的任意两个顶点间至少存在k条边不重的 (u,v)路。 推论对于一个阶至少为3的无环图G,下面三个命题等价。 (1)G是2连通的： (2)G中任意两点位于同一个圈上； (3)G无孤立点，且任意两条边在同一个圈上。 10
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10 由例1，H是k连通的，于是由定理2，u与w间存在k条 内点不交的u---w路，所以 G中有k条内点不交路(u ,vi) (1≦i≦k)。 对于边连通度，有类似定理： 定理3 (惠特尼1932) 一个非平凡的图G是k (k≧2)边连 通的，当且仅当G的任意两个顶点间至少存在k条边不重的 (u ,v)路。 推论 对于一个阶至少为3的无环图G，下面三个命题等价。 (1) G是2连通的； (2) G中任意两点位于同一个圈上； (3) G无孤立点，且任意两条边在同一个圈上
证明：(1)→(2) G是2连通的，则G的任意两个顶点间存在两条内点不交 路P与P,显然这两条路构成包含该两个项点的圈。 (2)→(3) G无孤立点显然。设e,与e是G的任意两条边，在e,与e2上 分别添加两点u与v得图H,则H是2连通的，由(1)→(2)，H的 任意两个顶点在同一个圈上，即u与v在同一个圈上，也即e 与e2在同一个圈上。 (3)→(1) 设u与v是无环图G的任意两个不相邻顶点，由于G无孤立 点，所以可设e1,e2分别与u,v相关联。由(3)，e1,e2在同 一个圈上，所以u与v在同一个圈上，因此分离u与v至少要 去掉两个顶点，即证明G是2连通的
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 11 证明：(1)→(2) G是2连通的,则G的任意两个顶点间存在两条内点不交 路P1与P2,显然这两条路构成包含该两个顶点的圈。 G无孤立点显然。设e1与e2是G的任意两条边，在e1与e2上 分别添加两点u与v得图H，则H是2连通的，由(1)→(2)，H的 任意两个顶点在同一个圈上，即u与v在同一个圈上，也即e1 与e2在同一个圈上。 (2)→(3) (3)→(1) 设u与v是无环图G的任意两个不相邻顶点，由于G无孤立 点，所以可设e1,e2分别与u, v相关联。由(3),e1,e2在同 一个圈上，所以u与v在同一个圈上，因此分离u与v至少要 去掉两个顶点，即证明G是2连通的