基于k-连通图定义证明完全图$K_n$连通度的技术问询

嘿，我看你现在正练图论里k-连通图的证明题呢，刚好之前啃这块的时候踩过不少小坑，就着你给的定义，咱们一步步把完全图$K_n$连通度的证明捋明白！

先把咱们要用到的核心定义再明确一遍，毕竟证明的根基就是定义，可不能跑偏：

定义回顾 #

k-连通图的定义 #

一个图$G$被称为$k$-连通的，必须同时满足俩条件：

• 图的顶点数$|V(G)| > k$
• 不管你挑哪个顶点子集$T$（只要$T$的大小小于$k$），把$T$里的顶点都删掉之后，剩下的子图还是连通的

连通度的定义 #

对于连通图$G$，它的连通度是$k$，要么是：

• $k$是能让$G$成为k-连通图的最大自然数；要么是
• 当$G$只有1个顶点时，按特殊规则定义连通度（一般这儿默认是0，咱们严格按你给的描述来）

接下来咱们分情况对着完全图$K_n$来证：

情况1：$n=1$（单点图） #

直接按连通度的特殊定义来就行，没什么好说的，就是定义里指定的那个情况。

情况2：$n\geq2$ #

咱们要证的是：完全图$K_n$的连通度是$n-1$，分两步来：

第一步：先证$K_n$是$(n-1)$-连通的 #

对照k-连通图的两个条件来卡：

1. 顶点数条件：$K_n$有$n$个顶点，$n > n-1$（毕竟$n\geq2$），这条件直接满足；
2. 删点子图连通性：随便挑一个顶点子集$T$，只要$|T| < n-1$，那删掉$T$之后剩下的顶点数是$n - |T|$。因为$|T| < n-1$，所以剩下的顶点数肯定大于1。
   别忘了$K_n$是完全图——原来任意两个顶点之间都有边，删掉$T$之后，剩下的顶点之间的边全还在啊！那不管剩下多少个顶点（只要多于1），随便找俩点，直接有边连着重，剩下的子图肯定是连通的。
   这就把第二个条件也满足了，所以$K_n$确实是$(n-1)$-连通的。

第二步：再证没有比$n-1$更大的k能让$K_n$成为k-连通图 #

咱们反过来看，假设存在一个k比$n-1$大，那最小的就是k=n对吧？那咱们看看$K_n$能不能是n-连通的：
对照k-连通图的第一个条件，要求$|V(G)| > k$，也就是$n > n$——这明显不可能啊，矛盾了。那比n还大的k就更不用想了，连n都不满足，更大的数肯定也不行。
另外你也可以这么理解：要是真删了n-1个顶点，$K_n$就剩1个点了，但k-连通图的定义里只要求删去少于k个顶点的情况，删n-1个顶点刚好是等于k=n-1的情况，不在要求范围内，所以不影响咱们的结论。

所以啊，$n-1$就是能让$K_n$成为k-连通图的最大自然数，那它的连通度就是$n-1$了。

最后总结一下 #

• $n=1$时，按特殊定义算连通度；
• $n\geq2$时，$K_n$的连通度是$n-1$。

备注：内容来源于stack exchange，提问作者NTc5