# The generalized $4$-connectivity of bubble-sort graphs

Leyou Xu, Bo Zhou111Corresponding author. E-mail<EMAIL_ADDRESS>
School of Mathematical Sciences, South China Normal University
Guangzhou 510631, P.R. China

###### Abstract

For $S\subseteq V(G)$ with $|S|\geq 2$, let $\kappa_{G}(S)$ denote the maximum
number of internally disjoint trees connecting $S$ in $G$. For $2\leq k\leq
n$, the generalized $k$-connectivity $\kappa_{k}(G)$ of an $n$-vertex
connected graph $G$ is defined to be $\kappa_{k}(G)=\min\\{\kappa_{G}(S):S\in
V(G)\mbox{ and }|S|=k\\}$. The generalized $k$-connectivity can serve for
measuring the fault tolerance of an interconnection network. The bubble-sort
graph $B_{n}$ for $n\geq 2$ is a Cayley graph over the symmetric group of
permutations on $[n]$ generated by transpositions from the set
$\\{[1,2],[2,3],\dots,[n-1,n]\\}$. In this paper, we show that for the bubble-
sort graphs $B_{n}$ with $n\geq 3$, $\kappa_{4}(B_{n})=n-2$.

Keywords:  generalized $4$-connectivity, internally disjoint trees, bubble-
sort graphs, Cayley graphs

##  1 Introduction

An interconnection network is usually modelled by its topological graph, a
connected graph $G$ with vertex set $V(G)$ and edge set $E(G)$, where vertices
represent processors and edges represent communication links between
processors. For an interconnection network, one mainly concerns about the
reliability and fault tolerance, which usually can be measured by the
traditional connectivity of its topological graph. The connectivity
$\kappa(G)$ of a graph $G$ is defined to be the minimum cardinality of a
subset $S\in V(G)$ such that $G-S$ is disconnected or trivial. A graph $G$ is
said to be $k$-connected if $\kappa(G)\geq k$. For each $2$-subset $\\{x,y\\}$
of vertices of $G$, let $\kappa_{G}(x,y)$ denote the maximum number of
internally vertex disjiont $(x,y)$-paths in $G$. A well-known theorem of
Whitney [22] says that $\kappa(G)=\min\\{\kappa_{G}(x,y):\\{x,y\\}\subseteq
V(G)\\}$.

For a set $S$ of vertices in a connected graph $G$ and trees
$T_{1},\dots,T_{\ell}$ in $G$, we say $T_{1},\dots,T_{\ell}$ are $\ell$
internally edge disjoint trees connecting $S$ in $G$ if these trees are
pairwise edge disjoint and $V(T_{i})\cap V(T_{j})=S$ for every pair $i,j$ of
distinct integers with $1\leq i,j\leq\ell$.

Chartrand et al. [3] and Hager [8] proposed the concept of the generalized
$k$-connectivity of an $n$-vertex graph $G$ for $k=2,\dots,n$, see also [9,
4]. For any set $S$ of vertices of $G$ with $|S|\geq 2$, the generalized
connectivity of $S$, written as $\kappa_{G}(S)$, is the maximum number of
internally disjoint trees connecting $S$ in $G$. For $2\leq k\leq|V(G)|$, the
generalized $k$-connectivity (or $k$-tree connectivity) of $G$,
$\kappa_{k}(G)$, is the minimum value for $\kappa_{G}(S)$ over all subsets $S$
of vertices with $|S|=k$. Note that $\kappa_{2}(G)$ is the connectivity of
$G$, and $\kappa_{n}(G)$ is the maximum number of edge disjoint spanning trees
contained in $G$ [19, 21] (or the spanning tree packing number of $G$ [20]).
The generalized $k$-connectivity has been used to measure the capability of a
network to connect any $k$ vertices.

Cayley graphs have been used extensively to design interconnection networks.
The Cayley graph $\mbox{Cay}(X,S)$, where $X$ is a group with identity $e$,
$e\not\in S\subseteq X$ and $S$ is closed under inversion, is the graph with
vertex set $X$, such that $g$ and $h$ for $g,h\in X$ are adjacent if and only
if $h=gs$ for some $s\in S$.

Denote $\mbox{Sym}(n)$ the symmetric group (i.e., the group of all
permutations) on $[n]=\\{1,\dots,n\\}$. For convenience, we use
$(p_{1},\dots,p_{n})$ to denote the permutation $\sigma$ such that
$\sigma(i)=p_{i}$ for $i\in[n]$, and $[i,j]$ with $1\leq i<j\leq n$ to denote
the permutation $(1,\dots,i-1,j,i+1,\dots,j-1,i,j+1,\dots,n)$, which is called
a transposition. The composition $\sigma\pi$ of permutations $\sigma$ and
$\pi$ is the function that maps any element $i\in[n]$ to $\sigma(\pi(i))$.
Thus

$(p_{1},\dots,p_{i},\dots,p_{j},\dots,p_{n})[i,j]=(p_{1},\dots,p_{j},\dots,p_{i},\dots,p_{n}),$

which swaps the objects at positions $i$ and $j$.

Let $\mathcal{T}$ be a set of transpositions from $[n]$. The (transposition
generating) graph of $\mathcal{T}$, denoted by $G_{\mathcal{T}}$, is the graph
with vertex set $[n]$ such that, for $i,j\in[n]$, vertices $i$ and $j$ are
adjacent if and only if $[i,j]\in\mathcal{T}$. It is known that the Cayley
graph $\mbox{Cay}(\mbox{Sym}(n),\mathcal{T})$ is connected if and only if
$G_{\mathcal{T}}$ is connected. If $G_{\mathcal{T}}$ is the star, then
$\mbox{Cay}(\mbox{Sym}(n),\mathcal{T})$ is called a star graph, denoted by
$S_{n}$. If $G_{\mathcal{T}}$ is the path, then
$\mbox{Cay}(\mbox{Sym}(n),\mathcal{T})$ is called a bubble-sort graph, denoted
by $B_{n}$. Observe that $B_{2}$ is the $2$-vertex complete graph and $B_{3}$
is the $6$-vertex cycle. Generally, $B_{n}$ is an $n!$-vertex bipartite,
vertex transitive and regular graph of degree $n-1$.

The generalized connectivity has been studied extensively, see the recent book
[17]. There has been lots of results on the generalized $3$-connectivity for
various classes of graphs, see, e.g., [1, 7, 14, 15, 16, 24, 26]. For example,
Li et al. [15] showed that $\kappa_{3}(S_{n})=\kappa_{3}(B_{n})=n-2$ for
$n\geq 3$. The generalized $4$-connectivity has also received attention, see
[10, 18, 27, 25]. Li et al. [10] showed that $\kappa_{4}(S_{n})=n-2$ for
$n\geq 3$. More closely related results may be found, see, e.g., [5, 11, 12].

In this paper, we will determine the generalized $4$-connectivity of the
bubble-sort graph $B_{n}$. We show the following result.

######  Theorem 1.1.

For $n\geq 3$, $\kappa_{4}(B_{n})=n-2$.

##  2 Preliminaries

For $v\in V(G)$, denote by $N_{G}(v)$ the set of neighbors of $v$ in $G$,
$\delta_{G}(v)=|N_{G}(v)|$ and $N_{G}[v]=N_{G}(v)\cup\\{v\\}$. For a subset
$S\subseteq V(G)$, denote by $G[S]$ the subgraph of $G$ induced by $S$.

For $x,y\in V(G)$, a path joining $x$ and $y$ in $G$ is called an
$(x,y)$-path. For $X,Y\subset V(G)$, an $(X,Y)$-path is a path joining $x$ and
$y$ in $G$ for some $x\in X$ and some $y\in Y$, and any other vertex of the
path (if any exists) are not in $X\cup Y$. We write $(x,Y)$-path instead of
$(\\{x\\},Y)$-path.

######  Lemma 2.1.

[2] Let $G$ be a $k$-connected graph, and let $X,Y\subset V(G)$ with
$|X|,|Y|\geq k$. Then there are $k$ pairwise vertex disjoint $(X,Y)$-paths in
$G$.

######  Lemma 2.2.

[2] Let $G$ be a $k$-connected graph, and let $x\in V(G)$ and $Y\subset
V(G)\setminus\\{x\\}$ with $|Y|\geq k$. Then there are $k$ internally vertex
disjoint $(x,Y)$-paths such that $x$ is the only common terminal vertex.

The following lemma tells us an upper bound on $\kappa_{k}(G)$ for a graph
$G$.

######  Lemma 2.3.

[13] Let $G$ be a connected graph with minimum degree $\delta$. Then
$\kappa_{k}(G)\leq\delta$ for $3\leq k\leq|V(G)|$. Furthermore, if there exist
two adjacent vertices of degree $\delta$ in $G$, then
$\kappa_{k}(G)\leq\delta-1$.

######  Lemma 2.4.

[6] $\kappa(B_{n})=n-1$ for $n\geq 2$.

######  Lemma 2.5.

[15] $\kappa_{3}(B_{n})=n-2$ for $n\geq 3$.

As we consider the bubble-sort graph $B_{n}$, we may suppose without loss of
generality that $\mathcal{T}=\\{[i,i+1]:i\in[n-1]\\}$. Then
$E(G_{\mathcal{T}})=\\{i(i+1):i\in[n-1]\\}$.

For $i\in[n]$, let $\mbox{Sym}_{i}(n)$ denote the set of all permutations of
$[n]\setminus\\{i\\}$. For $\sigma=(p_{1},\dots,p_{n-1})\in\mbox{Sym}_{i}(n)$,
we have $\sigma(j)=p_{j}$ for $j<i$ and $\sigma(j)=p_{j-1}$ for $j>i$. Let

$V_{i}=\\{(p_{1},\dots,p_{n-1},i):(p_{1},\dots,p_{n-1})\in\mbox{Sym}_{i}(n)\\}$

and $B_{n-1}^{i}=B_{n}[V_{i}]$ for $i\in[n]$. Then $V(B_{n})$ can be
partitioned into $V_{1},\dots,V_{n}$ and $B_{n-1}^{i}\cong B_{n-1}$ for
$i\in[n]$. We call $B_{n-1}^{1},\dots,B_{n-1}^{n}$ the main parts of $B_{n}$.

If $u=(p_{1},\dots,p_{n-1},k)\in V_{k}$, then $u$ is in the main part
$B_{n-1}^{k}$. Let $u_{i}=u[i,i+1]$ for $i\in[n-1]$. Then
$N_{B_{n}}(u)=\\{u_{i}:i\in[n-1]\\}$ with $u_{1},\dots,u_{n-2}\in V_{k}$ and
$u_{n-1}\in V_{p_{n-1}}$. Note that $u_{n-1}$ is the unique neighbor of $u$
outside $B_{n-1}^{k}$, which we call the out-neighbor of $u$, written as
$u^{\prime}$ throughout this paper. The other $n-2$ neighbors of $u$ are
called the in-neighbors of $u$. The out-neighbor of $u_{i}$ is
$u_{i}^{\prime}=u_{i}[n-1,n]$ for $i\in[n-1]$. Then $u_{i}^{\prime}\in
V_{p_{n-1}}$ for $i\in[n-3]$ and $u_{n-2}^{\prime}\in V_{p_{n-2}}$. Note that
$u_{n-1}^{\prime}=u$.

It can be verified that any two distinct vertices have different out-neighbors
and $|((\cup_{u\in V_{i}}N_{B_{n}}(u))\setminus V_{i})\cap V_{j}|=(n-2)!$ for
$i,j\in[n]$ with $i\neq j$, see [6].

For $\\{i,j\\}\subset[n]$ with $n\geq 3$, it is shown in [15] that

$\kappa(B_{n}[V_{i}\cup V_{j}])=n-2.$

By the proof in [15], there are $n-2$ internally vertex disjoint paths between
any two vertices in $B_{n}[V_{i}\cup V_{j}]$. So we have the following result.

######  Lemma 2.6.

Let $B_{n-1}^{1},\dots,B_{n-1}^{n}$ be the main parts of $B_{n}$, where $n\geq
3$. For any $\emptyset\neq I\subset[n]$,

$\kappa(B_{n}[\cup_{i\in I}V_{i}])=n-2.$

Suppose that $T_{1},\dots,T_{s}$ are $s\geq 2$ trees such that $|V(T_{i})\cap
V(T_{j})|=0,1$ for any $i,j$ with $1\leq i<j\leq s$. If the graph with vertex
set $\cup_{i=1}^{s}V(T_{i})$ and edge set $\cup_{i=1}^{s}E(T_{i})$ connected,
then it is a tree, denoted by $T_{1}+\dots+T_{s}$. It is possible that $T_{i}$
is a path.

Fix $i\in[n]$. For $j\in[n]\setminus\\{i\\}$, let

$V_{j}^{i}=\\{(p_{1},\dots,p_{n-2},j,i):(p_{1},\dots,p_{n-2})\in\mbox{Sym}_{i,j}(n)\\},$

where $\mbox{Sym}_{i,j}(n)$ denotes the set of permutations of
$[n]\setminus\\{i,j\\}$. Denote the induced subgraph $B_{n}[V_{j}^{i}]$ by
$B_{n-2}^{(i,j)}$.

##  3 Proof of Theorem 1.1

###### Proof of Theorem 1.1.

By Lemma 2.3 and the fact that $B_{n}$ is $(n-1)$-regular, we have
$\kappa_{4}(B_{n})\leq n-2$. So it suffices to show that
$\kappa_{4}(B_{n})\geq n-2$. Let $S$ be an arbitrary subset of $V(B_{n})$ with
$|S|=4$, say $S=\\{x,y,z,w\\}$. Then, it suffices to show that

$\mbox{there are $n-2$ internally edge disjoint trees connecting $S$ in
$B_{n}$}.$

We prove this statement by induction on $n$.

If $n=3$, it is evident that there exists a tree containing vertices in $S$,
so the statement is true. Suppose that $n\geq 4$ and the statement is true for
$B_{n-1}$.

Recall that $B_{n-1}^{1},\dots,B_{n-1}^{n}$ are the main parts of $B_{n}$. We
consider the following five cases separately in subsections 3.1–3.5:

  * •

Case 1. The four vertices of $S$ lie in a main part of $B_{n}$;

  * •

Case 2. Two vertices of $S$ lie in a main part and the other two vertices in
$S$ lie in another main part of $B_{n}$;

  * •

Case 3. The four vertices of $S$ lie in three different main parts of $B_{n}$;

  * •

Case 4. The four vertices of $S$ lie in four different main parts of $B_{n}$;

  * •

Case 5. Three vertices of $S$ lie in a main part and the remaining one lies in
another main part of $B_{n}$.

###  3.1 Case 1

Assume that $x,y,z,w$ are in $B_{n-1}^{1}$. Note that $B_{n-1}^{1}\cong
B_{n-1}$. By the induction hypothesis, there are $n-3$ internally edge
disjoint trees $T_{1},\dots,T_{n-3}$ connecting $S$ in the main part
$B_{n-1}^{1}$ of $B_{n}$. By Lemma 2.6, $B_{n}[V(B_{n})\setminus V_{1}]$ is
connected, so there is a spanning tree $T$ in $B_{n}[V(B_{n})\setminus
V_{1}]$. Note that $x^{\prime},y^{\prime},z^{\prime},w^{\prime}$ are distinct
four vertices in $B_{n}[V(B_{n})\setminus V_{1}]$. So
$T_{n-2}=T+xx^{\prime}+yy^{\prime}+zz^{\prime}+ww^{\prime}$ is a tree
containing vertices in $S$ and $V(T_{n-2})\cap V_{1}=S$. It thus follows that
$T_{1},\dots,T_{n-2}$ are $n-2$ internally edge disjoint trees connecting $S$
in $B_{n}$.

###  3.2 Case 2

Assume that $x,y\in V(B_{n-1}^{1})$ and $z,w\in V(B_{n-1}^{2})$. By Lemma 2.4,
$\kappa(B_{n-1}^{2})=\kappa(B_{n-1})=n-2$, so there are $n-2$ internally
vertex disjoint $(z,w)$-paths $Q_{1},\dots,Q_{n-2}$ in $B_{n-1}^{2}$. Since
$|N_{B_{n-1}^{2}}(z)|=n-2$ and $Q_{1},\dots,Q_{n-2}$ are internally vertex
disjoint $(z,w)$-paths, we may assume that $V(Q_{i})\cap
N_{B_{n-1}^{2}}(z)=\\{z_{i}\\}$ for $i\in[n-2]$.

Case 2.1. One of $x^{\prime}$ and $y^{\prime}$, say $x^{\prime}$, is not in
$B_{n-1}^{2}$, and one of $z^{\prime}$ and $w^{\prime}$, say $z^{\prime}$, is
not in $B_{n-1}^{1}$.

By Lemma 2.4, there are $n-2$ internally vertex disjoint $(x,y)$-paths
$L_{1}$, $\dots,L_{n-2}$, and we may assume that $V(L_{i})\cap
N_{B_{n-1}^{1}}(x)=\\{x_{i}\\}$ for $i\in[n-2]$.

Note that there is exactly one in-neighbor of $x$, say $x_{n-2}$, whose out-
neighbor and $x^{\prime}$ lie in different main parts, and there is exactly
one in-neighbor of $z$, say $z_{n-2}$, whose out-neighbor and $z^{\prime}$ lie
in different main parts. Let

$X=\\{x_{i}^{\prime}:i\in[n-3]\\}\cup\\{x^{\prime}\\}\mbox{ and
}Z=\\{z_{i}^{\prime}:i\in[n-3]\\}\cup\\{z^{\prime}\\}.$

It is evident that $|X|=|Z|=n-2$. By Lemmas 2.1 and 2.6, there are $n-2$
disjoint $(X,Z)$-paths $R_{1},\dots,R_{n-2}$ in $B_{n}[\cup_{i=3}^{n}V_{i}]$.
Suppose that $x^{\prime}\in V(R_{n-2})$, $x_{i}^{\prime}\in V(R_{i})$ for
$i\in[n-3]$, $z^{\prime}\in V(R_{s})$ for some $s\in[n-2]$, $z_{i}^{\prime}\in
V(R_{i})$ for $i\in[n-3]\setminus\\{s\\}$ and $z_{s}^{\prime}\in V(R_{n-2})$.
If $s=n-2$, let

$T_{i}=L_{i}+x_{i}x_{i}^{\prime}+R_{i}+z_{i}^{\prime}z_{i}+Q_{i}\mbox{ for
}i\in[n-3]$

and

$T_{n-2}=L_{n-2}+xx^{\prime}+R_{n-2}+z^{\prime}z+Q_{n-2}.$

Otherwise, let

$T_{i}=L_{i}+x_{i}x_{i}^{\prime}+R_{i}+z_{i}^{\prime}z_{i}+Q_{i}\mbox{ for
}i\in[n-3]\setminus\\{s\\},$
$T_{s}=L_{s}+x_{s}x_{s}^{\prime}+R_{s}+z^{\prime}z+Q_{n-2}$

and

$T_{n-2}=L_{n-2}+xx^{\prime}+R_{n-2}+z_{s}^{\prime}z_{s}+Q_{s}.$

Then it is easy to see that $T_{1},\dots,T_{n-2}$ are $n-2$ internally edge
disjoint trees connecting $S$.

Case 2.2. $x^{\prime}$ and $y^{\prime}$ are both in $B_{n-1}^{2}$ and one of
$z^{\prime}$ and $w^{\prime}$ is not in $B_{n-1}^{1}$, or $z^{\prime}$ and
$w^{\prime}$ are both in $B_{n-1}^{1}$ and one of $x^{\prime}$ and
$y^{\prime}$ is not in $B_{n-1}^{2}$.

Assume that $x^{\prime}$ and $y^{\prime}$ are both in $B_{n-1}^{2}$ and one of
$z^{\prime}$ and $w^{\prime}$, say $z^{\prime}$, is not in $B_{n-1}^{1}$.

Suppose that $n=4$. Then $x$ and $y$ are adjacent. If $w^{\prime}\in V_{1}$,
then $w^{\prime}=x$ or $w^{\prime}=y$, say $w^{\prime}=y$. Let $x_{1}=x[2,3]$
and $y_{1}=y[2,3]$. Then $x_{1}^{\prime},y_{1}^{\prime},z^{\prime}\in
V_{3}\cup V_{4}$. As $B_{4}[V_{3}\cup V_{4}]$ is connected, there is a tree
$T_{1}$ containing $x_{1}^{\prime},y_{1}^{\prime},z^{\prime}$. Let

$T_{1}^{*}=xx_{1}+x_{1}x_{1}^{\prime}+yy_{1}+y_{1}y_{1}^{\prime}+T_{1}+z^{\prime}z+Q_{1}$

and

$T_{2}=xy+yw+Q_{2}.$

Then $T_{1}^{*}$ and $T_{2}$ are two internally edge disjoint trees connecting
$S$. Otherwise, $w^{\prime}\notin V_{1}$. Since $x^{\prime},y^{\prime}\in
V_{2}$, there is a tree $F_{1}$ in $B_{3}^{2}$ containing
$x^{\prime},y^{\prime},z,w$. Similarly, there is a tree $F_{2}$ in
$B_{4}[V_{1}\cup V_{3}\cup V_{4}]$ containing
$\\{x,y,z^{\prime},w^{\prime}\\}$. Then
$F_{1}^{*}=F_{1}+x^{\prime}x+y^{\prime}y$ and
$F_{2}^{*}=F_{2}+w^{\prime}w+z^{\prime}z$ are two internally edge disjoint
trees connecting $S$.

Suppose that $n\geq 5$. For $j=2,\dots,n$, let

$V_{j}^{1}=\\{(p_{1},\dots,p_{n-2},j,1):(p_{1},\dots,p_{n-2})\in\mbox{Sym}_{1,j}(n)\\},$

where $\mbox{Sym}_{1,j}(n)$ denotes the set of permutations of
$[n]\setminus\\{1,j\\}$. Denote the induced subgraph $B_{n}[V_{j}^{1}]$ by
$B_{n-2}^{(j)}$.

Since $B_{n-2}^{(1,j)}\cong B_{n-2}$ and $B_{n-1}^{1}\cong B_{n-1}$, we view
$B_{n-2}^{(1,2)},\dots,B_{n-2}^{(1,n)}$ as the main parts of $B_{n-1}^{1}$.
Then $x$ and $y$ are in $B_{n-2}^{(1,2)}$. By Lemma 2.4,
$\kappa(B_{n-2}^{(1,2)})=n-3$, so there exist $n-3$ internally disjoint
$(x,y)$-paths $L_{1},L_{2},\dots,L_{n-3}$ in $B_{n-2}^{(1,2)}$. Note that
there are $n-3$ vertices adjacent to $x$ in $B_{n-2}^{(1,2)}$. Then each
$L_{i}$ contains exactly one vertex in $N_{B_{n-2}^{(1,2)}}(x)$, which we
denote by $x_{i}$, where $i\in[n-3]$.

Assume that $z_{n-2}$ is the vertex whose out-neighbor is not in the same main
part as $z^{\prime}$.

Let $x=(p_{1},\dots,p_{n-2},2,1)$ and $y=(r_{1},\dots,r_{n-2},2,1)$. Let
$x_{n-2}=x[n-2,n-1]$, $x_{n-2,1}=x_{n-2}[n-3,n-2]$,
$x_{n-2,2}=x_{n-2,1}[n-4,n-3]$, $x_{n-2,3}=x_{n-2,2}[n-3,n-2]$ and
$\widehat{x}_{n-2}=x_{n-2,3}[n-2,n-1]$. That is,

$x_{n-2}=(p_{1},\dots,p_{n-4},p_{n-3},2,p_{n-2},1),$
$x_{n-2,1}=(p_{1},\dots,p_{n-4},2,p_{n-3},p_{n-2},1),$
$x_{n-2,2}=(p_{1},\dots,2,p_{n-4},p_{n-3},p_{n-2},1),$
$x_{n-2,3}=(p_{1},\dots,2,p_{n-3},p_{n-4},p_{n-2},1)$

and

$\widehat{x}_{n-2}=(p_{1},\dots,2,p_{n-3},p_{n-2},p_{n-4},1).$

Let

$P_{x}=xx_{n-2}x_{n-2,1}x_{n-2,2}x_{n-2,3}\widehat{x}_{n-2}.$

There are three probabilities: (i) If
$\\{r_{n-3},r_{n-2}\\}=\\{p_{n-3},p_{n-2}\\}$, then set $y_{n-2}=y[n-2,n-1]$,
$y_{n-2,1}=y_{n-2}[n-3,n-2]$, $y_{n-2,2}=y_{n-2,1}[n-4,n-3]$,
$y_{n-2,3}=y_{n-2,2}[n-3,n-2]$, $\widehat{y}_{n-2}=y_{n-2,3}[n-2,n-1]$ and
$P_{y}=yy_{n-2}y_{n-2,1}y_{n-2,2}y_{n-2,3}\widehat{y}_{n-2}$. (ii) If
$r_{n-2}\in\\{p_{n-3},p_{n-2}\\}$ and $r_{n-3}\notin\\{p_{n-3},p_{n-2}\\}$,
then set $y_{n-2}=y[n-2,n-1]$, $y_{n-2,1}=y_{n-2}[n-3,n-2]$,
$\widehat{y}_{n-2}=y_{n-2,1}[n-2,n-1]$ and
$P_{y}=yy_{n-2}y_{n-2,1}\widehat{y}_{n-2}$. (iii) Otherwise, set
$\widehat{y}_{n-2}=y[n-2,n-1]$ and $P_{y}=y\widehat{y}_{n-2}$. As $x\neq y$,
we have $V(P_{x})\cap V(P_{y})=\emptyset$. Correspondingly to (i)–(iii), we
have by Lemma 2.6 that each of $B_{n-1}^{1}[V_{p_{n-4}}^{1}\cup
V_{r_{n-4}}^{1}]$, $B_{n-1}^{1}[V_{p_{n-4}}^{1}\cup V_{r_{n-3}}^{1}]$, or
$B_{n-1}^{1}[V_{p_{n-4}}^{1}\cup V_{r_{n-2}}^{1}]$ is connected, so there is a
$(\widehat{x}_{n-2},\widehat{y}_{n-2})$-path $P_{xy}$ in one of them. Let

$L_{n-2}=P_{x}+P_{xy}+P_{y}.$

Since $V(L_{n-2})\cap V_{2}^{1}=\\{x,y\\}$, we have $n-2$ internally disjoint
$(x,y)$-paths in $B_{n-1}^{1}$.

Case 2.2.1. $x,y$ are not adjacent.

Let $\widehat{x}_{i}=x_{i}[n-2,n-1]$ for $i\in[n-3]$. Then
$|\\{\widehat{x}_{i}^{\prime}:i\in[n-3]\\}\cap V_{p_{n-2}}^{1}|=n-4$ and
$|\\{\widehat{x}_{i}^{\prime}:i\in[n-3]\\}\cap V_{p_{n-3}}^{1}|=1$. Since
$x_{i}\in N_{B_{n}}(x)$ for $1\leq i\leq n-3$, we have
$\widehat{x}_{i}\neq\widehat{x}_{j}$ if $i\neq j$. Note that $xy\notin
E(B_{n})$. By comparing the position of ‘$2$’ in the permutation corresponding
to the vertices on $P_{x}$ and in $\widehat{x}_{i}$ for $i\in[n-3]$, we have
$V(P_{x})\cap\\{\widehat{x}_{i}:i\in[n-3]\\}=\emptyset$. Similarly,
$V(P_{y})\cap\\{\widehat{x}_{i}:i\in[n-3]\\}=\emptyset$.

Let $X=\\{\widehat{x}_{i}^{\prime}:i\in[n-2]\\}$, and
$Z=\\{z_{i}^{\prime}:i\in[n-3]\\}\cup\\{z^{\prime}\\}$. Note that
$X\subseteq\cup_{i=3}^{n}V_{i}$ and $Z\subseteq\cup_{i=3}^{n}V_{i}$. By Lemmas
2.1 and 2.6, there are $n-2$ disjoint $(X,Z)$-paths $R_{1},\dots,R_{n-2}$ in
$B_{n}[\cup_{i=3}^{n}V_{i}]$. Assume that $z^{\prime}\in V(R_{n-2})$,
$z_{i}^{\prime}\in V(R_{i})$ for $i\in[n-3]$, $\widehat{x}_{n-2}^{\prime}\in
V(R_{s})$ for some $s\in[n-2]$, $\widehat{x}_{i}^{\prime}\in V(R_{i})$ for
$i\in[n-3]\setminus\\{s\\}$ and $\widehat{x}_{s}^{\prime}\in V(R_{n-2})$. If
$s=n-2$, let

$T_{i}=L_{i}+x_{i}\widehat{x}_{i}+\widehat{x}_{i}\widehat{x}_{i}^{\prime}+R_{i}+z_{i}^{\prime}z_{i}+Q_{i}\mbox{
for }i\in[n-3]$

and

$T_{n-2}=L_{n-2}+\widehat{x}_{n-2}\widehat{x}_{n-2}^{\prime}+R_{n-2}+z^{\prime}z+Q_{n-2}.$

Otherwise, let

$T_{i}=L_{i}+x_{i}\widehat{x}_{i}+\widehat{x}_{i}\widehat{x}_{i}^{\prime}+R_{i}+z_{i}^{\prime}z_{i}+Q_{i}\mbox{
for }i\in[n-3]\setminus\\{s\\},$
$T_{s}=L_{n-2}+\widehat{x}_{n-2}\widehat{x}^{\prime}_{n-2}+R_{s}+z_{s}^{\prime}z_{s}+Q_{s}$

and

$T_{n-2}=L_{s}+x_{s}\widehat{x}_{s}+\widehat{x}_{s}\widehat{x}_{s}^{\prime}+R_{n-2}+z^{\prime}z+Q_{n-2}.$

Then $T_{1},\dots,T_{n-2}$ are $n-2$ internally edge disjoint trees connecting
$S$ in $B_{n}$.

Case 2.2.2. $x,y$ are adjacent.

Assume that $L_{1}=xy$. Let $\widehat{x}_{i}=x_{i}[n-2,n-1]$ for
$i=2,\dots,n-3$. By similar argument as in Case 2.2.1, we have
$V(P_{x})\cap\\{\widehat{x}_{i}:i=2,\dots,n-3\\}=\emptyset$ and
$V(P_{y})\cap\\{\widehat{x}_{i}:i=2,\dots,n-3\\}=\emptyset$.

Suppose that
$N_{B_{n-1}^{2}}[x^{\prime}]\cap(\cup_{i=1}^{n-2}V(Q_{i}))=\emptyset$. Let
$\widehat{x}_{1}=x^{\prime}[n-2,n-1]$. Let $X$ and $Z$ be defined the same as
that in Case 2.2.1. Then there are $n-2$ internally vertex disjoint
$(X,Z)$-paths $R_{i}$ in $B_{n}[\cup_{i=3}^{n}V_{i}]$ for $i\in[n-2]$. If
$s\neq 1$, let $T_{i}$ be defined as in Case 2.2.1 for $i=2,\dots,n-2$, and
let

$T_{1}=xy+xx^{\prime}+x^{\prime}\widehat{x}_{1}+\widehat{x}_{1}\widehat{x}_{1}^{\prime}+R_{1}+z_{1}^{\prime}z_{1}+Q_{1}.$

Otherwise, let $T_{i}$ be defined as in Case 2.2.1 for $i=2,\dots,n-3$,

$T_{1}=L_{n-2}+\widehat{x}_{n-2}^{\prime}\widehat{x}_{n-2}^{\prime}+R_{1}+z_{1}^{\prime}z_{1}+Q_{1}$

and

$T_{n-2}=xy+xx^{\prime}+x^{\prime}\widehat{x}_{1}+\widehat{x}_{1}\widehat{x}_{1}^{\prime}+R_{n-2}+z^{\prime}z+Q_{n-2}.$

In either case, there are $n-2$ internally edge disjoint trees connecting $S$.

Otherwise, assume that $\widehat{x}_{1}\in N_{B_{n-1}^{2}}[x^{\prime}]\cap
V(Q_{\ell})$ for some $\ell\in[n-2]$. So

$T_{1}=\begin{cases}Q_{\ell}+x^{\prime}\widehat{x}_{1}+xx^{\prime}+xy&\mbox{if
$\widehat{x}_{1}\neq x^{\prime}$}\\\
Q_{\ell}+xx^{\prime}+xy&\mbox{otherwise}\end{cases}$

is a tree containing vertices in $S$. Let
$X=\\{\widehat{x}_{i}^{\prime}:i=2,\dots,n-2\\}$,
$Z=\\{z_{i}^{\prime}:i\in[n-3]\\}$ if $\ell=n-2$ and
$Z=\\{z_{i}^{\prime}:i\in[n-3]\setminus\\{\ell\\}\\}\cup\\{z^{\prime}\\}$
otherwise. By Lemmas 2.1 and 2.6, there are $n-3$ internally vertex disjoint
$(X,Z)$-paths $R_{1},\dots,R_{n-3}$ in $B_{n}[\cup_{i=3}^{n}V_{i}]$. Assume
that $\widehat{x}_{i+1}^{\prime},z_{i}^{\prime}\in V(R_{i})$ for $i\in[n-3]$
if $\ell=n-2$. Let

$T_{i}=L_{i}+x_{i}\widehat{x}_{i}+\widehat{x}_{i}\widehat{x}_{i}^{\prime}+R_{i-1}+z_{i-1}^{\prime}z_{i-1}+Q_{i-1}\mbox{
for }i=2,\dots,n-3,$

and

$T_{n-2}=L_{n-2}+\widehat{x}_{n-2}\widehat{x}_{n-2}^{\prime}+R_{n-3}+z_{n-3}^{\prime}z_{n-3}+Q_{n-3}.$

Otherwise, we may suppose without loss of generality that $\ell=1$. Assume
that $z^{\prime}\in V(R_{n-3})$, $z_{i}^{\prime}\in V(R_{i-1})$ for
$i=2,\dots,n-3$, $\widehat{x}_{s}^{\prime}\in V(R_{n-3})$,
$\widehat{x}_{n-2}^{\prime}\in V(R_{s-1})$ and $\widehat{x}_{i}^{\prime}\in
V(R_{i-1})$ for $i\in[n-3]\setminus\\{1,s\\}$. If $s=n-2$, let

$T_{i}=L_{i}+x_{i}\widehat{x}_{i}+\widehat{x}_{i}\widehat{x}_{i}^{\prime}+R_{i-1}+z_{i}^{\prime}z_{i}+Q_{i}\mbox{
for }i=2,\dots,n-3,$

and

$T_{n-2}=L_{n-2}+\widehat{x}_{n-2}\widehat{x}_{n-2}^{\prime}+R_{n-3}+z^{\prime}z+Q_{n-2}.$

Otherwise, let

$T_{i}=L_{i}+x_{i}\widehat{x}_{i}+\widehat{x}_{i}\widehat{x}_{i}^{\prime}+R_{i-1}+z_{i}^{\prime}z_{i}+Q_{i}\mbox{
for }i\in[n-3]\setminus\\{1,s\\},$
$T_{s}=L_{n-2}+\widehat{x}_{n-2}\widehat{x}_{n-2}^{\prime}+R_{s-1}+z_{s}^{\prime}z_{s}+Q_{s}$

and

$T_{n-2}=L_{s}+x_{s}\widehat{x}_{s}+\widehat{x}_{s}\widehat{x}_{s}^{\prime}+R_{n-3}+z^{\prime}z+Q_{n-2}.$

Then $T_{1},\dots,T_{n-2}$ are $n-2$ internally edge disjoint trees connecting
$S$ in $B_{n}$.

Case 2.3. Both $x^{\prime},y^{\prime}$ are in $B_{n-1}^{2}$ and
$z^{\prime},w^{\prime}$ are in $B_{n-1}^{1}$.

If $n=4$, then $B_{4}[S]$ is a cycle of length four with edges $xy,zw,xz,yw$.
Let $x_{1}=x[2,3]$, $y_{1}=y[2,3]$ and $z_{1}=z[2,3]$. Then
$x_{1}^{\prime},y_{1}^{\prime},z_{1}^{\prime}\in V_{3}\cup V_{4}$. So there is
a tree $T_{1}^{\prime}$ connecting
$x_{1}^{\prime},y_{1}^{\prime},z_{1}^{\prime}$. Then

$T_{1}=xx_{1}+x_{1}x_{1}^{\prime}+yy_{1}+y_{1}y_{1}^{\prime}+T_{1}^{\prime}+z_{1}^{\prime}z_{1}+z_{1}z+zw$

and

$T_{2}=zx+xy+yw$

are two internally edge disjoint trees connecting $S$.

For $n\geq 5$, by the same way as in Case 2.2, we may construct $n-2$
internally vertex disjoint $(x,y)$-paths in $B_{n-1}^{1}$, and $n-2$
internally vertex disjoint $(z,w)$-paths in $B_{n-1}^{2}$, and so we may
obtain $n-2$ internally edge disjoint trees connecting $S$.

###  3.3 Case 3

Assume that $x,y\in V_{1}$, $z\in V_{2}$ and $w\in V_{3}$. Let

$x=(p_{1},\dots,p_{n-1},1)\mbox{ and }y=(r_{1},\dots,r_{n-1},1).$

Then $x^{\prime}\in V_{p_{n-1}}$ and $y^{\prime}\in V_{r_{n-1}}$. By
considering whether the out-neighbors of $x$ and $y$ are in the same main part
of $B_{n}$, we discuss the following two cases.

Case 3.1. $x^{\prime}$ and $y^{\prime}$ are in the different main parts, i.e.,
$p_{n-1}\neq r_{n-1}$.

Since $\kappa(B_{n-1}^{1})=n-2$, there are $n-2$ internally vertex disjoint
$(x,y)$-paths $L_{1},\dots,L_{n-2}$ in $B_{n-1}^{1}$. Let
$\widehat{x}=x[n-2,n-1]$ and $\widehat{y}=y[n-2,n-1]$. Note that each $L_{i}$
contains exactly one vertex in $N_{B_{n-1}^{1}}(x)$ and exactly one vertex in
$N_{B_{n-1}^{1}}(y)$ for $i\in[n-2]$. Assume that $\widehat{x}\in V(L_{n-2})$
and $\widehat{y}\in V(L_{s})$ for some $s\in[n-2]$. Assume that $V(L_{i})\cap
N_{B_{n}}(x)=\\{x_{i}\\}$ for $i\in[n-3]$ and $V(L_{i})\cap
N_{B_{n}}(y)=\\{y_{i}\\}$ for $i\in[n-2]\setminus\\{s\\}$. Let
$X=\\{x_{i}^{\prime}:i\in[n-3]\\}\cup\\{x^{\prime}\\}$ and
$Y=\\{y_{i}^{\prime}:i\in[n-2]\setminus\\{s\\}\\}\cup\\{y^{\prime}\\}$.

Assume that $p_{n-1}\neq 3$ and $r_{n-1}\neq 2$, otherwise, we change the role
of $x$ and $y$ in the following proof. By Lemmas 2.2 and 2.6, there are $n-2$
internally vertex disjoint $(z,X)$-paths $Q_{1},\dots,Q_{n-2}$ in
$B_{n}[V_{2}\cup V_{p_{n-1}}]$ and $n-2$ internally vertex disjoint
$(w,Y)$-paths $R_{1},\dots,R_{n-2}$ in $B_{n}[V_{3}\cup V_{r_{n-1}}]$. Assume
that $x^{\prime}\in V(Q_{n-2})$, $x_{i}^{\prime}\in V(Q_{i})$ for $i\in[n-3]$,
and $y^{\prime}\in V(R_{s})$ and $y_{i}^{\prime}\in V(R_{i})$ for
$i\in[n-2]\setminus\\{s\\}$. If $s=n-2$, let

$T_{i}=Q_{i}+x_{i}^{\prime}x_{i}+L_{i}+y_{i}y_{i}^{\prime}+R_{i}\mbox{ for
}i\in[n-3],$

and

$T_{n-2}=Q_{n-2}+x^{\prime}x+L_{n-2}+yy^{\prime}+R_{n-2}.$

Otherwise, let

$T_{i}=Q_{i}+x_{i}^{\prime}x_{i}+L_{i}+y_{i}y_{i}^{\prime}+R_{i}\mbox{ for
}i\in[n-3]\setminus\\{s\\},$
$T_{s}=Q_{s}+x_{s}^{\prime}x_{s}+L_{s}+y^{\prime}y+R_{s},$

and

$T_{n-2}=Q_{n-2}+xx^{\prime}+L_{n-2}+y_{n-2}y_{n-2}^{\prime}+R_{n-2}.$

Then $T_{1},\dots,T_{n-2}$ are $n-2$ internally disjoint edge disjoint trees
connecting $S$.

Case 3.2. $x^{\prime}$ and $y^{\prime}$ are in the same main part, i.e.,
$p_{n-1}=r_{n-1}$.

Assume that $p_{n-1}\neq 3$. By similar argument as in Case 2.2, we obtain
$n-2$ internally vertex disjoint $(x,y)$-paths $L_{1},\dots,L_{n-2}$. Let
$x_{i},\widehat{x}_{i}$ for $i\in[n-2]$ and $X$ be defined the same way as in
Case 2.2. Suppose that $V(L_{i})\cap N_{B_{n}}(y)=\\{y_{i}\\}$ for
$i\in[n-3]$. Let $Y=\\{y_{i}:i\in[n-3]\\}\cup\\{y^{\prime}\\}$. By Lemmas 2.2
and 2.6, there are $n-2$ internally disjoint $(w,X)$-paths
$Q_{1},\dots,Q_{n-2}$ in $B_{n}[V(B_{n})\setminus(V_{1}\cup V_{2}\cup
V_{p_{n-1}})]$ and there are $n-2$ internally disjoint $(z,Y)$-paths
$R_{1},\dots,R_{n-2}$ in $B_{n}[V_{2}\cup V_{p_{n-1}}]$. Assume that
$\widehat{x}_{i}^{\prime}\in V(Q_{i})$ for $i\in[n-2]$, $y_{i}^{\prime}\in
V(R_{i})$ for $i\in[n-3]$ and $y^{\prime}\in V(R_{n-2})$. Let

$T_{i}=Q_{i}+\widehat{x}_{i}^{\prime}\widehat{x}_{i}+x_{i}\widehat{x}_{i}+L_{i}+y_{i}y_{i}^{\prime}+R_{i}\mbox{
for }i\in[n-3]$

and

$T_{n-2}=Q_{n-2}+\widehat{x}_{n-2}^{\prime}\widehat{x}_{n-2}+L_{n-2}+yy^{\prime}+R_{n-2}.$

Then there are $n-2$ internally edge disjoint trees $T_{1},\dots,T_{n-2}$
connecting $S$.

###  3.4 Case 4

Assume that $x\in V_{1}$, $y\in V_{2}$, $z\in V_{3}$ and $w\in V_{4}$. Suppose
first that there are at least two vertices in $S$ whose out-neighbors lie in
$\cup_{i=5}^{n}V_{i}$, say $x^{\prime},y^{\prime}\in\cup_{i=5}^{n}V_{i}$. By
Lemma and 2.6, there are $n-2$ internally vertex disjoint $(x,z)$-paths
$L_{1},\dots,L_{n-2}$ in $B_{n}[V_{1}\cup V_{3}]$ and $n-2$ internally vertex
disjoint $(y,w)$-paths $Q_{1},\dots,Q_{n-2}$ in $B_{n}[V_{2}\cup V_{4}]$. Then
by similar argument as in Case 2.1, we can obtain $n-2$ internally edge
disjoint trees connecting $S$.

Suppose next that there is at most one vertex in $S$ whose unique out-neighbor
lies in $\cup_{i=5}^{n}V_{i}$, that is, there are three vertices in $S$, say
$x,y,z$, with $x^{\prime},y^{\prime},z^{\prime}\in\cup_{i=1}^{4}V_{i}$.

Note that $x^{\prime}\not\in V_{1}$. Assume that $x^{\prime}\in V_{2}$ (if
$x^{\prime}\in V_{3}$ or $x^{\prime}\in V_{4}$, the argument is similar by
viewing $z$ or $w$ as $y$). We consider the following two cases.

Case 4.1. $y^{\prime}\in V_{1}$.

Recall that $z^{\prime}\in V_{1}\cup V_{2}\cup V_{4}$. Suppose first that
$z^{\prime}\in V_{4}$. By Lemma 2.6, there are $n-2$ internally vertex
disjoint $(x,z)$-paths $L_{1},\dots,L_{n-2}$ in $B_{n}[V_{1}\cup V_{3}]$. Let
$\widehat{x}=x[n-2,n-1]$ and $\widehat{z}=z[n-2,n-1]$. Note that each $L_{i}$
contains exactly one vertex in $N_{B_{n-1}^{1}}(x)$. Assume that
$\widehat{x}\in V(L_{n-2})$ and $V(L_{i})\cap N_{B_{n}}(x)=\\{x_{i}\\}$ for
$i\in[n-3]$. Similarly, we may assume that $\widehat{z}\in V(L_{s})$ for some
$s\in[n-2]$ and $V(L_{i})\cap N_{B_{n}}(z)=\\{z_{i}\\}$ for
$i\in[n-2]\setminus\\{s\\}$. Let
$X=\\{x_{i}^{\prime}:i\in[n-3]\\}\cup\\{x^{\prime}\\}$ and
$Z=\\{z_{i}^{\prime}:i\in[n-2]\setminus\\{s\\}\\}\cup\\{z^{\prime}\\}$. Then
$X\subseteq V_{2}$ with $|X|=n-2$ and $Z\subseteq V_{4}$ with $|Z|=n-2$. By
Lemmas 2.2 and 2.4, there are $n-2$ internally vertex disjoint $(y,X)$-paths
$Q_{1},\dots,Q_{n-2}$ in $B_{n-1}^{2}$ and there are $n-2$ internally vertex
disjoint $(w,Z)$-paths $R_{1},\dots,R_{n-2}$ in $B_{n-1}^{4}$. Assume that
$x_{i}^{\prime}\in V(Q_{i})$ for $i\in[n-3]$, $x^{\prime}\in V(Q_{n-2})$ and
$z^{\prime}\in V(R_{s})$, $z_{i}^{\prime}\in V(R_{i})$ for
$i\in[n-2]\setminus\\{s\\}$. If $s=n-2$, let

$T_{i}=L_{i}+x_{i}x_{i}^{\prime}+Q_{i}+z_{i}z_{i}^{\prime}+R_{i}\mbox{ for
}i\in[n-3]$

and

$T_{n-2}=L_{n-2}+xx^{\prime}+Q_{n-2}+zz^{\prime}+R_{n-2}.$

Otherwise, let

$T_{i}=L_{i}+x_{i}x_{i}^{\prime}+Q_{i}+z_{i}z_{i}^{\prime}+R_{i}\mbox{ for
}i\in[n-3]\setminus\\{s\\},$
$T_{s}=L_{s}+x_{s}x_{s}^{\prime}+Q_{s}+zz^{\prime}+R_{s}$

and

$T_{n-2}=L_{n-2}+xx^{\prime}+Q_{n-2}+z_{n-2}z_{n-2}^{\prime}+R_{n-2}.$

Then $T_{1},\dots,T_{n-2}$ are $n-2$ internally edge disjoint trees connecting
$S$. Next suppose $z^{\prime}\in V_{1}\cup V_{2}$, say $z^{\prime}\in V_{1}$.
There are $n-2$ internally vertex disjoint $(z,w)$-paths $L_{1},\dots,L_{n-2}$
by Lemma 2.6. Let $\widehat{z}=z[n-2,n-1]$. Note that each $L_{i}$ contains
exactly one vertex in $N_{B_{n-1}^{3}}(z)$. Assume that $\widehat{z}\in
V(L_{n-2})$ and $V(L_{i})\cap N_{B_{n}}(z)=\\{z_{i}\\}$ for $i\in[n-3]$. Let
$Z=\\{z_{i}^{\prime}:i\in[n-3]\\}\cup\\{z^{\prime}\\}$. Then $Z\subseteq
V_{1}$ with $|Z|=n-2$. By Lemma 2.4, there are $n-2$ internally vertex
disjoint $(x,Z)$-paths $Q_{1},\dots,Q_{n-2}$. Assume that $z_{i}^{\prime}\in
V(Q_{i})$ for $i\in[n-3]$ and $z^{\prime}\in V(Q_{n-2})$. Let
$\widehat{x}=x[n-2,n-1]$. Note that each $Q_{i}$ contains exactly one vertex
in $N_{B_{n-1}^{1}}(x)$. Assume that $\widehat{x}\in V(Q_{s})$ for some
$s\in[n-2]$ and $V(Q_{i})\cap N_{B_{n-1}^{1}}(x)=\\{y_{i}\\}$ for
$i\in[n-2]\setminus\\{s\\}$. Let
$X=\\{x_{i}^{\prime}:i\in[n-2]\setminus\\{s\\}\\}\cup\\{x^{\prime}\\}$. Then
$X\subseteq V(B_{n-1}^{2})$ with $|X|=n-2$. There are $n-2$ internally vertex
disjoint $(y,X)$-paths $R_{1},\dots,R_{n-2}$ by Lemma 2.4. Assume that
$x_{i}^{\prime}\in V(R_{i})$ for $i\in[n-2]\setminus\\{s\\}$ and
$x^{\prime}\in V(R_{s})$. If $s=n-2$, let

$T_{i}=L_{i}+z_{i}z_{i}^{\prime}+Q_{i}+x_{i}x_{i}^{\prime}+R_{i}\mbox{ for
}i\in[n-3]$

and

$T_{n-2}=L_{n-2}+zz^{\prime}+Q_{n-2}+xx^{\prime}+R_{n-2}.$

Otherwise, let

$T_{i}=L_{i}+z_{i}z_{i}^{\prime}+Q_{i}+x_{i}x_{i}^{\prime}+R_{i}\mbox{ for
}i\in[n-3]\setminus\\{s\\},$
$T_{s}=L_{s}+z_{s}z_{s}^{\prime}+Q_{s}+xx^{\prime}+R_{s}$

and

$T_{n-2}=L_{n-2}+zz^{\prime}+Q_{n-2}+x_{n-2}x_{n-2}^{\prime}+R_{n-2}.$

Then there are $n-2$ internally edge disjoint trees $T_{1},\dots,T_{n-2}$
connecting $S$.

Case 4.2. $y^{\prime}\notin V_{1}$.

Note that $y^{\prime}\in V_{3}\cup V_{4}$. Assume that $y^{\prime}\in V_{3}$.
By Lemma 2.6, there are $n-2$ internally vertex disjoint $(x,w)$-paths
$L_{1},\dots,L_{n-2}$ in $B_{n}[V_{1}\cup V_{4}]$. Let
$\widehat{x}=x[n-2,n-1]$. Note that each $L_{i}$ contains exactly one vertex
in $N_{B_{n-1}}(x)$. Assume that $\widehat{x}\in V(L_{n-2})$ and $V(L_{i})\cap
N_{B_{n-1}^{1}}(x)=\\{x_{i}\\}$ for $i\in[n-3]$. Let
$X=\\{x_{i}^{\prime}:i\in[n-3]\\}\cup\\{x^{\prime}\\}$. Then $X\subseteq
V_{2}$ with $|X|=n-2$. By Lemmas 2.2 and 2.4, there are $n-2$ internally
vertex disjoint $(y,X)$-paths $Q_{1},\dots,Q_{n-2}$ in $B_{n-1}^{2}$. Assume
that $x_{i}^{\prime}\in V(Q_{i})$ for $i\in[n-3]$ and $x^{\prime}\in
V(Q_{n-2})$. Let $\widehat{y}=y[n-2,n-1]$. Note that each $Q_{i}$ contains
exactly one vertex in $N_{B_{n-1}}(y)$. Assume that $\widehat{y}\in V(Q_{s})$
for some $s\in[n-2]$ and $V(Q_{i})\cap N_{B_{n-1}}(y)=\\{y_{i}\\}$ for
$i\in[n-2]\setminus\\{s\\}$. Let
$Y=\\{y_{i}^{\prime}:i\in[n-2]\setminus\\{s\\}\\}\cup\\{y^{\prime}\\}$. Then
$Y\subseteq V_{3}$ with $|Y|=n-2$. Since $\kappa(B_{n-1}^{3})=n-2$, there are
$n-2$ internally vertex disjoint $(z,Y)$-paths $R_{1},\dots,R_{n-2}$ in
$B_{n-1}^{3}$. Assume that $y_{i}^{\prime}\in V(R_{i})$ for
$i\in[n-2]\setminus\\{s\\}$ and $y^{\prime}\in V(R_{s})$. If $s=n-2$, let

$T_{i}=L_{i}+x_{i}x_{i}^{\prime}+Q_{i}+y_{i}y_{i}^{\prime}+R_{i}\mbox{ for
}i\in[n-3],$

and

$T_{n-2}=L_{n-2}+xx^{\prime}+Q_{n-2}+yy^{\prime}+R_{n-2}.$

Otherwise, let

$T_{i}=L_{i}+x_{i}x_{i}^{\prime}+Q_{i}+y_{i}y_{i}^{\prime}+R_{i}\mbox{ for
}i\in[n-3]\setminus\\{s\\},$
$T_{s}=L_{s}+x_{s}x_{s}^{\prime}+Q_{s}+yy^{\prime}+R_{s}$

and

$T_{n-2}=L_{n-2}+xx^{\prime}+Q_{n-2}+y_{n-2}y_{n-2}^{\prime}+R_{n-2}.$

Then there are $n-2$ internally edge disjoint trees $T_{1},\dots,T_{n-2}$
connecting $S$.

###  3.5 Case 5

Assume that $x,y,z\in V_{1}$ and $w\in V_{2}$.

Suppose first that $n=4$. Note that $B_{3}$ is a cycle of length $6$. Let
$P_{xy}$, $P_{xz}$, and $P_{yz}$ be the $(x,y)$-path, $(x,z)$-path and
$(y,z)$-path in $B_{3}^{1}$ with $z\notin V(P_{xy})$, $y\notin V(P_{xz})$ and
$x\notin V(P_{yz})$, respectively. Suppose that $w^{\prime}\in V_{1}$. If
$w^{\prime}\notin\\{x,y,z\\}$, then there is a spanning tree $T_{1}$ in
$B_{3}^{1}$ and a spanning tree $T_{2}$ in $B_{4}[V(B_{4})\setminus V_{1}]$,
so $T_{1}^{*}=T_{1}+w^{\prime}w$ and
$T_{2}^{*}=T_{2}+x^{\prime}x+y^{\prime}y+z^{\prime}z$ are two internally edge
disjoint trees connecting $S$. If $w^{\prime}\in\\{x,y,z\\}$, say
$w^{\prime}=x$, then there is a spanning tree $T$ in $B_{4}[V(B_{4})\setminus
V_{1}]$, so $T_{1}=wx+P_{xy}+P_{yz}$ and
$T_{2}=P_{xz}+zz^{\prime}+T+y^{\prime}y$ are two internally edge disjoint
trees connecting $S$. Next suppose that $w^{\prime}\notin V_{1}$. Note that
one of $x^{\prime},y^{\prime},z^{\prime}$, say $x^{\prime}$, lies outside
$B_{3}^{2}$. Then $x^{\prime}\in V_{3}\cup V_{4}$. Assume that $x^{\prime}\in
V_{3}$. Let $x_{1}=x[1,2]$ and assume that $x_{1}\in V(P_{xy})$.

If $z^{\prime}\in V_{2}$, then we choose a vertex $w_{1}$ in $B_{3}^{2}$
different from $w,z^{\prime}$ such that $w_{1}^{\prime}\in V_{3}$. By Lemmas
2.2 and 2.4, there are two $(w,\\{w_{1},z^{\prime}\\})$-paths $L_{1}$ and
$L_{2}$. Assume that $w_{1}\in V(L_{1})$ and $z^{\prime}\in V(L_{2})$. Since
$w,w_{1}^{\prime}\in V_{3}\cup V_{4}$, there are two
$(\\{w^{\prime},w_{1}^{\prime}\\},\\{x^{\prime},x_{1}^{\prime}\\})$-paths
$Q_{1}$ and $Q_{2}$ in $B_{4}[V_{1}\cup V_{2}]$ by Lemmas 2.1 and 2.6. Assume
that $w_{1}^{\prime}\in V(Q_{1})$. If $x^{\prime}\in V(Q_{1})$, let
$T_{1}=P_{yz}+P_{xz}+xx^{\prime}+Q_{1}+w_{1}^{\prime}w_{1}+L_{1}$ and
$T_{2}=P_{xy}+x_{1}x_{1}^{\prime}+Q_{2}+w^{\prime}w+L_{2}+z^{\prime}z$. If
$x^{\prime}\in V(Q_{2})$, let
$T_{1}=P_{yz}+P_{xz}+xx^{\prime}+Q_{2}+w^{\prime}w$ and
$T_{2}=P_{xy}+x_{1}x_{1}^{\prime}+Q_{1}+w_{1}^{\prime}w_{1}+L_{1}+L_{2}+z^{\prime}z$.
Then $T_{1}$ and $T_{2}$ are two internally edge disjoint trees connecting
$S$.

If $z^{\prime}\in V_{3}\cup V_{4}$, say $z^{\prime}\in V_{4}$. If
$w^{\prime}\in V_{4}$, let $w_{1}$ and $w_{2}$ be two vertices in $B_{3}^{2}$
with $w_{1}^{\prime},w_{2}^{\prime}\in V_{3}$, and there are two internally
vertex disjoint $(w,w_{i})$-path $L_{i}$ for $i=1,2$ in $B_{3}^{2}$ by Lemma
2.4. Similarly, there are two internally vertex disjoint
$(\\{x^{\prime},x_{1}^{\prime}\\},\\{w_{1}^{\prime},w_{2}^{\prime}\\})$-paths
$Q_{1}$ and $Q_{2}$ in $B_{3}^{3}$ and one $(w^{\prime},z^{\prime})$-path $K$
in $B_{3}^{4}$. Then
$T_{1}=P_{yz}+P_{xz}+xx^{\prime}+Q_{1}+w_{1}^{\prime}w_{1}+L_{1}$ and
$T_{2}=P_{xy}+x_{1}x_{1}^{\prime}+Q_{2}+w_{2}^{\prime}w_{2}+L_{2}+ww^{\prime}+K+z^{\prime}z$
are two internally edge disjoint trees connecting $S$. Otherwise,
$w^{\prime}\in V_{3}$. Let $w_{1}$ and $w_{2}$ be two vertices in $B_{3}^{2}$
with $w_{1}^{\prime}\in V_{3}$ and $w_{2}^{\prime}\in V_{4}$. By similar
argument above, we may obtain two internally edge disjoint trees connecting
$S$.

Now suppose that $n\geq 5$. Let

$x=(p_{1},\dots,p_{n-1},1),y=(q_{1},\dots,q_{n-1},1),z=(r_{1},\dots,r_{n-1},1).$

Then $x\in V_{p_{n-1}}^{1}$, $y\in V_{q_{n-1}}^{1}$ and $z\in
V_{r_{n-1}}^{1}$.

Case 5.1. $x^{\prime},y^{\prime}$ and $z^{\prime}$ lie in three different main
parts.

Let $x_{i}=x[i,i+1]$ for $i\in[n-2]$. Then $x_{1},\dots,x_{n-3}\in
V_{p_{n-1}}^{1}$ and $x_{n-2}\in V_{p_{n-2}}^{1}$. Since $q_{n-1}\neq
r_{n-1}$, we may assume that $x_{n-2}\notin V_{q_{n-1}}^{1}$. By Lemma 2.6,
there are $n-3$ internally vertex disjoint $(x,y)$-paths $L_{1},\dots,L_{n-3}$
in $B_{n-1}^{1}$. Assume that $x_{i}\in V(L_{i})$ for $i\in[n-3]$. Let
$\widehat{x}_{i}=x_{i}[n-2,n-1]$ for $i\in[n-4]$ and let
$Z=\\{\widehat{x}_{i}:i\in[n-4]\\}\cup\\{x_{n-2}\\}$. We have $Z\subseteq
V_{1}\setminus(V_{p_{n-1}}^{1}\cup V_{q_{n-1}}^{1})$. As
$\kappa(B_{n-1}^{1}[V_{1}\setminus(V_{p_{n-1}}^{1}\cup
V_{q_{n-1}}^{1})])=n-3$, there are $n-3$ internally vertex disjoint
$(z,Z)$-paths $Q_{1},\dots,Q_{n-3}$. Assume that $\widehat{x}_{i}\in V(Q_{i})$
for $i\in[n-4]$ and $x_{n-2}\in V(Q_{n-3})$. Let
$F=\\{x_{i}^{\prime}:i\in[n-3]\\}\cup\\{x^{\prime},y^{\prime},z^{\prime}\\}$
and $F_{1}=F\cap V_{2}$.

Case 5.1.1. $F_{1}=\emptyset$.

There are three possibilities: (i) $w^{\prime}\notin V_{1}\cup V_{p_{n-1}}$,
(ii) $w^{\prime}\in V_{p_{n-1}}$ and (iii) $w^{\prime}\in V_{1}$.

For (i), choose $n-2$ vertices $w_{1},\dots,w_{n-2}\in V_{2}$ with out-
neighbors in $V_{p_{n-1}}$. Then there are $n-2$ internally vertex disjoint
$(w,w_{i})$-paths $H_{i}$ for $i\in[n-2]$ in $B_{n-1}^{2}$. Let
$X=\\{x_{i}^{\prime}:i\in[n-3]\\}\cup\\{x^{\prime}\\}$ and
$W=\\{w_{i}^{\prime}:i\in[n-2]\\}$. Then $X,W\subseteq V_{p_{n-1}}$ with
$|X|=|W|=n-2$. By Lemma 2.1, there are $n-2$ internally vertex disjoint
$(X,W)$-paths $R_{1},\dots,R_{n-2}$ in $B_{n-1}^{p_{n-1}}$. Assume that
$x_{i}^{\prime},w_{i}^{\prime}\in V(R_{i})$ for $i\in[n-3]$ and
$x^{\prime},w_{n-2}\in V(R_{n-2})$. Since
$y^{\prime},z^{\prime},w^{\prime}\notin V_{1}\cup V_{p_{n-1}}$ and
$B_{n}[V(B_{n})\setminus(V_{1}\cup V_{p_{n-1}})]$ is connected, there is a
tree $T$ containing $y^{\prime},z^{\prime},w^{\prime}$. Let

$T_{i}=H_{i}+w_{i}w_{i}^{\prime}+R_{i}+x_{i}^{\prime}x_{i}+L_{i}+x_{i}\widehat{x}_{i}+Q_{i}\mbox{
for }i\in[n-4],$
$T_{n-3}=H_{n-3}+w_{n-3}w_{n-3}^{\prime}+R_{n-3}+x_{n-3}^{\prime}x_{n-3}+L_{n-3}+xx_{n-2}+Q_{n-3},$

and

$T_{n-2}=xx^{\prime}+R_{n-2}+w_{n-2}^{\prime}w_{n-2}+H_{n-2}+ww^{\prime}+T+y^{\prime}y+z^{\prime}z$

Then there are $n-2$ internally edge disjoint trees $T_{1},\dots,T_{n-2}$
connecting $S$.

For (ii), let $w_{1},\dots,w_{n-3}$ be $n-3$ vertices in $B_{n-1}^{2}$ with
out-neighbors in $B_{n-1}^{p_{n-1}}$ and $w_{n-2}\in V_{2}$ be one vertex with
out-neighbor in $B_{n}[V(B_{n})\setminus(V_{1}\cup V_{p_{n-1}})]$. By Lemmas
2.2 and 2.4, there are $n-2$ internally vertex disjoint $(w,w_{i})$-paths
$H_{i}$ for $i\in[n-2]$ in $B_{n-1}^{2}$. Let
$X=\\{x_{i}^{\prime}:i\in[n-3]\\}\cup\\{x^{\prime}\\}$ and
$W=\\{w_{i}^{\prime}:i\in[n-3]\\}\cup\\{w^{\prime}\\}$. Then $X,W\subseteq
V_{p_{n-1}}$ with $|X|=|W|=n-2$. By Lemma 2.1, there are $n-2$ internally
vertex disjoint $(X,W)$-paths $R_{1},\dots,R_{n-2}$ in $B_{n-1}^{p_{n-1}}$.
Assume that $x_{i}^{\prime}\in V(R_{i})$ for $i\in[n-3]$, $x^{\prime}\in
V(R_{n-2})$, $w^{\prime}\in V(R_{s})$ for some $s\in[n-2]$, $w_{i}^{\prime}\in
V(R_{i})$ for $i\in[n-3]\setminus\\{s\\}$ and $w_{s}^{\prime}\in V(Q_{n-2})$.
Since $y^{\prime},z^{\prime},w_{n-2}^{\prime}\notin V_{1}\cup V_{p_{n-1}}$,
there is a tree $T$ with $y^{\prime},z^{\prime},w_{n-2}^{\prime}\in V(T)$ in
$B_{n}[V(B_{n})\setminus(V_{1}\cup V_{p_{n-1}})]$. If $s=n-2$, let

$T_{i}=H_{i}+w_{i}w_{i}^{\prime}+R_{i}+x_{i}^{\prime}x_{i}+L_{i}+x_{i}\widehat{x}_{i}+Q_{i}\mbox{
for }i\in[n-4],$
$T_{n-3}=H_{n-3}+w_{n-3}w_{n-3}^{\prime}+R_{n-3}+x_{n-3}^{\prime}x_{n-3}+L_{n-3}+xx_{n-2}+Q_{n-3},$

and

$T_{n-2}=xx^{\prime}+R_{n-2}+w^{\prime}w+H_{n-2}+w_{n-2}w_{n-2}^{\prime}+T+y^{\prime}y+z^{\prime}z.$

If $s=n-3$, let

$T_{i}=H_{i}+w_{i}w_{i}^{\prime}+R_{i}+x_{i}^{\prime}x_{i}+L_{i}+x_{i}\widehat{x}_{i}+Q_{i}\mbox{
for }i\in[n-4],$
$T_{n-3}=ww^{\prime}+R_{n-3}+x_{n-3}^{\prime}x_{n-3}+L_{n-3}+xx_{n-2}+Q_{n-3}$

and

$T_{n-2}=xx^{\prime}+R_{n-2}+w_{n-3}^{\prime}w_{n-3}+H_{n-3}+H_{n-2}+w_{n-2}w_{n-2}^{\prime}+T+y^{\prime}y+z^{\prime}z.$

Otherwise, let

$T_{i}=H_{i}+w_{i}w_{i}^{\prime}+R_{i}+x_{i}^{\prime}x_{i}+L_{i}+x_{i}\widehat{x}_{i}+Q_{i}\mbox{
for }i\in[n-4]\setminus\\{s\\},$
$T_{s}=ww^{\prime}+R_{s}+x_{s}^{\prime}x_{s}+L_{s}+x_{s}\widehat{x}_{s}+Q_{s},$
$T_{n-3}=H_{n-3}+w_{n-3}w_{n-3}^{\prime}+R_{n-3}+x_{n-3}^{\prime}x_{n-3}+L_{n-3}+xx_{n-2}+Q_{n-3}$

and

$T_{n-2}=xx^{\prime}+R_{n-2}+w_{s}^{\prime}w_{s}+H_{s}+H_{n-2}+w_{n-2}w_{n-2}^{\prime}+T+y^{\prime}y+z^{\prime}z.$

Then $T_{1},\dots,T_{n-2}$ are $n-2$ internally edge disjoint trees connecting
$S$.

Now we consider (iii). Suppose that
$N_{B_{n-1}^{1}}[w^{\prime}]\cap\cup_{i=1}^{n-3}(V(L_{i})\cup
V(Q_{i}))=\emptyset$. Let $\widehat{w}=w^{\prime}[n-2,n-1]$. If
$\widehat{w}^{\prime}\notin V_{p_{n-1}}$ ($\widehat{w}^{\prime}\in
V_{p_{n-1}}$, respectively), then we use $\widehat{w}^{\prime}$ for
$w^{\prime}$ in the above argument in (i) ((ii), respectively). So we obtain
$n-2$ internally edge disjoint trees connecting $S$. Otherwise, assume that
$\widetilde{w}\in N_{B_{n-1}^{1}}[w^{\prime}]\cap\cup_{i=1}^{n-3}(V(L_{i})\cup
V(Q_{i}))$. Since $F_{1}=\emptyset$, $\widetilde{w}\in V(Q_{s})$ for some
$s\in[n-3]$. Let $w_{1},\dots,w_{n-3}$ be $n-3$ vertices in $B_{n-1}^{2}$ with
out-neighbors in $B_{n-1}^{p_{n-1}}$ and $w_{n-2}$ be a vertex in
$B_{n-1}^{2}$ with out-neighbor in $B_{n}[V(B_{n})\setminus(V_{1}\cup
V_{p_{n-1}})]$. By Lemma 2.6, there are $n-2$ internally vertex disjoint
$(w,w_{i})$-paths $H_{i}$ for $i\in[n-2]$. Let
$X=\\{x_{i}^{\prime}:i\in[n-3]\setminus\\{s\\}\\}\cup\\{x^{\prime}\\}$ and
$W=\\{w_{i}^{\prime}:i\in[n-3]\\}$. Then $X,W\subseteq V_{p_{n-1}}$ with
$|X|=|W|=n-3$. By Lemmas 2.1 and 2.4, there are $n-3$ internally vertex
disjoint $(X,W)$-paths $R_{1},\dots,R_{n-3}$ in $B_{n-1}^{p_{n-1}}$. Assume
that $x_{i}^{\prime},w_{i}^{\prime}\in V(R_{i})$ for
$i\in[n-3]\setminus\\{s\\}$ and $x^{\prime},w_{s}^{\prime}\in V(R_{s})$. Since
$w_{n-2}^{\prime},y^{\prime},z^{\prime}\notin V_{1}\cup V_{p_{n-1}}$, there is
a spanning tree $T$ in $B_{n}[V(B_{n})\setminus(V_{1}\cup V_{p_{n-1}})]$ with
$w_{n-2}^{\prime},y^{\prime},z^{\prime}\in V(T)$ by Lemma 2.6. If $s=n-3$, let

$T_{i}=H_{i}+w_{i}w_{i}^{\prime}+R_{i}+x_{i}^{\prime}x_{i}+L_{i}+x_{i}\widehat{x}_{i}+Q_{i}\mbox{
for }i\in[n-4],$
$T_{n-3}=\begin{cases}L_{n-3}+xx_{n-2}+Q_{n-3}+w^{\prime}w&\mbox{ if
}\widetilde{w}=w^{\prime}\\\
L_{n-3}+xx_{n-2}+Q_{n-3}+\widetilde{w}w^{\prime}+w^{\prime}w&\mbox{
otherwise}\end{cases}$

and

$T_{n-2}=xx^{\prime}+R_{n-3}+w_{n-3}^{\prime}w_{n-3}+H_{n-3}+H_{n-2}+w_{n-2}w_{n-2}^{\prime}+T+y^{\prime}y+z^{\prime}z.$

Otherwise, let

$T_{i}=H_{i}+w_{i}w_{i}^{\prime}+R_{i}+x_{i}^{\prime}x_{i}+L_{i}+x_{i}\widehat{x}_{i}+Q_{i}\mbox{
for }i\in[n-4]\setminus\\{s\\},$
$T_{s}=\begin{cases}L_{s}+x_{s}\widehat{x}_{s}+Q_{s}+w^{\prime}w,&\mbox{ if
}\widetilde{w}=w^{\prime},\\\
L_{s}+x_{s}\widehat{x}_{s}+Q_{s}+\widetilde{w}w^{\prime}+w^{\prime}w&\mbox{
otherwise},\end{cases}$
$T_{n-3}=H_{n-3}+w_{n-3}w_{n-3}^{\prime}+R_{n-3}+x_{n-3}^{\prime}x_{n-3}+L_{n-3}+xx_{n-2}+Q_{n-3},$

and

$T_{n-2}=xx^{\prime}+R_{n-3}+w_{s}^{\prime}w_{s}+H_{s}+H_{n-2}+w_{n-2}w_{n-2}^{\prime}+T+y^{\prime}y+z^{\prime}z.$

Then $T_{1},\dots,T_{n-2}$ are $n-2$ internally edge disjoint trees connecting
$S$.

Case 5.1.2. $F_{1}=\\{x_{i}^{\prime}:i\in[n-3]\\}\cup\\{x^{\prime}\\}$.

Suppose that $w^{\prime}\notin V_{1}$. By Lemmas 2.2 and 2.4, there are $n-2$
internally vertex disjoint $(w,F_{1})$-paths $H_{1},\dots,H_{n-2}$ in
$B_{n-1}^{2}$. Assume that $x_{i}^{\prime}\in V(H_{i})$ for $i\in[n-3]$ and
$x^{\prime}\in V(H_{n-2})$. Since $y^{\prime},z^{\prime},w^{\prime}\in
V(B_{n})\setminus(V_{1}\cup V_{2})$, there is a spanning tree $T$ in
$B_{n}[V(B_{n})\setminus(V_{1}\cup V_{2})]$ with
$y^{\prime},z^{\prime},w^{\prime}\in V(T)$. Let

$T_{i}=H_{i}+x_{i}^{\prime}x_{i}+L_{i}+x_{i}\widehat{x}_{i}+Q_{i}\mbox{ for
}i\in[n-4],$
$T_{n-3}=H_{n-3}+x_{n-3}^{\prime}x_{n-3}+L_{n-3}+xx_{n-2}+Q_{n-3},$

and

$T_{n-2}=T+yy^{\prime}+zz^{\prime}+w^{\prime}w+H_{n-2}+x^{\prime}x.$

Then there are $n-2$ internally edge disjoint trees $T_{1},\dots,T_{n-2}$
connecting $S$.

Suppose that $w^{\prime}\in V_{1}$. If
$N_{B_{n-1}^{1}}[w^{\prime}]\cap\cup_{i=1}^{n-3}(V(L_{i})\cup
V(Q_{i}))=\emptyset$, then we may consider $\widehat{w}^{\prime}$ as
$w^{\prime}$ in the argument above with $\widehat{w}=w^{\prime}[n-2,n-1]$, and
hence obtain $n-2$ internally edge disjoint trees connecting $S$. Otherwise,
some vertex in $N_{B_{n-1}^{1}}[w^{\prime}]$ lies on some path $L_{i}$ or
$Q_{i}$, so the argument is similar to that in Case 5.1.1.

Case 5.1.3. $F_{1}=\\{y^{\prime}\\}$ or $F_{1}=\\{z^{\prime}\\}$, say
$F_{1}=\\{y^{\prime}\\}$.

Let $y_{i}=y[i,i+1]$ for $i\in[n-2]$. Note $p_{n-1}\neq r_{n-1}$. Assume that
$y_{n-2}\notin V_{p_{n-1}}^{1}$. By Lemma 2.6, there are $n-3$ internally
vertex disjoint $(x,y)$-paths $L_{1},\dots,L_{n-3}$ in
$B_{n-1}^{1}[V_{p_{n-1}}^{1}\cup V_{q_{n-1}}^{1}]$. Assume that $y_{i}\in
V(L_{i})$ for $i\in[n-3]$. Let $\widehat{y}_{i}=y_{i}[n-2,n-1]$ for
$i\in[n-4]$ and let $Z=\\{\widehat{y}_{i}:i\in[n-4]\\}\cup\\{y_{n-2}\\}$. Then
$Z\subseteq V_{1}\setminus(V_{p_{n-1}}^{1}\cup V_{q_{n-1}}^{1})$. Since
$\kappa(B_{n-1}^{1}[V_{1}\setminus(V_{p_{n-1}}^{1}\cup
V_{q_{n-1}}^{1})])=n-3$, there are $n-3$ internally vertex disjoint
$(z,Z)$-paths $Q_{1},\dots,Q_{n-3}$. Assume that $\widehat{y}_{i}\in V(Q_{i})$
for $i\in[n-4]$ and $y_{n-2}\in V(Q_{n-3})$. Let
$F_{2}=(\\{y_{i}^{\prime}:i\in[n-3]\\}\cup\\{x^{\prime},y^{\prime},z^{\prime}\\})\cap
V_{2}$. Recall that $y^{\prime}\in V_{2}$, then
$F_{2}=\\{y_{i}^{\prime}:i\in[n-3]\\}\cup\\{y^{\prime}\\}$. Now by considering
whether $w^{\prime}$ is in $V_{1}$ and similar argument as in Case 5.1.2,
there are $n-2$ internally edge disjoint trees connecting $S$.

Case 5.2. $x^{\prime},y^{\prime}$ and $z^{\prime}$ lie in two different main
parts.

Assume that $x^{\prime}$ lies in different main part from $y^{\prime}$ and
$z^{\prime}$. For $j\in[n]\setminus\\{2\\}$,

Since $\kappa(B_{n-2}^{(1,j)})=n-3$, there are $n-3$ internally vertex
disjoint $(y,z)$-paths $L_{1},\dots,L_{n-3}$ in $B_{n-2}^{(1,q_{n-1})}$.
Assume that $y_{i}\in V(L_{i})$ and let $\widehat{y}_{i}=y_{i}[n-2,n-1]$ for
$i\in[n-3]$. Then $\widehat{y}_{i}\in(V_{q_{n-2}}^{1}\cup
V_{q_{n-3}}^{1})\subseteq V_{1}$. Since $x\in V_{p_{n-1}}^{1}\subseteq V_{1}$,
there are $n-3$ internally vertex disjoint $(x,\widehat{y}_{i})$-paths $Q_{i}$
in $B_{n-1}^{1}[V_{p_{n-1}}\cup V_{q_{n-2}}\cup V_{q_{n-3}}^{1}]$ for
$i\in[n-3]$ by Lemma 2.6. Let $x_{i}=x[i,i+1]$ for $i\in[n-3]$. Assume that
$x_{i}\in V(Q_{i})$ with $i\in[n-3]$. Let
$F=\\{x_{i}^{\prime}:i\in[n-3]\\}\cup\\{x^{\prime},y^{\prime},z^{\prime}\\}$
and $F_{1}=F\cap V_{2}$. There are three possibilities: (i) $F_{1}=\emptyset$,
(ii) $F_{1}=\\{x_{i}^{\prime}:i\in[n-3]\\}\cup\\{x^{\prime}\\}$ and (iii)
$F_{1}=\\{y^{\prime},z^{\prime}\\}$. The argument for (i) and (ii) is similar
as in Case 5.1.1 and Case 5.1.2, respectively. So we only consider (iii).
Suppose that $w\in V_{\ell}^{2}$ with $\ell\neq 2$.

Case 5.2.1. $w^{\prime}\notin V_{1}$.

We choose $n-3$ vertices $w_{1},\dots,w_{n-3}\in V_{\ell}^{2}$, then there are
$n-3$ internally vertex disjoint $(w,w_{i})$-paths $H_{i}$ for $i\in[n-3]$ in
$B_{n-2}^{(2,\ell)}$. Let $\widehat{w}=w[n-2,n-1]$. As
$\widehat{w},y^{\prime},z^{\prime}\in V_{2}\setminus V_{\ell}^{2}$, there is a
tree $T_{n-2}^{*}$ containing $\widehat{w},y^{\prime},z^{\prime}$ in
$B_{n-2}^{(2,\ell)}$ by Lemma 2.6. Let
$Y=\\{\widehat{y}_{i}^{\prime}:i\in[n-3]\\}\cup\\{x^{\prime}\\}$ and
$W=\\{w_{i}^{\prime}:i\in[n-3]\\}\cup\\{w^{\prime}\\}$. Then $Y,W\subseteq
V(B_{n})\setminus(V_{1}\cup V_{2})$, and so there are $n-2$ internally vertex
disjoint $(Y,W)$-paths $R_{1},\dots,R_{n-2}$ by Lemma 2.6. Assume that
$\widehat{y}_{i}^{\prime}\in V(R_{i})$ for $i\in[n-3]$, $x^{\prime}\in
V(R_{n-2})$, $w^{\prime}\in V(R_{s})$ for some $s\in[n-2]$, $w_{i}^{\prime}\in
V(R_{i})$ for $i\in[n-3]\setminus\\{s\\}$ and $w_{s}^{\prime}\in V(R_{n-2})$.
If $s=n-2$, let

$T_{i}=L_{i}+y_{i}\widehat{y}_{i}+Q_{i}+\widehat{y}_{i}\widehat{y}_{i}^{\prime}+R_{i}+w_{i}^{\prime}w_{i}+H_{i}\mbox{
for }i\in[n-3]$

and

$T_{n-2}=xx^{\prime}+R_{n-2}+w^{\prime}w+w\widehat{w}+T_{n-2}^{*}.$

Otherwise, let

$T_{i}=L_{i}+y_{i}\widehat{y}_{i}+Q_{i}+\widehat{y}_{i}\widehat{y}_{i}^{\prime}+R_{i}+w_{i}^{\prime}w_{i}+H_{i}\mbox{
for }i\in[n-3]\setminus\\{s\\},$
$T_{s}=L_{s}+y_{s}\widehat{y}_{s}+Q_{s}+\widehat{y}_{s}\widehat{y}_{s}^{\prime}+R_{s}+ww^{\prime}$

and

$T_{n-2}=xx^{\prime}+R_{n-2}+w_{s}^{\prime}w_{s}+H_{s}+w\widehat{w}+T_{n-2}^{*}.$

Hence, we obtain $n-2$ internally edge disjoint trees connecting $S$.

Case 5.2.2. $w^{\prime}\in V_{1}$.

If $N_{B_{n-1}^{1}}[w^{\prime}]\cap\cup_{i=1}^{n-3}(V(L_{i})\cup
V(Q_{i}))=\emptyset$, the result follows by considering $\widehat{w}^{\prime}$
for $w^{\prime}$ in the above proof with $\widehat{w}=w^{\prime}[n-2,n-1]$.

Suppose that $N_{B_{n-1}^{1}}[w^{\prime}]\cap\cup_{i=1}^{n-3}(V(L_{i})\cup
V(Q_{i}))\not=\emptyset$. Let $y_{i}=y[i,i+1]$, $w_{i}=w[i,i+1]$ and assume
that $y_{i}\in V(L_{i})$, $\widehat{y}_{i}\in V(Q_{i})$ for $i\in[n-3]$. Let
$\widehat{x}=x[n-2,n-1]$, $\widehat{z}=z^{\prime}[n-2,n-1]$,
$\widehat{w}=w[n-2,n-1]$ and $\widehat{w}_{i}=w_{i}[n-2,n-1]$ for $i\in[n-3]$.

Suppose that $y$ or $z$, say $y$, is adjacent to $w$. Then
$y_{i}^{\prime}=w_{i}$ for $i\in[n-3]$. If $z$ is not adjacent to $y$, then,
since $\kappa(B_{n-1}^{2})=n-2$, there is a $(z^{\prime},\widehat{w})$-path
$R$ in $B_{n-1}^{2}[V_{2}\setminus\\{w_{i}:i\in[n-3]\\}]$. Noting that
$\widehat{w}^{\prime},x^{\prime}\in V(B_{n})\setminus(V_{1}\cup V_{2})$, there
is an $(x^{\prime},\widehat{w}^{\prime})$-path $K$. Let

$T_{i}=ww_{i}+w_{i}^{\prime}y_{i}+L_{i}+y_{i}\widehat{y}_{i}+Q_{i}\mbox{ for
}\in[n-3]$

and

$T_{n-2}=xx^{\prime}+K+\widehat{w}^{\prime}\widehat{w}+R+z^{\prime}z+\widehat{w}w+wy.$

Then we obtain $n-2$ internally edge disjoint trees $T_{1},\dots,T_{n-2}$
connecting $S$. Suppose that $z$ is adjacent to $y$, say $z=y_{\xi}$ for some
$\xi\in[n-2]$. Then $z^{\prime}=w_{\xi}$. Let

$T_{i}=ww_{i}+w_{i}y_{i}+L_{i}+y_{i}\widehat{y}_{i}+Q_{i}\mbox{ for
}i\in[n-3]\setminus\\{\xi\\}.$

and $\widehat{y}=y[n-2,n-1]$. We consider $\widehat{y}\neq x$ and
$\widehat{y}=x$ separately. Suppose that $\widehat{y}\neq x$. Note that
$x^{\prime},\widehat{y}^{\prime},\widehat{w}_{\xi}^{\prime},\widehat{w}^{\prime}\notin
V_{1}\cup V_{2}$, there are two
$(\\{x^{\prime},\widehat{y}^{\prime}\\},\\{\widehat{w}_{\xi}^{\prime},\widehat{w}^{\prime}\\})$-paths
$R_{1}$ and $R_{2}$ by Lemma 2.6. If $x^{\prime}$ and
$\widehat{w}_{\xi}^{\prime}$ are in the same path, say $R_{1}$, let

$T_{\xi}=xx^{\prime}+R_{1}+\widehat{w}_{\xi}^{\prime}\widehat{w}_{\xi}+\widehat{w}_{\xi}w_{\xi}+w_{\xi}w+wy,$

and

$T_{n-2}=Q_{\xi}+\widehat{y}y+yz+\widehat{y}\widehat{y}^{\prime}+R_{2}+\widehat{w}^{\prime}\widehat{w}+\widehat{w}w.$

Otherwise, assume that $x^{\prime}$ is in $R_{1}$, let

$T_{\xi}=xx^{\prime}+R_{1}+\widehat{w}^{\prime}\widehat{w}+\widehat{w}w+wy+yz$

and

$T_{n-2}=Q_{\xi}+\widehat{y}y+\widehat{y}\widehat{y}^{\prime}+R_{2}+\widehat{w}_{\xi}^{\prime}\widehat{w}_{\xi}+\widehat{w}_{\xi}w_{\xi}+w_{\xi}w+w_{\xi}z.$

So we obtain $n-2$ internally edge disjoint trees $T_{1},\dots,T_{n-2}$
connecting $S$. Now suppose that $\widehat{y}=x$. Then

$x=(q_{1},\dots,q_{n-3},2,q_{n-2},1)\mbox{ and
}x^{\prime}=(q_{1},\dots,q_{n-3},2,1,q_{n-2}).$

Recall that $w=y^{\prime}$. Then

$w=(q_{1},\dots,q_{n-3},q_{n-2},1,2),\widehat{w}=(q_{1},\dots,q_{n-3},1,q_{n-2},2)$

and

$\widehat{w}^{\prime}=(q_{1},\dots,q_{n-3},1,2,q_{n-2}).$

It can be seen that $x^{\prime}$ is adjacent to $\widehat{w}^{\prime}$. Let

$T_{\xi}=yw+wz^{\prime}+z^{\prime}z+z\widehat{y}_{\xi}+Q_{\xi}$

and

$T_{n-2}=zy+yx+xx^{\prime}+x^{\prime}\widehat{w}^{\prime}+\widehat{w}^{\prime}\widehat{w}+\widehat{w}w.$

So there are $n-2$ internally edge disjoint trees $T_{1},\dots,T_{n-2}$
connecting $S$.

Next suppose that $y$ and $z$ are not adjacent to $w$. Suppose that
$y^{\prime}$ or $z^{\prime}$, say $y^{\prime}$, is adjacent to $w$. Then
$y_{\xi}=w^{\prime}$ for some $\xi\in[n-3]$. So

$T_{\xi}=wy_{\xi}+L_{\xi}+y_{\xi}\widehat{y}_{\xi}+Q_{\xi}$

is a tree containing the vertices in $S$. Let $W$ be the set of $n-4$
neighbors of $w$ such that they are not adjacent to $y$ or $z$ and
$Y=\\{\widehat{y}_{i}^{\prime}:i\in[n-3]\setminus\\{\xi\\}\\}$. Similarly to
the above argument, we may obtain $n-4$ internally vertex disjoint
$(Y,W)$-paths and hence $n-4$ internally edge disjoint trees $T_{i}$ for
$i\in[n-3]\setminus\\{\xi\\}$ connecting $S$. Since
$\kappa(B_{n-2}^{(2,1)})=n-3$, there is a tree $H$ containing
$w,y^{\prime},z^{\prime}$. Let $v_{1}=y^{\prime}[n-2,n-1]$,
$v_{2}=v_{1}[n-3,n-2]$, $v_{3}=v_{2}[n-4,n-3]$, $v_{4}=v_{3}[n-3,n-2]$,
$v_{5}=v_{4}[n-2,n-1]$ and $P_{y}=wy^{\prime}v_{1}v_{2}v_{3}v_{4}v_{5}$. Note
that there is an $(x^{\prime},v_{5}^{\prime})$-path $L_{n-2}$ with
$V(L_{n-2})\cap V(T_{i})=\emptyset$ for $i\in[n-3]$. Let

$T_{n-2}=H+P_{y}+v_{5}v_{5}^{\prime}+L_{n-2}+x^{\prime}x.$

So there are $n-2$ internally edge disjoint trees $T_{1},\dots,T_{n-2}$
connecting $S$. Suppose that
$y^{\prime},z^{\prime}\notin\\{w_{i}:i\in[n-3]\\}\cup\\{w\\}$. Let
$Y=\\{\widehat{y}_{i}^{\prime}:i\in[n-3]\\}$ and
$W=\\{\widehat{w}_{i}^{\prime}:i\in[n-4]\\}\cup\\{w_{n-2}^{\prime}\\}$. By
Lemmas 2.1 and 2.6, there are $n-3$ internally vertex disjoint $(Y,W)$-paths
in $B_{n}[V(B_{n})\setminus(V_{1}\cup V_{2})]$. Hence we may obtain $n-3$
internally edge disjoint trees $T_{i}$ for $i\in[n-3]$ by similar argument as
in Case 5.2.1. Since $\kappa(B_{n-2}^{(2,1)})=n-3$, there is a tree $H$ in
$B_{n-2}^{(2,1)}$ containing vertices $y^{\prime},z^{\prime},w$ with
$V(H)\cap\\{w_{i}:i\in[n-4]\\}=\emptyset$. By Lemma 2.6, there is an
$(x^{\prime},\widehat{w}_{n-3}^{\prime})$-path $L_{n-2}$ such that it is
disjoint with the above $n-3$ $(Y,W)$-paths. Let

$T_{n-2}=yy^{\prime}+zz^{\prime}+H+w_{n-3}\widehat{w}_{n-3}+\widehat{w}_{n-3}\widehat{w}_{n-3}^{\prime}+L_{n-2}+x^{\prime}x.$

Then there are $n-2$ internally edge disjoint trees $T_{1},\dots,T_{n-2}$
connecting $S$.

Case 5.3. $x^{\prime},y^{\prime},z^{\prime}$ lie in the same main part, that
is, $p_{n-1}=q_{n-1}=r_{n-1}$.

Case 5.3.1. There is at least one of $x,y,z$, say $x$, that is not adjacent to
the others.

Since $x,y,z\in V_{p_{n-1}}^{1}$, there are $n-4$ internally edge disjoint
trees $T_{1},\dots,T_{n-4}$ connecting $\\{x,y,z\\}$ in
$B_{n-2}^{(1,p_{n-1})}$ by Lemma 2.5. Note that each $T_{i}$ contains at least
one vertex in $N_{B_{n-2}^{(1,p_{n-1})}}(x)$, say $x_{i}$, for $i\in[n-4]$.
Assume that $x_{1}=x[n-3,n-2]$. Let $\widehat{x}_{i}=x_{i}[n-2,n-1]$ for
$i\in[n-4]$, $\widehat{x}=x[n-2,n-1]$, $\widehat{y}=y[n-2,n-1]$ and
$\widehat{z}=z[n-2,n-1]$. Note that $\widehat{x},\widehat{y},\widehat{z}\notin
V_{p_{n-1}}^{1}$ and $\kappa(B_{n-2})=n-3$, there is a tree $T_{n-3}$ not in
$B_{n-2}^{(1,p_{n-1})}$ containing $\widehat{x},\widehat{y},\widehat{z}$ with
$V(T_{n-3})\cap\\{\widehat{x}_{i}:i=1,\dots,n-4\\}=\emptyset$. Assume that
$x_{1}=x[n-3,n-2]$.

Let
$F=\\{\widehat{x}_{i}^{\prime}:i=1,\dots,n-4\\}\cup\\{\widehat{x}^{\prime},x^{\prime},y^{\prime},z^{\prime}\\}$
and $F_{1}=F\cap V_{2}$. Note that $\widehat{x}_{1}^{\prime}\in V_{p_{n-3}}$,
$\widehat{x}_{i}^{\prime}\in V_{p_{n-2}}$ for $i=2,\dots,n-4$,
$\widehat{x}^{\prime}\in V_{p_{n-2}}$ and $x^{\prime},y^{\prime},z^{\prime}\in
V_{p_{n-1}}$. There are four possibilities: (i) $F_{1}=\emptyset$, (ii)
$F_{1}=\\{\widehat{x}_{i}:i=2,\dots,n-4\\}\cup\\{\widehat{x}\\}$, (iii)
$F_{1}=\\{\widehat{x}_{1}\\}$, and (iv)
$F_{1}=\\{x^{\prime},y^{\prime},z^{\prime}\\}$. Note that (i)–(iii) can be
discussed similarly as in Case 5.1. Then we only need to consider (iv).

If $w^{\prime}\notin V_{1}$, then $w\notin V_{1}^{2}$ and
$x^{\prime},y^{\prime},z^{\prime}\in V_{1}^{2}$, and so the result follows by
similar argument as in Case 5.2. So we assume that $w^{\prime}\in V_{1}$.

Suppose first that $x^{\prime},y^{\prime},z^{\prime}\notin
N_{B_{n-1}^{2}}[w]$. Let $w_{i}=w[i,i+1]$, $\widehat{w}_{i}=w_{i}[n-2,n-1]$
for $i\in[n-4]$ and $\widehat{w}=w[n-2,n-1]$. Then
$\widehat{w}_{i}^{\prime}\notin V_{1}$ for $i\in[n-4]$. Let
$W=\\{\widehat{w}_{i}^{\prime}:i\in[n-4]\\}\cup\\{\widehat{w}^{\prime}\\}$ and
$X=\\{\widehat{x}_{i}:i\in[n-4]\\}\cup\\{\widehat{x}^{\prime}\\}$. By Lemma
2.6, there are $n-3$ internally vertex disjoint $(X,W)$-paths
$L_{1},\dots,L_{n-3}$ in $B_{n}[V(B_{n})\setminus(V_{1}\cup V_{2})]$. Assume
that $\widehat{x}_{i}^{\prime}\in V(L_{i})$ for $i\in[n-4]$,
$\widehat{x}^{\prime}\in V(L_{n-3})$, $\widehat{w}\in V(L_{s})$ for some
$s\in[n-3]$, $\widehat{w}_{i}^{\prime}\in V(L_{i})$ for
$i\in[n-4]\setminus\\{s\\}$ and $\widehat{w}_{s}\in L_{n-3}$. If $s=n-3$, let

$T_{i}^{*}=T_{i}+x_{i}\widehat{x}_{i}+\widehat{x}_{i}\widehat{x}_{i}^{\prime}+L_{i}+\widehat{w}_{i}^{\prime}\widehat{w}_{i}+\widehat{w}_{i}w_{i}+w_{i}w\mbox{
for }i\in[n-3]$

and

$T_{n-3}^{*}=T_{n-3}+x\widehat{x}+\widehat{x}\widehat{x}^{\prime}+L_{n-3}+\widehat{w}^{\prime}\widehat{w}+\widehat{w}w.$

Otherwise, let

$T_{i}^{*}=T_{i}+x_{i}\widehat{x}_{i}+\widehat{x}_{i}\widehat{x}_{i}^{\prime}+L_{i}+\widehat{w}_{i}^{\prime}\widehat{w}_{i}+\widehat{w}_{i}w_{i}+w_{i}w\mbox{
for }i\in[n-4]\setminus\\{s\\},$
$T_{s}^{*}=T_{s}+x_{s}\widehat{x}_{s}+\widehat{x}_{s}\widehat{x}_{s}^{\prime}+L_{s}+\widehat{w}^{\prime}\widehat{w}+\widehat{w}w,$

and

$T_{n-3}^{*}=T_{n-3}+x\widehat{x}+\widehat{x}\widehat{x}^{\prime}+L_{n-3}+\widehat{w}_{s}^{\prime}\widehat{w}_{s}+\widehat{w}_{s}w_{s}+w_{s}w.$

In $B_{n-2}^{(2,1)}$, there is a tree $T_{n-2}$ containing
$w,x^{\prime},y^{\prime},z^{\prime}$ with
$V(T_{n-2})\cap\\{w_{i}:i\in[n-4]\\}=\emptyset$. Let

$T_{n-2}^{*}=xx^{\prime}+yy^{\prime}+zz^{\prime}+T_{n-2}.$

Hence, we obtain $n-2$ internally edge disjoint trees
$T_{1}^{*},\dots,T_{n-2}^{*}$ connecting $S$.

Suppose next that $\\{x^{\prime},y^{\prime},z^{\prime}\\}\cap
N_{B_{n-1}^{2}}[w]\neq\emptyset$.

Suppose that $x^{\prime}=w$, that is, $w$ is adjacent to $x$. Then
$y^{\prime}$ and $z^{\prime}$ are not adjacent to $w$. So
$\\{x_{i}^{\prime}:i\in[n-4]\\}\cup\\{x\\}\subseteq N_{B_{n-1}^{2}}(w)$. Let
$\widehat{w}=w[n-2,n-1]$. Then $\widehat{w}^{\prime}$ is adjacent to
$\widehat{x}^{\prime}$. Let

$T_{i}^{*}=T_{i}+x_{i}x_{i}^{\prime}+x_{i}^{\prime}w\mbox{ for }i\in[n-4]$

and

$T_{n-3}^{*}=T_{n-3}+x\widehat{x}+\widehat{x}\widehat{x}^{\prime}+\widehat{x}^{\prime}\widehat{w}^{\prime}+\widehat{w}^{\prime}\widehat{w}+\widehat{w}w.$

Since $y^{\prime},z^{\prime}\in V_{2}$ and $\kappa(B_{n-1}^{2})=n-2$, there is
a tree $T_{n-2}$ containing $w,y^{\prime},z^{\prime}$ in
$B_{n-1}^{2}[V_{2}\setminus(\\{x_{i}^{\prime}:i\in[n-4]\\}\cup\\{\widehat{w}\\})]$.
Let

$T_{n-2}^{*}=zz^{\prime}+yy^{\prime}+T_{n-2}+wx.$

Then $T_{1}^{*},\dots,T_{n-2}^{*}$ are $n-2$ internally edge disjoint trees
connecting $S$.

Suppose that $w$ is not adjacent to $x$. Suppose that $y$ or $z$, say $y$, is
adjacent to $w$. Then $x^{\prime}$ is not adjacent to $w$. Choose $n-4$
neighbors of $w$, say $w_{1},\dots,w_{n-4}$ such that each of them is not
adjacent to $y$ or $z$. By similar proof when
$x^{\prime},y^{\prime},z^{\prime}\notin N_{B_{n-1}^{2}}[w]$, we may obtain
$n-2$ internally edge disjoint trees connecting $S$. So assume in the
following that $w$ is not adjacent to $y$ or $z$. Let $w_{i}=w[i,i+1]$,
$\widehat{w}_{i}=w_{i}[n-2,n-1]$ for $i\in[n-3]$, $\widehat{w}=w[n-2,n-1]$ and
$\widehat{x}_{n-3}=\widehat{x}$. Suppose first that there is exactly one of
$x^{\prime},y^{\prime},z^{\prime}$, say $x^{\prime}$, that is adjacent to $w$.
Then $w^{\prime}=x_{s}$ and $x^{\prime}=w_{t}$ for some $s,t\in[n-3]$,

$T_{s}^{*}=T_{s}+xw$

is a tree containing vertices in $S$. Let
$X=\\{\widehat{x}_{i}^{\prime}:i\in[n-3]\setminus\\{s\\}\\}$ and
$W=\\{\widehat{w}_{i}:i\in[n-3]\setminus\\{t\\}\\}$. By Lemmas 2.1 and 2.6,
there are $n-4$ internally vertex disjoint $(X,W)$-paths $Q_{i}$ for
$i\in[n-3]\setminus\\{s\\}$ in $B_{n}[V(B_{n})\setminus(V_{1}\cup V_{2})]$.
Assume that $\widehat{x}_{i}^{\prime},\widehat{w}_{\ell_{i}}\in V(Q_{i})$ for
$i\in[n-3]\setminus\\{s\\}$, where $\ell_{i}\in[n-3]\setminus\\{t\\}$ and
$\ell_{i}\neq\ell_{j}$ if $i\neq j$. Let

$T_{i}^{*}=T_{i}+x_{i}\widehat{x}_{i}+\widehat{x}_{i}\widehat{x}_{i}^{\prime}+Q_{i}+\widehat{w}_{\ell_{i}}^{\prime}\widehat{w}_{\ell_{i}}+\widehat{w}_{\ell_{i}}w_{\ell_{i}}+w_{\ell_{i}}w$

for $i\in[n-4]\setminus\\{s\\}$ and

$T_{n-3}^{*}=T_{n-3}+x\widehat{x}+\widehat{x}\widehat{x}^{\prime}+L_{n-3}+\widehat{w}_{\ell_{n-3}}^{\prime}\widehat{w}_{\ell_{n-3}}+\widehat{w}_{\ell_{n-3}}w_{\ell_{n-3}}+w_{\ell_{n-3}}w.$

Since $\kappa(B_{n-2}^{(2,1)})=n-3$, there is a tree $T_{n-2}$ containing
$w,x^{\prime},y^{\prime},z^{\prime}$ with
$V(T_{n-2})\cap\\{w_{i}:i\in[n-3]\setminus\\{t\\}\\}=\emptyset$ in
$B_{n-2}^{(2,1)}$. Let

$T_{n-2}^{*}=xx^{\prime}+yy^{\prime}+zz^{\prime}+T_{n-2}.$

Hence, there are $n-2$ internally edge disjoint trees
$T_{1}^{*},\dots,T_{n-2}^{*}$ connecting $S$. Suppose now that there are
exactly two of $x^{\prime},y^{\prime},z^{\prime}$, say $x^{\prime}$ and
$y^{\prime}$, that are adjacent to $w$. That is, $x^{\prime}=w_{t}$ and
$y^{\prime}=w_{r}$ for some $t,r\in[n-3]$. Assume that $w^{\prime}=x_{s}$.
Then

$T_{s}^{*}=T_{s}+xw$

is a tree containing vertices in $S$. Let $\widehat{w}_{n-2}=w[n-2,n-1]$. Let
$X=\\{\widehat{x}_{i}^{\prime}:i\in[n-3]\setminus\\{s\\}\\}$ and
$W=\\{\widehat{w}_{i}^{\prime}:i\in[n-2]\setminus\\{t,r\\}\\}$. Then
$X,W\subseteq V(B_{n})\setminus(V_{1}\cup V_{2})$, there are $n-4$ internally
vertex disjoint $(X,W)$-paths $Q_{i}$ for $i\in[n-3]\setminus\\{s\\}$. By
similar argument as above, we may construct $n-2$ internally edge disjoint
trees (one of which is $T_{s}^{*}$) connecting $S$. Finally suppose that
$x^{\prime},y^{\prime},z^{\prime}$ are all adjacent to $w$. Then there are
some $t,r,s\in[n-3]$ with $t<r<s$ such that $x^{\prime}=w_{t}$,
$y^{\prime}=w_{r}$ and $z^{\prime}=w_{s}$. Since $3\leq s\leq n-3$, $n\geq 6$.
Assume that $w^{\prime}=x_{\gamma}$ for some $\gamma\in[n-4]$. Then
$T_{\gamma}^{*}=T_{\gamma}+w^{\prime}w$ is a tree containing vertices in $S$.
It can be verified that $\widehat{x}^{\prime}$ is adjacent to
$\widehat{w}^{\prime}$. Let
$X=\\{\widehat{x}_{i}^{\prime}:i\in[n-4]\setminus\\{\gamma\\}\\}$ and
$W=\\{\widehat{w}_{i}^{\prime}:i\in[n-3]\setminus\\{t,r\\}\\}$. By Lemma 2.6,
there are $n-5$ internally vertex disjoint $(X,W)$-paths $L_{i}$ for
$i\in[n-4]\setminus\\{\gamma\\}$ in $B_{n}[V(B_{n})\setminus(V_{1}\cup
V_{2})]$ with
$V(L_{i})\cap\\{\widehat{x}^{\prime},\widehat{w}^{\prime}\\}=\emptyset$ for
$i\in[n-5]$. Assume that
$\widehat{w}_{s}^{\prime},\widehat{x}_{\xi}^{\prime}\in V(L_{\xi})$ for some
$\xi\in[n-4]\setminus\\{\gamma\\}$ and
$\widehat{x}_{i}^{\prime},\widehat{w}_{\ell_{i}}^{\prime}\in V(L_{i})$ for
$i\in[n-4]\setminus\\{\gamma,\xi\\}$, where
$\ell_{i}\in[n-3]\setminus\\{t,r,s\\}$ and $\ell_{i}\neq\ell_{j}$ if $i\neq
j$. Let $y_{\xi},z_{\xi}$ be the neighbors of $y$ and $z$ in $V(L_{\xi})$,
respectively. Then $y_{\xi}^{\prime},z_{\xi}^{\prime}\in V_{1}^{2}$. Let
$\widehat{y}_{\xi}=y_{\xi}^{\prime}[n-2,n-1]$. Recall that
$z^{\prime}=\widehat{w}_{s}$ and $\kappa(B_{n-2})=n-3$. So there is a
$(\widehat{y}_{\xi},\widehat{w}_{s})$-path $Q_{\xi}$ in
$B_{n-1}^{2}[V_{2}\setminus V_{1}^{2}]$ with
$V(Q_{\xi})\cap(\\{\widehat{w}_{i}:i\in[n-3]\setminus\\{t,r,s\\}\\}\cup\\{\widehat{w}\\})=\emptyset$.
By Lemma 2.4, there is a tree $T_{n-2}$ containing
$w,x^{\prime},y^{\prime},z_{\xi}^{\prime}$ in $B_{n-2}^{(2,1)}$ with
$V(T_{n-2})\cap\\{w_{i}:i\in[n-3]\setminus\\{t,r\\}\\}=\emptyset$. Let

$T_{i}^{*}=T_{i}+x_{i}\widehat{x}_{i}^{\prime}+\widehat{x}_{i}\widehat{x}_{i}^{\prime}+L_{i}+\widehat{w}_{\ell_{i}}^{\prime}\widehat{w}_{\ell_{i}}+\widehat{w}_{\ell_{i}}w_{\ell_{i}}+w_{\ell_{i}}w$

for $i\in[n-4]\setminus\\{\gamma,\xi\\}$,

$T_{n-3}^{*}=T_{n-3}+x\widehat{x}+\widehat{x}\widehat{x}^{\prime}+\widehat{x}^{\prime}\widehat{w}^{\prime}+\widehat{w}^{\prime}\widehat{w}+\widehat{w}w,$
$T_{\xi}^{*}=xx_{\xi}+x_{\xi}\widehat{x}_{\xi}+\widehat{x}_{\xi}\widehat{x}_{\xi}^{\prime}+L_{\xi}+\widehat{w}_{s}^{\prime}\widehat{w}_{s}+\widehat{w}_{s}w+\widehat{w}_{s}z$

and

$T_{n-2}^{*}=xx^{\prime}+yy^{\prime}+T_{n-2}+z_{\xi}^{\prime}z_{\xi}+z_{\xi}z.$

Hence, we obtain $n-2$ internally edge disjoint trees
$T_{1}^{*},\dots,T_{n-2}^{*}$ connecting $S$.

Case 5.3.2. There is one of $x,y,z$, say $x$, is adjacent to the others.

Let $x_{i}=x[i,i+1]$ for $i\in[n-2]$. There exist $\ell,s\in[n-3]$ such that
$y=x_{\ell}$ and $z=x_{s}$, where $\ell<s$. Suppose first that $s=n-3$. For
$i,j\in[n]\setminus\\{1\\}$ with $i\neq j$, let
$V_{j}^{1,i}=\\{(v_{1},\dots,v_{n-3},j,i,1):(v_{1},\dots,v_{n-3})\in\mbox{Sym}_{1,i,j}(n)\\}$,
where $\mbox{Sym}_{1,i,j}(n)$ is the set of permutations of
$[n]\setminus\\{1,i,j\\}$. Let
$B_{n-3}^{(1,p_{n-1},j)}=B_{n}[V_{j}^{1,p_{n-1}}]$. Then
$B_{n-3}^{(1,p_{n-1},j)}\cong B_{n-3}$. Note that $\kappa(B_{n-3})=n-4$. So
there are $n-4$ internally vertex disjoint $(x,y)$-paths $L_{1},\dots,L_{n-4}$
in $B_{n-3}^{(1,p_{n-1},j)}$. Assume that $x_{i}\in V(L_{i})$ for $i\in[n-4]$.
Let $\widehat{x}_{i}=x_{i}[n-3,n-2]$. Then $\widehat{x}_{i}\in
V_{p_{n-1}}^{1}\setminus V_{p_{n-2}}^{(1,p_{n-1})}$, and there are $n-4$
internally vertex disjoint $(z,\widehat{x}_{i})$-paths $Q_{i}$ for
$i\in[n-4]$. Let $y_{n-2}=y[n-2,n-1]$ and $z_{n-2}=z[n-2,n-1]$. Then
$x_{n-2},y_{n-2},z_{n-2}\in V_{1}\setminus V_{p_{n-1}}^{1}$, and there is a
tree $T$ containing $x_{n-2},y_{n-2},z_{n-2}$ in $B_{n}[V_{1}\setminus
V_{p_{n-1}^{1}}]$.

Let
$F=\\{\widehat{x}_{i}^{\prime}:i\in[n-4]\\}\cup\\{x_{n-2}^{\prime},x^{\prime},y^{\prime}\\}$
and $F_{1}=F\cap V_{2}$. Then there are three possibilities: (i)
$F_{1}=\emptyset$, (ii)
$F_{1}=\\{\widehat{x}_{i}^{\prime}:i\in[n-4]\\}\cup\\{x^{\prime},y^{\prime}\\}$,
and (iii) $F_{1}=\\{x_{n-2}^{\prime}\\}$. By considering whether the out-
neighbor of $w$ lies in $V_{1}$, and by similar discussions as in Case 5.1, we
have $n-2$ internally edge disjoint trees $T_{1},\dots,T_{n-2}$ such that
$T_{1},\dots,T_{n-3}$ connect $S$ and $T_{n-2}$ contains $x,y,w$. Let
$T_{n-2}^{*}=T_{n-2}+xz+xx^{\prime}+yy^{\prime}$. Then $T_{1},\dots,T_{n-3}$,
$T_{n-2}^{*}$ are $n-2$ internally edge disjoint trees connecting $S$.

Suppose that $s<n-3$. For any $t$ with $s\leq t\leq n-3$, let
$\\{i_{1},\dots,i_{n-(t+2)},j\\}\subset[n]\setminus\\{1\\}$. Let

$\displaystyle V_{j}^{1,i_{1},\dots,i_{n-(t+2)}}$ $\displaystyle=$
$\displaystyle\\{(v_{1},\dots,v_{t},j,i_{n-(t+2)},\dots,i_{1},1):(v_{1},\dots,v_{t})\in\mbox{Sym}_{1,i_{1},\dots,i_{n-(t+2)},j}(n)\\},$

where $\mbox{Sym}_{1,i_{1},\dots,i_{n-(t+2)},j}(n)$ is the set of permutations
of $[n]\setminus\\{1,i_{1},\dots,i_{n-(t+2)},j\\}$. Then $x,y\in
V_{p_{s+1}}^{1,p_{n-1},\dots,p_{s+2}}$. Since
$B_{n}[V_{p_{s+1}}^{1,p_{n-1},\dots,p_{s+2}}]\cong B_{s}$ and
$\kappa(B_{s})=s-1$, there are $s-1$ internally vertex disjoint $(x,y)$-paths
$L_{1},\dots,L_{s-1}$ in $B_{n}[V_{p_{s+1}}^{1,p_{n-1},\dots,p_{s+2}}]$.
Assume that $x_{i}\in V(L_{i})$ for $i\in[s-1]$. Let
$\widehat{x}_{i}=x_{i}[s,s+1]$ for $i\in[s-1]$. Then $z,\widehat{x}_{i}\in
V_{p_{s+2}}^{1,p_{n-1},\dots,p_{s+3}}\setminus
V_{p_{s+1}}^{1,p_{n-1},\dots,p_{s+2}}$. By Lemma 2.6, there are $s-1$
internally vertex disjoint $(z,\widehat{x}_{i})$-path $Q_{i}$ for $i\in[s-1]$.
Let $y_{i}=y[i,i+1]$ and $z_{i}=z[i,i+1]$ for $i=s+2,\dots,n-2$. Since
$B_{n}[V_{p_{i+1}}^{1,p_{n-1},\dots,p_{i+2}}\setminus
V_{p_{i}}^{1,p_{n-1},\dots,p_{i+1}}]$ is connected, there is a tree
$T^{*}_{i}$ containing $x_{i},y_{i},z_{i}$ for $i=s+2,\dots,n-2$.

Let
$F=\\{\widehat{x}_{i}^{\prime}:i\in[s-1]\\}\cup\\{x_{i}^{\prime}:i=s+2,\dots,n-2\\}\cup\\{x^{\prime},y^{\prime}\\}$.
Then there are three possibilities: (i) $F_{1}=\emptyset$, (ii)
$F_{1}=\\{\widehat{x}_{i}^{\prime}:i\in[s-1]\\}\cup\\{x_{i}^{\prime}:i=s+2,\dots,n-3\\}\cup\\{x^{\prime},y^{\prime}\\}$,
and (iii) $F_{1}=\\{x_{n-2}^{\prime}\\}$. By considering whether the out-
neighbor of $w$ lies in $V_{1}$, and similar discussions as in Case 5.1, we
may have $n-2$ internally edge disjoint trees $T_{1},\dots,T_{n-2}$ such that
$T_{1},\dots,T_{n-3}$ connect $S$ and one $T_{n-2}$ contains $x,y,w$. Let
$T_{n-2}^{*}=T+xz+xx^{\prime}+yy^{\prime}$, we obtain $n-2$ internally edge
disjoint trees $T_{1},\dots,T_{n-3}$, $T_{n-2}^{*}$ connecting $S$. ∎

##  4 Concluding remarks

From a theoretical perspective, the generalized $k$-connectivity
$\kappa_{k}(G)$ of a connected graph of order $n\geq 2$ includes two
fundamental concepts: the connectivity for $k=2$ and the maximum number of
edge disjoint spanning trees for $k=n$. From a practical perspective, the
generalized connectivity can measure the reliability and security of a
network. The bubble-sort graph $B_{n}$ is a particular Cayley graph that is
suitable as a topology for massively parallel systems. In this article, we
prove that $\kappa_{4}(B_{n})=n-2$ for $n\geq 3$. In other words, there are
$n-2$ internally disjoint trees connecting them in $B_{n}$ for any four
vertices of $B_{n}$ when $n\geq 3$. For further work, it would be interesting
to study the generalized connectivity of Cayley graphs on symmetric groups
generated by general trees and some other important networks [23].

Acknowledgement. This work was supported by National Natural Science
Foundation of China (No. 12071158).

## References

  * [1] E. Abajo, R. Casablanca, A. Diánez, P. García-Vázquez, On generalized $3$-connectivity of the strong product of graphs, Appl. Anal. Discrete Math. 12(2) (2018) 297–317.
  * [2] J.A. Bondy, U.S.R. Murty, Graph Theory, Springer, New York, 2008.
  * [3] G. Chartrand, S.F. Kapoor, L. Lesniak, D.R. Lick, Generalized connectivity in graphs, Bull. Bombay Math. Colloq. 2 (1984) 1–6.
  * [4] G. Chartrand, F. Okamoto, P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks 55(4) (2010) 360–367.
  * [5] L. Chen, X. Li, M. Liu, Y. Mao, A solution to a conjecture on the generalized connectivity of graphs J. Combin. Optim. 33(1) (2017) 275–282
  * [6] E. Cheng, L. Lipták, N. Shawash, Orienting Cayley graphs generated by transposition trees, Comput. Math. Appl. 55 (2008) 2662–2672
  * [7] H. Gao, B. Lv, K. Wang, Two lower bounds for generalized $3$-connectivity of Cartesian product graphs, Appl. Math. Comput. 338 (2018) 305–313.
  * [8] M. Hager, Pendant tree-connectivity, J. Combin. Theory Ser. B 38(2) (1985) 179–189.
  * [9] M. Hager, Path-connectivity in graphs, Discrete Math. 59(1–2) (1986) 53–59.
  * [10] C. Li, S. Lin, S. Li, The $4$-set tree connectivity of $(n,k)$-star networks, Theor. Comput. Sci. 844 (2020) 81–86.
  * [11] H. Li, X. Li, Y. Sun, The generalized $3$-connectivity of Cartesian product graphs, Discrete Math. Theor. Comput. Sci. 14(1) (2012) 43–54.
  * [12] S. Li, W. Li, Y. Shi, H. Sun, On minimally $2$-connected graphs with generalized connectivity, J. Combin. Optim. 34(1) (2017) 141–164.
  * [13] S. Li, X. Li, W. Zhou, Sharp bounds for the generalized connectivity $\kappa_{3}(G)$, Discrete Math. 310(15–16) (2010) 2147–2163.
  * [14] S. Li, Y. Shi, J. Tu, The generalized $3$-connectivity of Cayley graphs on symmetric groups generated by trees and cycles, Graphs Combin. 33(5) (2017) 1195–1209.
  * [15] S. Li, J. Tu, C. Yu, The generalized $3$-connectivity of star graphs and bubble-sort graphs, Appl. Math. Comput. 274 (2016) 41–46.
  * [16] X. Li, Y. Mao, The generalized $3$-connectivity of lexicographic product graphs, Discrete Math. Theor. Comput. Sci. 16(1) (2014) 339–353.
  * [17] X. Li, Y. Mao, Generalized Connectivity of Graphs, Springer, New York, 2016.
  * [18] S. Lin, Q. Zhang, The generalized $4$-connectivity of hypercubes, Discrete Appl. Math. 220 (2017) 60–67.
  * [19] C.St.J.A. Nash-Williams, Edge-disjoint spanning trees of finite graphs, J. London Math. Soc. 36 (1961) 445–450.
  * [20] E.M. Palmer, On the spanning tree packing number of a graph: a survey, Discrete Math. 230(1–3) (2001) 13–21.
  * [21] W.T. Tutte, On the problem of decomposing a graph into $n$ connected factors, J. London Math. Soc. 36 (1961) 221–230.
  * [22] H. Whitney, Congruent graphs and connectivity of graphs, Amer. J. Math. 54(1) (1932) 150–168.
  * [23] J. Xu, Topological Structure and Analysis of Interconnection Networks, Kluwer Academic Publishers, Dordrecht, 2001.
  * [24] S. Zhao, R. Hao, The generalized connectivity of bubble-sort star graphs, Internat. J. Found. Comput. Sci. 30(5) (2019) 793–809.
  * [25] S. Zhao, R. Hao, The generalized $4$-connectivity of exchanged hypercubes, Appl. Math. Comput. 347 (2019) 342–353.
  * [26] S. Zhao, R. Hao, L. Wu, The generalized connectivity of $(n,k)$-bubble-sort graphs, Comput. J. 62(9) (2019) 1277–1283.
  * [27] S. Zhao, R. Hao, J. Wu, The generalized $4$-connectivity of hierarchical cubic networks, Discrete Appl. Math. 289 (2021) 194–206.