情形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 连通的