仙人掌基网络的1,2-额外连通度

The 1,2-Extra Connectivity of Cactus-Based Networks

摘要: 连通度是评估网络可靠性的经典指标。根据故障处理器的分布情况，网络的条件连通性受到了广泛关注。本文旨在研究仙人掌基网络的1-额外连通度和2-额外连通度，为大规模并行计算系统和分布式网络的拓扑设计提供理论支持。

Abstract: Connectivity serves as a fundamental metric for evaluating network reliability. Based on the distribution of faulty processors, the conditional connectivity of a network has received much attention. This paper aims to investigate the 1-extra connectivity and 2-extra connectivity of cactus-based networks, providing theoretical support for the topological design of large-scale parallel computing systems and distributed networks.

1. 引言

随着信息技术的飞速发展，大规模并行计算系统和分布式网络的应用日益广泛，网络拓扑结构的设计与优化成为研究热点。网络拓扑的可靠性直接影响到系统的容错性和性能，因此，如何设计具有高可靠性和强容错能力的网络结构成为了一个重要课题。仙人掌基网络(Cactus-based Networks)作为一种特殊的层次化网络结构，因其独特的拓扑性质和良好的容错能力，受到了广泛关注。仙人掌基网络基于对换生成的凯莱图构建，具有对称性和高连通性，能够有效应对节点或链路故障，确保网络的稳定运行。本文旨在研究仙人掌基网络的1-额外连通度和2-额外连通度，为大规模并行计算系统和分布式网络的拓扑设计提供理论支持。

2. 预备知识

2.1. 术语和概念

设$G=\left(V\left(G\right),E\left(G\right)\right)$ 是一个简单有限图，其中$V\left(G\right)$ 表示点集，$E\left(G\right)$ 表示边集。$\left(x,y\right)$ 表示点$x$ 和点$y$ 之间的边，文中有时简记为$xy$ 。对于任意的点$u\in V\left(G\right)$ ，用$N_G\left(u\right)=\left\{w\in V\left(G\right)|\left(u,w\right)\in E\left(G\right)\right\}$ 表示$u$ 在$G$ 中的邻点集，用$d\left(u\right)=\left|N_G\left(u\right)\right|$ 表示$u$ 在图$G$ 中的度。对于图$G$ 的顶点集$S$ ，用$N_G\left(S\right)=\left\{w\in V\left(G\right)\backslash S|\exists u\in S,\left(u,w\right)\in E\left(G\right)\right\}$ 表示$S$ 的开邻集，$N\left[S\right]=N\left(S\right)\cup S$ 表示$S$ 的闭邻集。当图$G$ 可以从文中清楚看出时，用$N\left(u\right)$ 代替$N_G\left(u\right)$ ，用$N\left(S\right)$ 代替$N_G\left(S\right)$ 。对于图$G$ 的两个顶点集$A$ 和$B$ ，用$E\left(A,B\right)=\left\{\left(x,y\right)|x\in A,y\in B\right\}$ 表示$A$ 和$B$ 之间的边集，用$\left|E\left(A,B\right)\right|$ 表示顶点集$A$ 和$B$ 之间的边数。用$G\left[H\right]$ 表示由$H$ 在$G$ 中诱导的子图。对于一个网络$G$ 的连通度是指删除某个顶点集后使$G$ 不连通的最小顶点集大小，记为$\kappa \left(G\right)$ 。如果$\kappa \left(G\right)\ge k$ ，则称$G$ 是k-连通的[1] [2]。

2.2. CN_n的拓扑结构性

设$S$ 是$\Gamma$ 的子集，$1_{\Gamma }$ 群$\Gamma$ 的单位元，且$S=S^{-1}$ 。凯莱图$Cay\left(\Gamma ,S\right)$ 是一个顶点集为$\Gamma$ ，边集为$\left\{\left(g,gs\right):g\in \Gamma ,s\in S\right\}$ 的图。

Figure 1. Cactus graph

图1. 仙人掌图

由换位生成的凯莱图$Cay\left(Sym\left(n\right),T\right)$ 有$n!$ 个顶点，其中$Sym\left(n\right)$ 是$\left\{1,2,\cdots ,n\right\}$ 上的对称群，$T$ 是$Sym\left(n\right)$ 上的换位集。设$G\left(T\right)$ 是具有$n$ 个顶点$\left\{1,2,\cdots ,n\right\}$ 的图，当且仅当换位$\left(ij\right)\in T$ 时，$G\left(T\right)$ 中有一条边$\left(i,j\right)$ 。图$G\left(T\right)$ 被称为$Cay\left(Sym\left(n\right),T\right)$ 的换位生成图。如果$T=\left\{\left(1i\right):2\le i\le n\right\}$ ，是$Sym\left(n\right)$ 上的换位集，则$G\left(T\right)$ 是一个星图，$Cay\left(Sym\left(n\right),T\right)$ 是著名的星图$S_n$ (Star graph)。如果$G\left(T\right)$ 是一个具有$n$ 个顶点的路径，则$Cay\left(Sym\left(n\right),T\right)$ 是冒泡排序图$B_n$ (Bubble sort graph)。如果$T=\left\{\left(ij\right):1\le i\ne j\le n\right\}$ 是$Sym\left(n\right)$ 上的换位集，则$G\left(T\right)$ 是一个完全图，$Cay\left(Sym\left(n\right),T\right)$ 是完全转置图$C{T}_n$ (Complete-transposition graph)。如果$G\left(T\right)$ 是一个环，则$Cay\left(Sym\left(n\right),T\right)$ 是修正冒泡排序图$M{B}_n$ (Modified bubble sort graph) [3]-[7]。

如果$T=\left\{\left(1i\right):2\le i\le 2n+1\right\}\cup \left\{\left(2j2j+1\right):1\le j\le n\right\}$ 是$Sym\left(n\right)$ 上的换位集，则$G\left(T\right)$ 是一个仙人掌图(见图1)，$Cay\left(Sym\left(n\right),T\right)$ 是仙人掌基网络$C{N}_n$ (Cactus-based networks) [8]。

详细定义如下。

定义2.1 [8]：$n$ 维仙人掌基网络$C{N}_n$ 的顶点集由$\left\{1,2,\cdots ,2n+1\right\}$ 上的所有$\left(2n+1\right)!$ 个置换组成。$\left\{1,2,\cdots ,2n+1\right\}$ 上的一个置换$u$ 记为$u_1{u}_2\cdots u_{2n+1}$ 。点$u=u_1{u}_2\cdots u_{2n+1}\in V\left(C{N}_n\right)$ 与点$v=v_1{v}_2\cdots v_{2n+1}\in V\left(C{N}_n\right)$ 相邻当且仅当以下情况之一成立：

(规则1) 存在整数$i\in \left\{2,3,\cdots ,2n+1\right\}$ ，使得$u_1=v_i$ ，$u_i=v_1$ ，且对每个$j\in \left\{1,2,\cdots ,2n+1\right\}\backslash \left\{1,i\right\}$ ，$u_i=v_i$ ，即交换第1位和第i位。

(规则2) 存在整数$i\in \left\{1,2,\cdots ,n\right\}$ ，使得$u_{2i}=v_{2i+1}$ ，$u_{2i+1}=v_{2i}$ ，且对每个$j\in \left\{1,2,\cdots ,2n+1\right\}\backslash \left\{2i,2i+1\right\}$ ，$u_i=v_i$ ，即交换第$2i$ 位和第$2i+1$ 位，其中$1\le i\le n$ 。

例如，在$C{N}_2$ 中，有$5!$ 个点，点$u=12345$ ，通过规则1交换第1位和第$i$ 位，连接$21345$ 、$32145$ 、$42315$ 、$52341$ 这4个点，通过规则2交换第$2i$ 位和第$2i+1$ 位，连接$13245$ 、$12354$ 这2个点。在$C{N}_n$ 中，有$\left(2n+1\right)!$ 个点，对于任意的点$u\in V\left(C{N}_n\right)$ ，$u$ 通过规则1连接$2n$ 个点，通过规则连接$n$ 个点，所以，$C{N}_n$ 是3n-正则的，$C{N}_n$ 包含$\frac{3n}{2}\left(2n+1\right)!$ 条边。

Figure 2. CN₁

图2. CN₁

Figure 3. CN₂

图3. CN₂

下面探讨仙人掌基网络$C{N}_n$ 的层次结构，当$n=1$ 时，$C{N}_1$ 有$3!$ 个点(见图2)；当$n=2$ 时，$C{N}_2$ 有$5!$ 个点，$C{N}_2$ 中有$4\times 5$ 个$C{N}_1$ 的拷贝(见图3)；当$n=3$ 时，$C{N}_3$ 有$7!$ 个点，$C{N}_3$ 中有$6\times 7$ 个$C{N}_2$ 的拷贝。在$C{N}_n$ 中，有$\left(2n+1\right)!$ 个点，有$2n\left(2n+1\right)$ 个$C{N}_{n-1}$ 的拷贝，可以固定最后两个系数，将这些$C{N}_{n-1}$ 的拷贝依次记为$C{N}_n^{1,2},C{N}_n^{1,3},\cdots ,C{N}_n^{1,2n+1},C{N}_n^{2,1},\cdots ,C{N}_n^{2,2n+1},\cdots ,C{N}_n^{2n，(2n+1)}$ ，或者简记为$C{N}_n^1,C{N}_n^2,\cdots ,C{N}_n^{2n(2n+1)}$ 。其中，对任意正整数$i\in \left\{1,2,\cdots ,2n\left(2n+1\right)\right\}$ ，$C{N}_n^i$ 与$C{N}_{n-1}$ 同构，所以$V\left(C{N}_n^i\right)=\frac{\left(2n+1\right)!}{2n\left(2n+1\right)}=\left(2n-1\right)!$ ，仙人掌基网络具有良好的层次结构。

命题2.2：仙人掌基网络$C{N}_n$ 具有以下性质。

1) $C{N}_n$ 有$\left(2n+1\right)!$ 个点，$\frac{3n}{2}\left(2n+1\right)!$ 条边，$C{N}_n$ 是3n-正则的，对任意正整数$i\in \left\{1,2,\cdots ,2n\left(2n+1\right)\right\}$ ，$V\left(C{N}_n^i\right)=\frac{\left(2n+1\right)!}{2n\left(2n+1\right)}=\left(2n-1\right)!$ 。

2) $C{N}_n$ 是二部图。

3) 当$n\ge 2$ 时，对任意正整数$i\in \left\{1,2,\cdots ,2n\left(2n+1\right)\right\}$ ，对任意的$u\in V\left(C{N}_n^i\right)$ ，在$N_{C{N}_n}\left(u\right)$ 中，恰有3个点分布在$V\left(C{N}_n\right)\backslash V\left(C{N}_n^i\right)$ 中。

4) 设$\left\{p,q,s,t\right\}\subseteq \left\{1,2,\cdots ,2n+1\right\}$ ，在$C{N}_n^{p,q}$ 和$C{N}_n^{q,p}$ 之间有$\left(2n-1\right)!$ 条独立边；在$C{N}_n^{p,q}$ 和$C{N}_n^{s,q}$ 之间有$\left(2n-2\right)!$ 条独立边；在$C{N}_n^{p,q}$ 和$C{N}_n^{p,s}$ 之间有$\left(2n-2\right)!$ 条独立边；在$C{N}_n^{p,q}$ 和$C{N}_n^{s,t}$ 之间没有边。

证明：

1) 前文叙述可得。

2) 一次交换会改变一个排列的奇偶性，其中一次交换对应于生成集的生成元。例如$C{N}_1$ 就是一个完全二部图。

3) $C{N}_n$ 是3n-正则的，$C{N}_{n-1}$ 是$\left(3n-3\right)$ -正则的，在$C{N}_n$ 中，对任意的$u\in V\left(C{N}_n^i\right)$ ，$C{N}_n^i$ 和$C{N}_{n-1}$ 同构，所以$N_{C{N}_n^i}\left(u\right)=3n-3$ ，$N_{C{N}_n\backslash C{N}_n^i}\left(u\right)=3$ 。

4) 对任意的$u\in V\left(C{N}_n^{p,q}\right)$ ，设$u=\left(u_1,u_2,\cdots ,u_{2n-1},p,q\right)$ ，由规则2可知$u$ 与$\left(u_1,u_2,\cdots ,u_{2n-1},q,p\right)$ 相邻，固定$p,q$ ，任取$u_1,\cdots ,u_{2n-1}$ ，得到第1)条结论；由规则1可知，$u$ 与$\left(p,u_2,\cdots ,u_{2n-1},u_1,q\right),\left(q,u_2,\cdots ,u_{2n-1},p,u_1\right)$ ，相邻，固定$u_1,p,q$ ，任取$u_2,\cdots ,u_{2n-1}$ ，得到第2)、3)条结论；其他情况无边相连，得到第4)条结论。

3. 仙人掌基网络CN_n的连通度

由于仙人掌图中含有三角形，只使用[9]中含有三角形情况的定理。

引理3.1 [9]：设$G$ 设是由具有$m$ 条边，在$\left\{1,2,\cdots ,n\right\}$ 上的生成图$A$ 得到的凯莱图，且$m\ge 7$ 。假设$T$ 是$G$ 的一个点集，当$A$ 中有三角形时$\left|T\right|\le 2m-3$ 。那么以下情况之一成立：

1) $G-T$ 连通。

2) $G-T$ 不连通，恰好有两个分支，并且其中一个分支为一个孤立点。

3) 生成图$A$ 有三角形，$G-T$ 不连通，恰好有三个分支，其中两个分支为孤立点，并且$\left|T\right|=2m-3$ 。

引理3.2 [9]：设$G$ 设是由具有$m$ 条边，在$\left\{1,2,\cdots ,n\right\}$ 上的生成图$A$ 得到的凯莱图，且$n\ge 4$ 。则$G$ 中不包含$K_{2,4}$ 作为子图。另外，如果$A$ 中没有$K_3$ ，则$G$ 中不包含$K_{2,3}$ 作为子图。

定理3.3：对仙人掌基网络$C{N}_n$ ，$n\ge 3$ 时，$\kappa \left(C{N}_n\right)=3n$ 。

证明：一方面，显然有$\kappa \left(C{N}_n\right)\le \delta \left(C{N}_n\right)\le 3n$ 。

另一方面，设仙人掌基网络$C{N}_n$ 在$\left\{1,2,\cdots ,n\right\}$ 上的生成图为$A$ ，$A$ 中存在三角形，并且$A$ 有$3n$ 条边，对$C{N}_n$ 任意割集$F$ ，有$\left|F\right|\le 3n\le 6n-3$ ，由引理3.1可知，以下情况之一成立：

1) $C{N}_n-F$ 中恰好有两个分支，并且其中一个分支为一个孤立点。

2) $C{N}_n-F$ 中恰好有三个分支，其中两个分支为孤立点，并且$\left|F\right|=6n-3$ 。

若为情况1)，因为其中一个分支为孤立点，所以割集$F$ 为这个孤立点的邻集，$C{N}_n$ 是$3n$ -正则的，所以$\left|F\right|=3n$ 。若为情况2)，此时$\left|F\right|=6n-3$ ，结合$\left|F\right|\le 3n\le 6n-3$ 可知$n=1$ ，有$\left|F\right|=3n$ 。所以$\kappa \left(C{N}_n\right)=3n$ 。

定义3.4 [10]：对$G$ 的一个割集$F$ ，如果$G-F$ 的分支中不存在孤立点，则称$F$ 为$G$ 的一个超割集。称$G$ 的最小超割集的大小为超连通度，记为$\kappa \prime \left(G\right)$ 。

定义3.5 [11]：对$G$ 的一个割集$F$ ，如果$G-F$ 的分支点数均大于$g$ ，则称$F$ 为$G$ 的一个g-额外割集。称$G$ 的最小g-额外割集的大小为g-额外连通度，记为${\kappa }^g\left(G\right)$ 。

定理3.6：对仙人掌基网络$C{N}_n$ ，$n\ge 4$ 时，$\kappa \prime \left(G\right)=6n-2$ 。

证明：任取$C{N}_n$ 的一条边$xy$ ，取$F=N_{C{N}_n}\left(xy\right)$ ，由于$C{N}_n$ 是二部图，所以$x$ 和$y$ 没有公共邻点，结合$C{N}_n$ 是3n-正则的，可知$\left|N_{C{N}_n}\left(x\right)\right|=\left|N_{C{N}_n}\left(y\right)\right|=3n-1$ ，从而$\left|F\right|=6n-2$ 。

若$C{N}_n-F$ 存在孤立点分支$u$ ，$u$ 只能和$N_{C{N}_n}\left(x\right)$ 或$N_{C{N}_n}\left(y\right)$ 中的点相邻，$d\left(u\right)=3n$ ，所以$u$ 在$N_{C{N}_n}\left(x\right)$ 中$N_{C{N}_n}\left(y\right)$ 均有邻点，分别设为$x\prime$ 和$y\prime$ ，则$xyy\prime ux\prime x$ 为一个5-长圈(见图4)，与$C{N}_n$ 是二部图矛盾，$C{N}_n-F$ 不存在孤立点分支。所以$\kappa \prime \left(G\right)\le 6n-2$ 。

若$C{N}_n$ 中存在割集$F\prime$ ，使得$\left|F\prime \right|\le 6n-3$ ，由引理3.1可知，以下情况之一成立：

1) 恰好有两个分支，并且其中一个分支为一个孤立点。

2) 恰好有三个分支，其中两个分支为孤立点，并且$\left|F\prime \right|=6n-3$ 。

不论哪种情况$F\prime$ 都不是超割集，所以$\kappa \prime \left(G\right)=6n-2$ 。

Figure 4. Illustration for Theorem 3.6

图4. 定理3.6的图例

定理3.7：对仙人掌基网络$C{N}_n$ ，$n\ge 4$ 时，${\kappa }^2\left(C{N}_n\right)=9n-6$ 。

证明：仙人掌基网络$C{N}_n$ 的生成图$A$ 中含有三角形，由引理3.2知，$C{N}_n$ 中没有$K_{2,4}$ 作为子图，而$C{N}_n$ 中含有$C{N}_1$ ，所以$C{N}_n$ 中存在$K_{2,3}$ ，任取$C{N}_n$ 中一个2-长路$uvw$ ，且$\left|N\left(u\right)\cap N\left(w\right)\right|=3$ ，取$F=N_{C{N}_n}\left(uvw\right)$ ，$F_1=N_{C{N}_n}\left(u\right)-\left\{v\right\}$ ，$F_2=N_{C{N}_n}\left(v\right)-\left\{u,w\right\}$ ，$F_3=N_{C{N}_n}\left(w\right)-F_1-\left\{v\right\}$ ，不难发现$\left|F_1\right|=3n-1$ ，$\left|F_2\right|=3n-2$ ，$\left|F_3\right|=3n-3$ ，所以$\left|F\right|=9n-6$ 。

若$C{N}_n-F$ 存在孤立点分支$x$ ，$d_F(x)=3n$ ，若$x$ 与$F_2$ 中的点相邻，则必会与$F\backslash F_2$ 中的点相邻，会出现5-长圈，与$C{N}_n$ 是二部图矛盾；又因为$C{N}_n$ 中没有$K_{2,4}$ ，所以$x$ 邻$F_1$ 中至多3个点，同理$x$ 邻$F_3$ 中至多1个点，这与$d\left(x\right)=3n$ 矛盾。

若$C{N}_n\backslash F$ 存在一个分支$H$ ，$\left|H\right|=2$ ，设$x,y\in V\left(H\right)$ ，由$C{N}_n$ 是3n-正则的二部图可知，$N_F\left(x\right)\cap N_F\left(y\right)=\varnothing$ ，$\left|N_F\left(x\right)\right|=\left|N_F\left(y\right)\right|=3n-1$ ，若$x$ 与$F_2$ 中的点相邻，则必会与$F\backslash F_2$ 中的点相邻，会出现5-长圈，与$C{N}_n$ 是二部图矛盾，$y$ 同理不与$F_2$ 中的点相邻，所以$N_F\left(x\right)$ ，$N_F\left(y\right)\subseteq F\backslash F_2$ ，有$6n-2=\left|N_F\left(y\right)\right|\le \left|F\backslash F_2\right|=6n-4$ ，矛盾。

所以$F$ 为$C{N}_n$ 的2-额外割集，${\kappa }^2\left(C{N}_n\right)\le 9n-6$ 。设$F$ 为$C{N}_n$ 的最小2-额外割集，$\left|F\right|\le 9n-7$ ，定义

$C{N}_n^k\cap F=F_k,k\in \left\{1,2,\cdots ,2n\left(2n+1\right)\right\}$

$I=\left\{i|i\in \left[n\right],\left|T_i\right|\ge 3n-3\right\},J=\left\{j|j\in \left[n\right],\left|T_j\right|\le 3n-4\right\}$

$T_I={\cup }_{i\in I}{T}_i,C{N}_n^I={\cup }_{i\in I}C{N}_n^i$

可知$\left|I\right|\le 3$ ，否则$3\left(3n-3\right)\le \left|F_I\right|\le \left|F\right|\le 9n-7$ ，和$n\ge 4$ 矛盾。(若无特殊说明，下文均默认$i\in I$ ，$j\in J$ )。

将$2n\left(2n+1\right)$ 个$C{N}_{n-1}$ 块按照$C{N}_n^{1,2},\cdots ,C{N}_n^{1,2n+1},C{N}_n^{2,2n+1},\cdots ,C{N}_n^{2n,2n+1},\cdots ,C{N}_n^{2n,1},C{N}_n^{2n+1,1},\cdots ,C{N}_n^{2n+1,2n}$ 的顺序依次排列，从而保证每两个相邻的$C{N}_{n-1}$ 块之间存在$\left(2n-2\right)!$ 条独立边，并且$C{N}_n^{1,k}$ 和$C{N}_n^{k,1}$ 之间存在$\left(2n-1\right)!$ 条独立边(见图5)，$k\in \left\{2,3,\cdots ,2n+1\right\}$ 。因为$C{N}_n^j-F_j$ 不会产生新的连通分支，所以$C{N}_n^{\{1,2,\mathrm{...},n\}\backslash I}-F$ 之间是相互连通的，即$C{N}_n-F$ 产生的较小分支只能出现在$C{N}_n^I-F$ 中。

Figure 5. Illustration for Theorem 3.7

图5. 定理3.7的图例

对$C{N}_n$ 中任意一个2-长路$uvw$ ，有$N\left(uvw\right)\ge \left(3n-1\right)+\left(3n-2\right)+\left(3n-3\right)=9n-6$ ，所以$C{N}_n-F$ 产生的最小分支点数应大于3。

情况1：$\left|I\right|=1$

在$C{N}_n^i$ 中，点数大于等于$3n-3$ 的割集，即所有$C{N}_n^i-F_i$ 中至多只有一个会产生不连通分支。若$C{N}_n^i-F_i$ 中的分支和其他分块中的点相连，则$C{N}_n-F$ 连通，矛盾。所以$C{N}_n^i-F_i$ 中存在至少一个分支$H$ 支也是$C{N}_n-F$ 中的分支，并且$\left|H\right|\ge 3$ ，可知$H$ 中存在一个2-长路$uvw$ ，并且$\left|N_{C{N}_n^i}\left(uvw\right)\right|\ge 9n-15$ ，所以$\left|N_{C{N}_n^i}\left(H\right)\right|\ge 9n-15-\left|H\right|+3=9n-12-\left|H\right|$ ，而$\left|N_{C{N}_n\backslash C{N}_n^i}\left(H\right)\right|=3\left|H\right|$ ，又$N_{C{N}_n}\left(H\right)\subset F$ ，所以$\left|F\right|\ge \left|N_{C{N}_n^i}\left(H\right)\right|+\left|N_{C{N}_n\backslash C{N}_n^i}\left(H\right)\right|\ge 9n-12+2\left|H\right|$ ，这和$\left|F\right|\le 9n-7$ 矛盾。

情况2：$\left|I\right|=2$ ，设$I=\left\{i_1,i_2\right\}$

在$C{N}_n^i$ 中，点数大于等于$3n-3$ 的割集，即所有$C{N}_n^i-F_i$ 中至多只有两个会产生不连通分支。现不妨设$\left|F_{i_1}\right|\le \left|F_{i_2}\right|$ ，结合对集合$I$ 的定义可知，$3n-3\le \left|F_{i_1}\right|\le \frac{9n-7}{2}$ ，$\frac{9n-7}{2}\le \left|F_{i_2}\right|\le 6n-4$ 。

若$C{N}_n^i-F_i$ 中不出现孤立点，则$\left|F_i\right|\ge \kappa \prime \left(C{N}_n^i\right)=6n-8$ ；若$C{N}_n^i-F_i$ 中出现至少两个孤立点$u_1,u_2$ ，则$\left|F_i\right|\ge \left|N\left(u_1\right)\right|+\left|N\left(u_2\right)\right|-3\ge 6n-9$ 。

所以$C{N}_n^{i_1}-F_{i_1}$ 中有且仅有一个孤立点，不妨设为$u$ 。若$C{N}_n^{i_1}-F_{i_1}-\left\{u\right\}$ 中的分支数大于等于2，说明$F_{i_1}\cup \left\{u\right\}$ 至少为一个2-额外割集，有$\left|F_{i_1}\right|+1\ge \kappa \prime \left(C{N}_n^i\right)=6n-8$ ，这显然矛盾。说明$C{N}_n^{i_1}-F_{i_1}$ 只产生了两个分支，并且其中一个为孤立点。

联系前文对$2n\left(2n+1\right)$ 个$C{N}_n^i$ 块的排序，$\left|F_{i_1}\right|\le \left|F_{i_2}\right|\le 6n-4\le \left(2n-2\right)!$ ，可知$C{N}_n^{i_1}-F_{i_1}$ 产生较大的那个分支和$C{N}_n^{i_2}-F_{i_2}$ 中产生的部分分支会与$C{N}_n^{\{1,2,\cdots ,n\}\backslash I}-F$ 连通，现只考虑$C{N}_n^{i_2}-F_{i_2}$ 中不与$C{N}_n^{\{1,2,\mathrm{...},n\}\backslash I}-F$ 连通的分支。不妨设其中一个为$H\prime$ ，若$C{N}_n^{i_1}-F_{i_1}$ 中产生的点分支$u$ 不与$H\prime$ 相邻，即$H\prime$ 为$C{N}_n-F$ 中的一个分支，此时证明过程类似情况1。

可知$C{N}_n^{i_1}-F_{i_1}$ 中产生的点分支$u$ 与$H\prime$ 相连，即$H\prime \cup \left\{u\right\}$ 为$C{N}_n-F$ 中的一个分支，若$\left|H\prime \right|=2$ ，可知$\left|N_{C{N}_n}\left(H\prime \cup \left\{u\right\}\right)\right|\ge 9n-6$ ，和$N_{C{N}_n}\left(H\prime \cup \left\{u\right\}\right)\subset F$ 矛盾。所以$\left|H\prime \right|\ge 3$ ，可得$H\prime$ 中存在2-长路，设为$uvw$ ，并且$\left|N_{C{N}_n^{i_2}}\left(uvw\right)\right|\ge 9n-15$ ，所以$\left|N_{C{N}_n^{i_2}}\left(H\prime \right)\right|\ge 9n-15-\left|H\prime \right|+3=9n-12-\left|H\prime \right|$ ，而另一方面$\left|N_{C{N}_n\backslash C{N}_n^{i_2}}\left(H\prime \right)\right|=3\left|H\prime \right|$ ，又因为$u$ 与$H\prime$ 相连，有$N_{C{N}_n}\left(H\prime \right)\backslash \left\{u\right\}\subset F$ ，所以$\left|F\right|\ge \left|N_{C{N}_n^i}\left(H\right)\right|+\left|N_{C{N}_n\backslash C{N}_n^i}\left(H\right)\right|-\left|\left\{u\right\}\right|\ge 9n-13+2\left|H\right|$ ，这和$\left|F\right|\le 9n-7$ 矛盾。

情况3：$\left|I\right|=3$ ，$i\in I$

在$C{N}_n^i$ 中，点数大于等于$3n-3$ 的割集，即所有$C{N}_n^i-F_i$ 中至多只有三个会产生不连通分支。由集合$I$ 的定义可知，$3n-3\le \left|F_i\right|\le 3n-1$ ，类似情况2的讨论可知，$C{N}_n^i-F_i$ 只产生了两个分支，并且其中一个为孤立点。类似讨论可知，$C{N}_n-F$ 中产生最小的分支只能是三个孤立点相连组成的2-长路，这和$\left|F\right|\le 9n-7$ 矛盾。

综上，${\kappa }^2\left(G\right)=9n-6$ 。