顶点连通度

顶点连通度（vertex connectivity）衡量至少删除多少顶点才能破坏图的连通性。对于连通且非完全的有限无向简单图，顶点连通度 $\kappa (G)$ 是使剩余图不连通的顶点集合的最小大小。它把单个割点的概念推广为多个顶点共同形成的分离集。

一个环上没有割点，因为删一个顶点后还留下一条路径；但删两个不相邻顶点会把环切开，因此长度至少四的环的顶点连通度为二。这个量度关心顶点失效后的整体连接，而不只是每个顶点有多少邻居。

分离集与边界约定

若 $S\subseteq V(G)$，删除 $S$ 指取诱导子图 $G-S=G[V(G)\setminus S]$。当剩下至少两个顶点且它们之间有不同分量时，$S$ 是一个顶点分离集。对非连通图取 $\kappa (G)=0$；对完全图 $K_n$ 取 $\kappa (K_n)=n-1$，包括 $\kappa (K_1)=0$。本文只讨论非空图。

完全图的约定须单独交代：从 $K_n$ 中删除少于 $n-1$ 个顶点，余图仍是完全图而连通；删 $n-1$ 个只剩一个顶点，并没有变成含至少两个分量的图。若只使用“删后不连通”的最小化定义，就找不到完全图的有限分离集，必须采用上述标准延拓或明确另用无穷约定。

称图为k顶点连通，通常要求顶点数大于 $k$，且删除少于 $k$ 个顶点后仍连通。于是连通的非完全图恰有 $\kappa (G)\ge k$ 时满足该条件。证明一个具体值需要两半：说明更少删除均不够，并给出达到该数目的分离集。

轮图的完整计算

考虑五顶点轮图：四个外围顶点按 $a,b,c,d,a$ 连成四环，中心 $o$ 与四个外围点都相邻。这里“轮图”用具体顶点和边定义，避免不同资料对下标的命名差异。

外围顶点度为三，中心度为四。中心提供绕行路线，外围环在中心被删后继续保持连接。

下界。 删除至多两个顶点。如果中心 $o$ 仍在，所有留下的外围点都与它相连，所以余图连通。如果中心被删，那么至多再删一个外围点；四环删零个或一个顶点后分别是环或三顶点路径，仍连通。两种情况覆盖全部删除方式，故 $\kappa (G)\ge 3$。

上界。 删除 $\{o,b,d\}$，剩下外围对顶点 $a,c$，二者没有边，余图不连通。因此 $\kappa (G)\le 3$。合起来得到 $$\kappa (G)=3.$$ 下界来自对所有小集合的分类，上界来自一个具体集合。只展示某三个顶点能切断图，并不能排除只删一两个就成功的可能。

最小度提供的上界

令 $\delta (G)$ 为最小顶点度。对于非空简单图，有标准上界 $$\kappa (G)\le \delta (G).$$

证明。 非连通图左端为零，结论显然；完全图两端都为 $n-1$。剩下考虑连通非完全图，取最小度顶点 $v$。因图非完全，最小度小于 $n-1$，故至少存在一个不同于 $v$ 且不与它相邻的顶点 $w$。删除 $v$ 的全部邻居 $N(v)$ 后，$v$ 成为孤立点，$w$ 仍在，所以余图不连通。这给出大小为 $\mathrm{deg}(v)=\delta (G)$ 的分离集。

轮图中最小度为三，这一证明正给出 $N(a)=\{b,d,o\}$ 的三点分离集。但最小度大不保证连通度同样大：两个完全图 $K_4$ 只共享一个顶点 $v$，其最小度为三；删除 $v$ 就把两边分开，连通度只有一。度数是局部邻居数量，分离集还取决于各区域如何拼接。

新边、删点与有解答的变式

在固定顶点集上增加边，不会减小顶点连通度：任何删点后原来存在的连接路线仍保留。这个单调性不表示增加一条边一定使数值增加，原有最小分离集可能仍然有效。

变式。 将主例中中心到外围点 $a$ 的边 $oa$ 删除。此时 $a$ 的度降为二，所以 $\kappa \le 2$；删除 $b,d$ 的确使 $a$ 孤立，而 $o,c$ 仍相连。另一方面，删任何一个顶点仍连通：删中心时留四环；删 $a$ 时中心连接其余外围点；删 $c$ 时 $a$ 经 $b$ 或 $d$ 接中心；删 $b$ 或 $d$ 时另一个仍连接 $a$ 与中心。故新图连通度恰为二。

点连通度与边连通度分别限制顶点失效和边失效。若把一座中转设施视为顶点，删除它会同时删除多条关联边；删除一条线路则只影响一条边。两种量度针对不同失效模型，不能只由边数替代顶点数。