\publicationdetails

242022197538

On the Connectivity of Token Graphs of Trees

Ruy Fabila-Monroy\affiliationmark1 Partially supported by CONACYT (Mexico), grant 253261. Jesús Leaños\affiliationmark2 Ana Laura Trujillo-Negrete\affiliationmark1 Partially supported by CONACYT (Mexico), Convocatoria 2021 de Estancias Posdoctorales por México en Apoyo por SARS-CoV-2 (COVID-19). Departamento de Matemáticas, Cinvestav, CDMX, Mexico.
Unidad Académica de Matemáticas, Universidad Autónoma de Zacatecas, Zacatecas, Mexico.

(2021-06-03; 2021-11-06; 2022-02-14)

Abstract

Let $k$ and $n$ be integers such that $1\leq k\leq n-1$ , and let $G$ be a simple graph of order $n$ . The $k$ –token graph $F_{k}(G)$ of $G$ is the graph whose vertices are the $k$ -subsets of $V(G)$ , where two vertices are adjacent in $F_{k}(G)$ whenever their symmetric difference is an edge of $G$ . In this paper we show that if $G$ is a tree, then the connectivity of $F_{k}(G)$ is equal to the minimum degree of $F_{k}(G)$ .

keywords:

token graphs, connectivity, trees

1 Introduction

Throughout this paper, $G$ is a simple finite graph of order $n\geq 2$ and $k\in\{1,\ldots,n-1\}$ . The $k$ -token graph $F_{k}(G)$ of $G$ is the graph whose vertices are all the $k$ -subsets of $V(G)$ , where two $k$ -subsets are adjacent whenever their symmetric difference is a pair of adjacent vertices in $G$ . We often write token graph instead of $k$ -token graph. See Figure 1 for an example.

Refer to caption — Figure 1: A graph $G$ and its $2$ –token graph $F_{2}(G)$ .

The study of token graphs probably started with Johns (1988) PhD Thesis, in which $F_{k}(G)$ was called the $k$ -subgraph graph of $G$ and some results concerning the diameter of $F_{k}(G)$ were reported. Since then, token graphs have been defined independently at least three more times.

Alavi et al. (1991) defined $F_{2}(G)$ and call it the double vertex graph of $G$ , and a year later, Zhu et al. (1992) generalized the concept for $k\in\{2,\ldots,n-1\}$ under the name of $k$ -tuple vertex graph of $G$ . In these two papers, the authors studied several combinatorial issues of $F_{k}(G)$ such as Eulerianicity, Hamiltonicity, connectivity, regularity, etc.

This concept was reintroduced for third time by Rudolph (2002), when some connections of $F_{k}(G)$ with quantum mechanics and the graph isomorphism problem were discussed. Regarding the quantum mechanics, Rudolph used $F_{k}(G)$ to model the evolution of a cluster of $n$ interacting qubits ( $2$ -level atoms), which must have exactly $k$ qubits in excited state at any time (the $n$ qubits are the vertices of $G$ and their interactions define the edges of $G$ ). The use of $F_{k}(G)$ in this direction is still of interest, see Barghi and Ponomarenko (2009); Alzaga et al. (2010); Ouyang (2019). For instance, Ouyang (2019) showed that $F_{k}(G)$ has applications in the Heisenberg model, which is a quantum theory of magnetism.

With respect to the graph isomorphism problem, Rudolph (2002) found pairs of cospectral graphs $G$ and $H$ such that $F_{2}(G)$ and $F_{2}(H)$ are not cospectral, implying that $G$ and $H$ are not isomorphic. Following Rudolph’s approach, Audenaert et al. (2007) showed the existence of pairs of non-isomorphic cospectral graphs whose corresponding $2$ -token graphs are cospectral. A few years later, Barghi and Ponomarenko (2009), and independently, Alzaga et al. (2010), showed that for any $k\in\mathbb{Z}^{+}$ , there exist infinitely many pairs of non-isomorphic graphs whose corresponding $k$ -token graphs are cospectral. In Rudolph (2002) $F_{k}(G)$ was originally called the $k$ -level matrix of $G$ , but in Audenaert et al. (2007) $F_{k}(G)$ was renamed as the symmetric $k$ -th power of $G$ .

As far as we know, Fabila-Monroy et al. (2012) is the last paper in which $F_{k}(G)$ has been defined, under the name of the $k$ -token graph of $G$ . In that paper, Fabila-Monroy, Flores-Peñaloza, Huemer, Hurtado, Urrutia, and Wood defined $F_{k}(G)$ as “a model in which $k$ indistinguishable tokens move from vertex to vertex along the edges of a graph” and showed several results on the connectivity, diameter, chromatic and clique numbers, and Hamiltonian paths. From this last definition of $F_{k}(G)$ , it is not hard to see that the estimation of any parameter involving connectivity or the determination of the distance between vertices of $F_{k}(G)$ can be seen as a reconfiguration problem. We recall that reconfiguration problems are a family of combinatorial problems that ask if there exists a step-by-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. For two specific examples of theses connections we refer the reader to Ito et al. (2011); Yamanaka et al. (2015).

In 2017 Sloane¹¹1https://oeis.org/A085680 observed that the problem of determining the maximum size of a binary code of length $n$ and constant weight $2$ that can correct a single adjacent transposition is equivalent to determining the packing number of $F_{2}(P_{n})$ , where $P_{n}$ is the path graph of order $n$ . Gómez Soto et al. (2018) solved this problem.

Token graphs are also a generalization of Johnson graphs: if $G$ is the complete graph of order $n$ , then $F_{k}(G)$ is isomorphic to the Johnson graph $J(n,k)$ . Johnson graphs have been widely studied; the analysis of many of its combinatorial properties is an active area of research (see for instance Alavi (2015); Brouwer and Etzion ; Riyono (2007); Etzion and Bitan (1996); Terwilliger (1986)).

The following approach has been applied in several papers such as Fabila-Monroy et al. (2012); de Alba et al. (2017); Gómez Soto et al. (2018); Carballosa et al. (2017); Leaños and Trujillo-Negrete (2018); Leaños and Ndjatchi (2021).

For a given graph invariant $\eta$ , what can be said of $\eta(F_{k}(G))$ in terms of $G$ and $\eta(G)$ ?

In particular, Fabila-Monroy et al. (2012) gave families of graphs of order $n$ with connectivity exactly $t$ , and whose $k$ -token graphs have connectivity exactly $k(t-k+1)$ , whenever $k\leq t$ ; they also conjectured that if $G$ is $t$ -connected and $k\leq t$ , then $F_{k}(G)$ is at least $k(t-k+1)$ -connected. This was proven by Leaños and Trujillo-Negrete (2018). Recently, a similar lower bound was proven for edge-connectivity by Leaños and Ndjatchi (2021); they showed that if $G$ is $t$ -edge-connected and $k\leq t$ then $F_{k}(G)$ is at least $k(t-k+1)$ -edge-connected. Infinite families of graphs attaining this lower bound were also given.

In this paper we study the connectivity and edge-connectivity of $F_{k}(G)$ when $G$ is a tree. As usual let $\kappa(G)$ , $\lambda(G)$ , and $\delta(G)$ be the connectivity, edge-connectivity, and minimum degree of $G$ , respectively. It is well known that if $G$ is connected then

\kappa(G)\leq\lambda(G)\leq\delta(G).

(1)

The main result of this paper is the following.

Theorem 1.

If $G$ is a tree of order $n$ and $1\leq k\leq n-1$ then

\kappa(F_{k}(G))=\lambda(F_{k}(G))=\delta(F_{k}(G)).

We remark that while the hypothesis $k\leq\kappa(G)$ has played a central role in both results on $\kappa(F_{k}(G))$ stated in Fabila-Monroy et al. (2012); Leaños and Trujillo-Negrete (2018), this hypothesis does not hold when $G$ is a tree; this absence is responsible for the new difficulties in the proof of Theorem 1.

We now recall some standard notation which is used throughout this paper. Let $u$ and $v$ be distinct vertices of $G$ . The distance between $u$ and $v$ in $G$ is denoted by $d_{G}(u,v)$ (we sometimes write $d(u,v)$ when $G$ is understood from the context); we write $uv$ to mean that $u$ and $v$ are adjacent. The neighbourhood of $v$ in $G$ is the set $\{u\in V(G):uv\in E(G)\}$ and it is denoted by $N_{G}(v)$ . The degree of $v$ is the number $\deg_{G}(v):=|N_{G}(v)|$ . The number $\delta(G):=\min\{deg_{G}(v):v\in V(G)\}$ is the minimum degree of $G$ . A $u-v$ path of $G$ is starting at $u$ and ending in $v$ . Let $U$ and $W$ be subsets of $V(G)$ . We use: $G\setminus W$ to denote the subgraph of $G$ that results by removing $W$ from $G$ ; $U\setminus W$ to denote set subtraction; and $U\triangle W$ to denote symmetric difference. For brevity, if $m$ is a positive integer, then we use $[m]$ to denote $\{1,\ldots,m\}$ . We follow the convention that $[m]=\emptyset$ for $m=0$ .

The rest of the paper is organized as follows. In Section 1.1 we establish several ways to construct paths in $F_{k}(G)$ which come from the concatenation of certain paths of $G$ . These paths of $F_{k}(G)$ play a central role in our constructive proof of Theorem 1. In Section 1.2 we give some basic results on the connectivity structure of $F_{k}(G)$ which help us to simplify significantly the proof of Theorem 1. Finally, in Section 2 we prove Theorem 1.

1.1 Constructing Paths of $F_{k}(G)$ from Paths of $G$

In this section we construct paths in $F_{k}(G)$ using a given set of paths of $G$ . For this purpose, we find it useful to use the following interpretation of $F_{k}(G)$ given by Fabila-Monroy et al. (2012). We consider that there are $k$ indistinguishable tokens placed at the vertices of $G$ (at most one token per vertex). A vertex of $F_{k}(G)$ corresponds to one of this token configurations. Two such configurations are adjacent in $F_{k}(G)$ if and only if one configuration can be reached from the other by moving one token along an edge of $G$ from its current vertex to an unoccupied vertex. These token moves are called admissible moves. Under this interpretation, if $A$ and $B$ are two distinct $k$ -subsets of $V(G)$ then a path in $F_{k}(G)$ with endvertices $A$ and $B$ corresponds to a finite sequence of token configurations that are produced by a corresponding sequence of admissible moves. With this in mind, now we explain how to produce some paths of $F_{k}(G)$ from a certain set of paths of $G$ .

Let $P:=a_{0}a_{1}a_{2}\ldots a_{m}$ be an $a-b$ path of $G$ ( $a_{0}=a$ and $a_{m}=b$ ); let $A,B\in V(F_{k}(G))$ be such that $A\triangle B=\{a,b\}$ , $P\cap A=\{a\}$ and $P\cap B=\{b\}$ . A natural way of constructing an $A-B$ path ${\mathcal{P}}$ in $F_{k}(G)$ using $P$ is by moving the token at $a$ along $P$ to $b$ . More precisely, we start at $A$ , then for each $i=0,1,\ldots,m-1$ , we move (in this order) the token at $a_{i}$ along the edge $a_{i}a_{i+1}$ to the vertex $a_{i+1}$ . We denote this sequence of admissible token moves by

a_{0}\longrightarrow a_{1}\longrightarrow a_{2}\cdots\longrightarrow a_{m}.

Clearly, the first and last configurations of this sequence correspond to the vertices $A$ and $B$ of $F_{k}(G)$ , respectively. Moreover, note that if $A_{0}=A,A_{m}=B$ , and $A_{i}=(A_{i-1}\setminus\{a_{i-1}\})\cup\{a_{i}\}$ for $i\in[m]$ , then ${\mathcal{P}}=AA_{1}A_{2}\ldots A_{m-1}B$ . We refer to ${\mathcal{P}}$ as the path of $F_{k}(G)$ induced by $P$ . See Figure 2. Let ${\mathcal{Q}}$ be a path of $F_{k}(G)$ and let $\{Q_{0},Q_{1},\ldots,Q_{m}\}$ be its vertex set. Since each of these $Q_{i}$ ’s is a $k$ -set of $V(G)$ , then $q:=k-|\cap_{i=0}^{m}Q_{i}|$ is well defined. We say that ${\mathcal{Q}}$ is a path of Type $q$ . Thus, ${\mathcal{P}}$ and any edge of $F_{k}(G)$ are examples of paths of Type 1.

We now define certain paths of Type 2. Let $e_{1}=a_{1}b_{1}$ and $e_{2}=a_{2}b_{2}$ be independent edges of $G$ , and let $A,B\in F_{k}(G)$ be such that $A\setminus B=\{a_{1},a_{2}\}$ and $B\setminus A=\{b_{1},b_{2}\}$ . A simple way to construct an $A-B$ path ${\mathcal{R}}$ of Type 2 (and length 2) is by moving the token at $a_{1}$ to $b_{1}$ along $e_{1}$ , and then, by moving the token at $a_{2}$ to $b_{2}$ along $e_{2}$ . We denote this construction by

a_{1}\longrightarrow b_{1};a_{2}\longrightarrow b_{2}.

Then ${\mathcal{R}}=A_{0}A_{1}A_{2}$ , where $A_{0}=A$ , $A_{1}=(A_{0}\setminus\{a_{1}\})\cup\{b_{1}\}$ , $A_{2}=(A_{1}\setminus\{a_{2}\})\cup\{b_{2}\}=B$ (see Figure 3). We remark that ${\mathcal{R}}$ can be seen as the concatenation of two paths of Type 1, namely those corresponding to $a_{1}\longrightarrow b_{1}$ and $a_{2}\longrightarrow b_{2}$ . As suggested above, we use a semicolon “ ; ” to denote the concatenation of paths of Type 1.

Now, suppose that $A$ and $B$ are adjacent vertices in $F_{k}(G)$ with $A\setminus B:=\{a\}$ and $B\setminus A:=\{b\}$ . Then $ab$ is an edge of $G$ . Let $u$ and $v$ be adjacent vertices of $G$ such that $u\in A\cap B$ and $v\in V(G)\setminus(A\cup B)$ . As we have seen above, a way to produce an $A-B$ path ${\mathcal{P}}$ is simply by moving the token at $a$ to $b$ along the edge $ab$ . Now we use a simple trick, involving the edges $uv$ and $ab$ , to produce a new $A-B$ path ${\mathcal{P}}_{uv}$ of $F_{k}(G)$ that is internally disjoint from ${\mathcal{P}}$ . The path ${\mathcal{P}}_{uv}$ is constructed as follows. First we move the token at $u$ to $v$ along $uv$ , and then we move the token at $a$ to $b$ along $ab$ , and finally we move back the token at $v$ to $u$ along $uv$ . Clearly, each of these moves is admissible and they together define the required ${\mathcal{P}}_{uv}$ path, which we denote by:

u\longrightarrow v;a\longrightarrow b;v\longrightarrow u.

We say that the vertex $v$ is playing the role of a distractor, which allow us to produce a new path $P_{uv}$ from ${\mathcal{P}}$ and $uv$ . See Figure 4.

We now generalize the above construction. Suppose that ${\mathcal{P}}$ is an $A-B$ path of $F_{k}(G)$ and that $uv$ is an edge of $G$ with $u\in A\cap B$ and $v\in V(G)\setminus(A\cup B)$ . If $u\in I$ and $v\notin I$ for any internal vertex $I$ of ${\mathcal{P}}$ , then we can get a new $A-B$ path $P_{uv}$ from ${\mathcal{P}}$ and $uv$ as follows. First move the token at $u$ to $v$ along $uv$ . Then, keeping the token at $v$ fixed, move the tokens from the vertices in $A\setminus B$ to the vertices in $B\setminus A$ according to ${\mathcal{P}}$ , and finally move back the token at the distractor $v$ to the initial vertex $u$ . Note that at the end we have produced an $A-B$ path ${\mathcal{P}}_{uv}$ with the following property: for each inner vertex $J$ of ${\mathcal{P}}_{uv}$ , we have that $v\in J$ and $u\notin J$ . This implies that if $u^{\prime}v^{\prime}$ is an edge of $G\setminus\{uv\}$ satisfying the same properties as $uv$ with respect to ${\mathcal{P}}$ , then the corresponding path ${\mathcal{P}}_{u^{\prime}v^{\prime}}$ is an $A-B$ path internally disjoint from both ${\mathcal{P}}$ and ${\mathcal{P}}_{uv}$ . The paths produced in this way play an important role in the proof of Theorem 1.

1.2 Some basic facts

In this section we prove auxiliary results that are used in the proof of Theorem 1.

Proposition 1.1.

Let $H$ be a connected graph. Then $H$ is $t$ -connected if and only if $H$ has $t$ pairwise internally disjoint $a-b$ paths, for any two vertices $a$ and $b$ of $H$ such that $d_{H}(a,b)=2$ .

Proof.

The forward implication follows directly from Menger’s Theorem. Conversely, let $U$ be a vertex cut of $H$ of minimum order. Let $H_{1}$ and $H_{2}$ be two distinct components of $H-U$ , and let $u\in U$ . Since $U$ is a minimum cut, then $u$ has at least a neighbour $v_{i}$ in $H_{i}$ , for $i=1,2$ . Then $d_{H}(v_{1},v_{2})=2$ . By hypothesis, $H$ has $t$ pairwise internally disjoint $v_{1}-v_{2}$ paths. Since each of these $t$ paths intersects $U$ , then we have that $|U|\geq t$ , as required. ∎

Proposition 1.2.

Let $X$ and $Y$ be vertices of $F_{k}(G)$ with $d_{F_{k}(G)}(X,Y)=2$ . Then the following hold:

1)

$|X\cap Y|=k-1$ or $|X\cap Y|=k-2$ ,
2)

If $|X\cap Y|=k-2$ , then $G$ has two independent edges $x_{1}y_{1}$ and $x_{2}y_{2}$ such that $X\setminus Y=\{x_{1},x_{2}\}$ and $Y\setminus X=\{y_{1},y_{2}\}$ .
3)

If $|X\cap Y|=k-1$ , then $G$ has two vertices $x$ and $y$ at distance two in $G$ such that $X\setminus Y=\{x\}$ and $Y\setminus X=\{y\}$ .

Proof.

1)

This is equivalent to showing that $|X\triangle Y|\in\{2,4\}$ . Since $X$ and $Y$ are distinct $k$ -sets of $V(G)$ , $|X\triangle Y|$ must be an even positive integer. If $|X\triangle Y|\geq 6$ , then we need to carry at least 3 tokens from the vertices in $X\setminus Y$ to the vertices in $Y\setminus X$ , and so $d_{F_{k}(G)}(X,Y)\geq 3$ . Hence $|X\triangle Y|\in\{2,4\}$ , as required. See Figure 5.
2)

Note that $|X\setminus Y|=|Y\setminus X|=2$ in this case. Since $d_{F_{k}(G)}(X,Y)=2$ , there is a way to carry the two tokens at the vertices of $X\setminus Y$ to the vertices of $Y\setminus X$ with exactly two admissible token moves. These two token moves corresponds to two independent edges joining vertices of $X\setminus Y$ with the vertices of $Y\setminus X$ . See Figure 5 ( $i$ ).
3)

In this case $X\setminus Y$ and $Y\setminus X$ each consists of exactly one vertex of $G$ ; say $x$ and $y$ , respectively. Since $d_{F_{k}(G)}(X,Y)=2$ , then $x$ cannot be adjacent to $y$ in $G$ . On the other hand, $d_{F_{k}(G)}(X,Y)=2$ implies the existence of an $X-Y$ path ${\mathcal{P}}$ produced by exactly 2 admissible token moves. Now note that ${\mathcal{P}}$ necessarily involves two admissible token moves $x\longrightarrow v$ and $u\longrightarrow y$ . There are two possibilities either $x\longrightarrow v$ is applied before $u\longrightarrow y$ or $u\longrightarrow y$ is applied before $x\longrightarrow v$ . Since ${\mathcal{P}}$ is produced by exactly 2 admissible token moves, we have that $u=v\in N_{G}(x)\cap N_{G}(y)$ , and $xvy$ is a path of length two in $G$ , as required. The two possibilities are depicted in ( $ii$ ) and ( $iii$ ) of Figure 5.

∎

Let $X$ be a vertex of $F_{k}(G)$ . From the definition of $F_{k}(G)$ it is not hard to see that the complementary map $\psi(X):=V(G)\setminus X$ defines an isomorphism between $F_{k}(G)$ and $F_{n-k}(G)$ . The next proposition follows from the definition of $\psi$ .

Proposition 1.3.

Let $\psi:F_{k}(G)\rightarrow F_{n-k}(G)$ be the complementary isomorphism, and let $X,Y,x,y$ and $v$ be as in the proof of Proposition 1.2 (3). Then exactly one of $v\notin X\cup Y$ or $v\notin\psi(X)\cup\psi(Y)$ holds.

Proof.

From Proposition 1.2 (3) we know that $\{x\}=X\setminus Y$ and $\{y\}=Y\setminus X$ . Since $P=xvy$ is a path of length 2, then we have that $v\notin\{x,y\}$ . These imply that exactly one of $v\in X\cap Y$ or $v\in V(G)\setminus(X\cup Y)$ holds. Since $v\in X\cap Y$ is equivalent to $v\notin\psi(X)\cup\psi(Y)$ , and $v\in V(G)\setminus(X\cup Y)$ is equivalent to $v\notin X\cup Y$ , we are done. ∎

2 Proof of Theorem 1

Throughout this section, $T$ is a tree of order $n\geq 2$ , and $k\in\{1,2,\ldots,n-1\}$ . It is sufficient to show that

\kappa(F_{k}(T))\geq\delta(F_{k}(T)).

From the definition of $F_{1}(G)$ it is straightforward to see that $G$ and $F_{1}(G)$ are isomorphic. In this case Theorem 1 holds. We assume that $n\geq 4$ and $k\in\{2,\ldots,n-2\}$ . By Proposition 1.1, it suffices to prove the following.

Lemma 2.1.

Let $X,Y\in V(F_{k}(T))$ with $d_{F_{k}(T)}(X,Y)=2$ . Then $F_{k}(T)$ has at least $\delta(F_{k}(T))$ pairwise internally disjoint $X-Y$ paths.

Proof.

For brevity of notation, let $XY:=X\cap Y$ , $\overline{XY}:=V(T)\setminus(X\cup Y),$ and $\delta:=\delta(F_{k}(T))$ . We remark that here $XY$ and $\overline{XY}$ are subsets of $V(T)$ , but not edges of $F_{k}(T)$ or $F_{n-k}(T)$ .

Informally, the general strategy to show Lemma 2.1 is as follows.

•

Step 1. First, we construct a certain number $m$ of pairwise internally disjoint $X-Y$ paths in $F_{k}(T)$ .
•

Step 2. If $\delta>m$ , we construct the $\delta-m$ missing $X-Y$ paths.

The hypothesis $d(X,Y)=2$ and Proposition 1.2 (1) imply that $|XY|=k-1$ or $|XY|=k-2$ . We analyze these cases separately.

2.1 Case 1: $|XY|=k-1$

From Proposition 1.2 (3) we know that there exist $x,y,v\in V(T)$ such that $\{x\}=X\setminus Y,\{y\}=Y\setminus X,v\notin\{x,y\}$ , and $P=xvy$ is a shortest $x-y$ path of $T$ . In view of Proposition 1.3, we can assume without any loss of generality that $v\notin X\cup Y$ . Indeed, if $v\in X\cup Y$ then by Proposition 1.3 $v\notin\psi(X)\cup\psi(Y)$ . Since $F_{k}(T)$ and $F_{n-k}(T)$ are isomorphic under $\psi(U)=V(T)\setminus U$ , then we can work with $\psi(X)$ and $\psi(Y)$ in $F_{n-k}(T)$ instead of $X$ and $Y$ in $F_{k}(T)$ . We assume that $X$ and $Y$ are as in Figure 5 ( $ii$ ). Let $\overline{XY}^{\prime}:=\overline{XY}\setminus\{v\}$ and let

	$\displaystyle\overline{XY}(x)$	$\displaystyle:=\{w\in\overline{XY}^{\prime}:\text{$w$ is adjacent to $x$}\}=\{w_{x}^{1},\ldots,w_{x}^{a}\},$
	$\displaystyle\overline{XY}(y)$	$\displaystyle:=\{w\in\overline{XY}^{\prime}:\text{$w$ is adjacent to $y$}\}=\{w_{y}^{1},\ldots,w_{y}^{d}\},$
	$\displaystyle XY(x)$	$\displaystyle:=\{z\in XY:\text{$z$ is adjacent to $x$}\}=\{z_{x}^{1},\ldots,z_{x}^{c}\},$
	$\displaystyle XY(y)$	$\displaystyle:=\{z\in XY:\text{$z$ is adjacent to $y$}\}=\{z_{y}^{1},\ldots,z_{y}^{b}\},$

where $a:=|\overline{XY}(x)|$ , $b:=|XY(y)|$ , $c:=|XY(x)|$ , and $d:=|\overline{XY}(y)|$ . See Figure 6.

Let us define

E_{XY,\overline{XY}}:=\{zw\in E(T):z\in XY\text{ and }w\in\overline{XY}\},\text{ and }\eta:=|E_{XY,\overline{XY}}|.

Since $T$ is a tree, then $\overline{XY}(x),\overline{XY}(y),XY(x),$ and $XY(y)$ are pairwise disjoint. Then, in $F_{k}(T)$ , $deg(X)=a+b+\eta+1$ and $deg(Y)=c+d+\eta+1.$ Without loss of generality we may assume that $deg(X)\leq deg(Y)$ . Hence, $a+b\leq c+d$ .

Let $m_{x}:=\min\{a,c\}$ , $m_{y}:=\min\{b,d\}$ , and $m:=m_{x}+m_{y}+\eta+1.$

2.1.1 Step 1 of Case 1

We produce the required $m$ $X-Y$ paths by means of four types of constructions.

1.

Using the vertex $v$ :

${\mathcal{P}}_{0}:=x\longrightarrow v\longrightarrow y.$

Let $\mathbb{T}_{1}:=\{{\mathcal{P}}_{0}\}$ . Note that if $A_{0}$ is the (unique) inner vertex of ${\mathcal{P}}_{0}$ , then

(C1)

$A_{0}\cap XY=XY$ and $A_{0}\cap\overline{XY}^{\prime}=\emptyset$ .

Using the edges of $E_{XY,\overline{XY}}$ . For each $z_{i}w_{j}\in E_{XY,\overline{XY}}$ , let ${\mathcal{P}}_{i,j}$ be the $X-Y$ path defined as follows:

{\mathcal{P}}_{i,j}:=\begin{cases}z_{i}\rightarrow w_{j};x\rightarrow v\rightarrow y;w_{j}\rightarrow z_{i}&\text{if $w_{j}\neq v$;}\\ z_{i}\rightarrow v\rightarrow y;x\rightarrow v\rightarrow z_{i}&\text{if $w_{j}=v$.}\end{cases}

Let $\mathbb{T}_{2}:=\{{\mathcal{P}}_{i,j}:z_{i}w_{j}\in E_{XY,\overline{XY}}\}$ . Note that if $A_{i,j}$ is an inner vertex of ${\mathcal{P}}_{i,j}$ , then

(C2): $A_{i,j}\cap XY=XY\setminus\{z_{i}\}$ .

Moreover, depending on whether $w_{j}\neq v$ or $w_{j}=v$ , then $A_{i,j}$ also satisfies the following:

(C2.1): If $w_{j}\neq v$ , then $A_{i,j}\cap\overline{XY}^{\prime}=\{w_{j}\}$ .
(C2.2): If $w_{j}=v$ , then $A_{i,j}\cap\overline{XY}^{\prime}=\emptyset$ .

We recall that if $r=0$ , then $[r]=\emptyset$ .

3.

Using the vertices $w_{x}^{i}\in\overline{XY}(x)$ and $z_{x}^{i}\in XY(x)$ . For each $i\in[m_{x}]$ , we define the path ${\mathcal{P}}_{i}$ as follows:

${\mathcal{P}}_{i}:=x\rightarrow w_{x}^{i};z_{x}^{i}\rightarrow x\rightarrow v\rightarrow y;w_{x}^{i}\rightarrow x\rightarrow z_{x}^{i}.$

Let $\mathbb{T}_{3}:=\{{\mathcal{P}}_{i}:i\in[m_{x}]\}$ . Again, note that if $A_{i}$ is an inner vertex of ${\mathcal{P}}_{i}$ , then

(C3)

Either $A_{i}\cap XY=XY$ or $A_{i}\cap XY=XY\setminus\{z_{x}^{i}\}$ , and either $A_{i}\cap\overline{XY}^{\prime}=\emptyset$ or $A_{i}\cap\overline{XY}^{\prime}=\{w_{x}^{i}\}$ , and at least one of the following holds: $A_{i}\cap XY=XY\setminus\{z_{x}^{i}\}$ or $A_{i}\cap\overline{XY}^{\prime}=\{w_{x}^{i}\}$ .
4.

Using the vertices $w_{y}^{j}\in\overline{XY}(y)$ and $z_{y}^{j}\in XY(y)$ . For each $j\in[m_{y}]$ , we define the path ${\mathcal{Q}}_{j}$ as follows:

${\mathcal{Q}}_{j}:=z_{y}^{j}\rightarrow y\rightarrow w_{y}^{j};x\rightarrow v\rightarrow y\rightarrow z_{y}^{j};w_{y}^{j}\rightarrow y.$

Let $\mathbb{T}_{4}:=\{{\mathcal{Q}}_{j}:j\in[m_{y}]\}$ . Again, note that if $A_{j}$ is an inner vertex of ${\mathcal{Q}}_{j}$ , then

(C4)

Either $A_{j}\cap XY=XY$ or $A_{j}\cap XY=XY\setminus\{z_{y}^{j}\}$ , and either $A_{j}\cap\overline{XY}^{\prime}=\emptyset$ or $A_{j}\cap\overline{XY}^{\prime}=\{w_{y}^{j}\}$ , and at least one of the following holds: $A_{j}\cap XY=XY\setminus\{z_{y}^{j}\}$ or $A_{j}\cap\overline{XY}^{\prime}=\{w_{y}^{j}\}$ .

Let us define $\mathbb{T}:=\mathbb{T}_{1}\cup\mathbb{T}_{2}\cup\mathbb{T}_{3}\cup\mathbb{T}_{4}.$ Since $|\mathbb{T}_{1}|=1,|\mathbb{T}_{2}|=\eta,|\mathbb{T}_{3}|=m_{x},|\mathbb{T}_{4}|=m_{y}$ , and $m=1+\eta+m_{x}+m_{y}$ , then in order to finish the Step 1 of Case 1, it is enough to show that the paths in $\mathbb{T}$ are pairwise internally disjoint.

Claim 2.2.

The $X-Y$ paths in $\mathbb{T}$ are pairwise internally disjoint.

Proof of Claim 2.2:First we show separately that the paths in $\mathbb{T}_{\ell}$ are pairwise internally disjoint for $\ell\in\{2,3,4\}$ .

Suppose that $\boldsymbol{\ell=2}$ , and let ${\mathcal{P}}_{i,j}$ and ${\mathcal{P}}_{s,t}$ be distinct paths in $\mathbb{T}_{2}$ . Let $A_{i,j}$ and $A_{s,t}$ be inner vertices of ${\mathcal{P}}_{i,j}$ and ${\mathcal{P}}_{s,t}$ , respectively. Since $(i,j)\neq(s,t)$ , then $z_{i}\neq z_{s}$ or $w_{j}\neq w_{t}$ .

If $z_{i}\neq z_{s}$ , then from (C2) we know that $A_{i,j}\cap XY=XY\setminus\{z_{i}\}$ and $A_{s,t}\cap XY=XY\setminus\{z_{s}\}$ . Hence $z_{i}\in A_{s,t}\setminus A_{i,j}$ , which implies that $A_{i,j}\neq A_{s,t}$ .

Now suppose that $w_{j}\neq w_{t}$ . First suppose that $v\notin\{w_{j},w_{t}\}$ . By (C2.1) we have $A_{i,j}\cap\overline{XY}^{\prime}=\{w_{j}\}$ , and similarly, $A_{s,t}\cap\overline{XY}^{\prime}=\{w_{t}\}$ . Then, $A_{i,j}\cap\overline{XY}^{\prime}\neq A_{s,t}\cap\overline{XY}^{\prime}$ and so $A_{i,j}\neq A_{s,t}$ . Then we may assume that $v\in\{w_{j},w_{t}\}$ . Without loss of generality suppose that $w_{j}=v$ . We know by (C2.2) that $A_{i,j}\cap\overline{XY}^{\prime}=\emptyset$ , and by (C2.1) that $A_{s,t}\cap\overline{XY}^{\prime}=\{w_{t}\}$ , these two facts imply that $A_{i,j}\neq A_{s,t}$ .

Suppose that $\boldsymbol{\ell=3}$ , and let ${\mathcal{P}}_{s}$ and ${\mathcal{P}}_{t}$ be distinct paths in $\mathbb{T}_{3}$ . For $r\in\{s,t\}$ , let $A_{r}$ be an inner vertex of ${\mathcal{P}}_{r}$ . From the last assertion of (C3) we know that $A_{s}\cap\overline{XY}^{\prime}=\{w_{x}^{s}\}$ or $A_{s}\cap XY=XY\setminus\{z_{x}^{s}\}$ . Suppose that $A_{s}\cap\overline{XY}^{\prime}=\{w_{x}^{s}\}$ . Since (C3) implies that $A_{t}\cap\overline{XY}^{\prime}=\emptyset$ or $A_{t}\cap\overline{XY}^{\prime}=\{w_{x}^{t}\}$ , then we have $A_{s}\cap\overline{XY}^{\prime}\neq A_{t}\cap\overline{XY}^{\prime}$ , and so $A_{s}\neq A_{t}$ . Now suppose that $A_{s}\cap XY=XY\setminus\{z_{x}^{s}\}$ . Again, from (C3) we know that $A_{t}\cap XY=XY$ or $A_{t}\cap XY=XY\setminus\{z_{x}^{t}\}$ . Since $z_{x}^{s}\neq z_{x}^{t}$ , then $A_{s}\cap XY\neq A_{t}\cap XY$ , and so $A_{s}\neq A_{t}$ .

Suppose that $\boldsymbol{\ell=4}$ . This case can be handled in a totally analogous manner as previous case.

Let $A_{0},A_{i,j},A_{s}$ , and $A_{t}$ be inner vertices of ${\mathcal{P}}_{0}\in\mathbb{T}_{1}$ , ${\mathcal{P}}_{i,j}\in\mathbb{T}_{2}$ , ${\mathcal{P}}_{s}\in\mathbb{T}_{3}$ , and ${\mathcal{Q}}_{t}\in\mathbb{T}_{4}$ , respectively. It remains to show that ${\mathcal{P}}_{0},{\mathcal{P}}_{i,j},{\mathcal{P}}_{s}$ , and ${\mathcal{Q}}_{t}$ are pairwise internally disjoint. We analyze separately each pair.

${\{A_{0},A_{i,j}\}}$ :: Here we have $A_{0}\cap XY=XY$ , while $A_{i,j}\cap XY=XY\setminus\{z_{i}\}$ , and so $A_{0}\neq A_{i,j}$ .
${\{A_{0},A_{s}\}}$ :: By (C1) we know that $A_{0}\cap XY=XY$ and that $A_{0}\cap\overline{XY}^{\prime}=\emptyset$ . Similarly, by the last assertion of (C3), we know that either $A_{s}\cap XY=XY\setminus\{z_{x}^{s}\}$ or $A_{s}\cap\overline{XY}^{\prime}=\{w_{x}^{s}\}$ , then we have $A_{0}\neq A_{s}$ .
${\{A_{0},A_{t}\}}$ :: As in previous case, the last assertion of (C4) implies that either $A_{t}\cap XY=XY\setminus\{z_{y}^{t}\}$ or $A_{t}\cap\overline{XY}^{\prime}=\{w_{y}^{t}\}$ . Then, since $A_{0}\cap XY=XY$ and $A_{0}\cap\overline{XY}^{\prime}=\emptyset$ , we have $A_{0}\neq A_{t}$ .
${\{A_{i,j},A_{s}\}}$ :: First suppose that $w_{j}=v$ . Then $z_{i}\neq z_{x}^{s}$ , as otherwise the vertex set $\{x,z_{i},v\}$ forms a cycle, contradicting that $T$ is a tree. Since $A_{i,j}\cap XY=XY\setminus\{z_{i}\}$ , and either $A_{s}\cap XY=XY$ or $A_{s}\cap XY=XY\setminus\{z_{x}^{s}\}$ , then $A_{i,j}\cap XY\neq A_{s}\cap XY$ , as required.

Suppose now that $w_{j}\neq v$ . By (C3) we know that $A_{s}\cap XY=XY$ or $A_{s}\cap XY=XY\setminus\{z_{x}^{s}\}$ . If $A_{s}\cap XY=XY$ , then $A_{i,j}\cap XY=XY\setminus\{z_{i}\}$ implies that $A_{s}\neq A_{i,j}$ . Thus we may assume that $A_{s}\cap XY=XY\setminus\{z_{x}^{s}\}$ . If $z_{i}\neq z_{x}^{s}$ , then $XY\setminus\{z_{x}^{s}\}=A_{s}\cap XY\neq A_{i,j}\cap XY=XY\setminus\{z_{i}\}$ , as desired. Then we can assume that $z_{x}^{s}=z_{i}$ . This implies that $w_{x}^{s}\neq w_{j}$ , as otherwise $\{z_{i},x,w_{j}\}$ forms a cycle. By (C2.1) we know that $A_{i,j}\cap\overline{XY}^{\prime}=\{w_{j}\}$ , and by (C3) we have that either $A_{s}\cap\overline{XY}^{\prime}=\emptyset$ or $A_{s}\cap\overline{XY}^{\prime}=\{w_{x}^{s}\}$ . Since $w_{x}^{s}\neq w_{j}$ , then $A_{i,j}\cap\overline{XY}^{\prime}\neq A_{s}\cap\overline{XY}^{\prime}$ , as required.
${\{A_{i,j},A_{t}\}}$ :: Again, this case can be handled in a totally analogous manner as previous case.
${\{A_{s},A_{t}\}}$ :: Since $XY(x),XY(y),\overline{XY}(x)$ , and $\overline{XY}(y)$ are pairwise disjoint, then $z_{x}^{s}\neq z_{y}^{t}$ and $w_{x}^{s}\neq w_{y}^{t}$ . From these inequalities and (C3)-(C4) we have that either $A_{s}\cap XY\neq A_{t}\cap XY$ or $A_{s}\cap\overline{XY}^{\prime}\neq A_{t}\cap\overline{XY}^{\prime}$ , and so $A_{s}\neq A_{t}$ .

This completes the proof of Claim 2.2. $\triangle$

2.1.2 Step 2 of Case 1

We start by showing that $\delta-m\leq 2$ .

Claim 2.3.

Let $\delta,m,m_{x},m_{y},$ and $\eta$ be as above. Then,

\delta\leq\begin{cases}m_{x}+m_{y}+\eta+1=m&\text{if $a\leq c$ and $b\leq d$, or $a>c$,}\\ m_{x}+m_{y}+\eta+2=m+1&\text{if $b=d+1$,}\\ m_{x}+m_{y}+\eta+3=m+2&\text{if $b\geq d+2$.}\end{cases}

Proof of Claim 2.3: First we note that if $a\leq c$ and $b\leq d$ , then

\delta\leq deg(X)=a+b+\eta+1=m_{x}+m_{y}+\eta+1=m,

as claimed.

Suppose that $a>c$ . Since $a+b\leq c+d$ , then $b<d$ . Let $U:=\overline{XY}\cup\{x,y\}$ . Since $T[U]$ is a forest, then it contains at least a vertex $u\in U\setminus\{v\}$ such that $deg_{T[U]}(u)\leq 1$ . Note that $u\notin\{x,y\}$ , because $deg_{T[U]}(x)=a+1\geq 2$ and $deg_{T[U]}(y)=d+1\geq 2$ . Let $X^{\prime}:=(X\setminus\{x\})\cup\{u\}$ , so

\delta\leq deg(X^{\prime})\leq b+c+\eta+deg_{T[U]}(u)\leq m_{x}+m_{y}+\eta+1=m,

as claimed.

Suppose that $b=d+1$ . Since $a+b\leq c+d$ , then $a<c$ . In this case we have that

\delta\leq deg(X)=a+b+\eta+1=a+(d+1)+\eta+1=m_{x}+m_{y}+\eta+2=m+1.

Finally, suppose that $b\geq d+2$ . Since $a+b\leq c+d$ , then $c\geq a+2$ . Let $U:=X\cup Y$ . Since $T[U]$ is a forest, then it contains at least a vertex $u\in U$ such that $deg_{T[U]}(u)\leq 1$ . Note that $u\notin\{x,y\}$ , because $deg_{T[U]}(x)\geq c\geq 2$ and $deg_{T[U]}(y)\geq b\geq 2$ . Let $X^{\prime}=(X\setminus\{u\})\cup\{y\}$ , then

\delta\leq deg(X^{\prime})\leq(a+1)+(d+1)+\eta+deg_{T[U]}(u)\leq m_{x}+m_{y}+\eta+3=m+2.

This completes the proof of Claim 2.3. $\triangle$

Claim 2.3 shows that almost all $X-Y$ paths claimed by Lemma 2.1 are provided by $\mathbb{T}$ , when $|XY|=k-1$ . We finish the proof of Case 1 with the construction of the remaining $\delta-m$ $X-Y$ paths.

Claim 2.4.

If $|XY|=k-1$ , then $F_{k}(T)$ has at least $\delta$ $X-Y$ pairwise internally disjoint paths.

Proof of Claim 2.4: We have already constructed $m$ $X-Y$ pairwise internally disjoint paths, namely the elements of $\mathbb{T}$ . Then, it remains to show the existence of $\delta-m$ additional $X-Y$ paths with similar properties. Since if $\delta\leq m$ then there is nothing to prove, we assume that $\delta>m$ . From this and Claim 2.3 it follows that $b\geq d+1$ . Moreover, since $a+b\leq c+d$ , then $c\geq a+1$ . Hence, $a=\min\{a,c\}$ and $d=\min\{b,d\}$ .

Suppose first that $b=d+1$ . By Claim 2.3 we have that $\delta\leq m+1$ . Thus, it is enough to construct a new $X-Y$ path internally disjoint to each path in $\mathbb{T}$ . Since $b=d+1>d=\min\{b,d\}$ and $c\geq a+1>a=\min\{a,c\}$ , then the vertices $z_{y}^{b}$ and $z_{x}^{c}$ were not used in the construction of the paths of $\mathbb{T}_{3}\cup\mathbb{T}_{4}$ . We construct the required path ${\mathcal{P}}$ as follows:

{\mathcal{P}}:=z_{y}^{b}\longrightarrow y;x\longrightarrow v;z_{x}^{c}\longrightarrow x;y\longrightarrow z_{y}^{b};v\longrightarrow y;x\longrightarrow z_{x}^{c}.

Let $A$ be an inner vertex of ${\mathcal{P}}$ . From the definition of ${\mathcal{P}}$ it follows that

(C5): Either $A\cap XY=XY\setminus\{z_{y}^{b}\}$ or $A\cap XY=XY\setminus\{z_{x}^{c}\}$ or $A\cap XY=XY\setminus\{z_{x}^{b},z_{y}^{c}\}$ , and that $A\cap\overline{XY}^{\prime}=\emptyset$ .

Now we show that ${\mathcal{P}}$ is internally disjoint to any path in $\mathbb{T}$ . Let $A_{0},A_{i,j},A_{s}$ , and $A_{t}$ be inner vertices of ${\mathcal{P}}_{0}\in\mathbb{T}_{1}$ , ${\mathcal{P}}_{i,j}\in\mathbb{T}_{2}$ , ${\mathcal{P}}_{s}\in\mathbb{T}_{3}$ , and ${\mathcal{Q}}_{t}\in\mathbb{T}_{4}$ , respectively.

We analyze these cases separately.

${\{A_{0},A\}}$ :: By (C1) and (C5) we know that $A_{0}\cap XY=XY$ and $A\cap XY\neq XY$ , respectively, and so $A\neq A_{0}$ .
${\{A_{i,j},A\}}$ :: If $w_{j}\neq v$ , then $A_{i,j}\cap\overline{XY}^{\prime}=\{w_{j}\}$ , and then $A\cap\overline{XY}^{\prime}\neq A_{i,j}\cap\overline{XY}^{\prime}$ , which implies that $A\neq A_{i,j}$ .
Now suppose that $w_{j}=v$ . Then $z_{i}\notin\{z_{y}^{b},z_{x}^{c}\}$ , as otherwise $T$ has a cycle. Then, by (C2) and (C5) we have that $A_{i,j}\cap XY\neq A\cap XY$ , and so $A\neq A_{i,j}$ .
${\{A_{s},A\}}$ :: Note that $z_{x}^{s}\neq z_{x}^{c}$ , because $s\leq a<c$ . Similarly, $z_{x}^{s}\neq z_{y}^{b}$ , because $XY(x)\cap XY(y)=\emptyset$ . Then, (C3) and (C5) implies that $A_{s}\cap XY\neq A\cap XY$ , and so $A\neq A_{s}$ .
${\{A_{t},A\}}$ :: We proceed as in previous case. Since $t\leq d<b$ , then $z_{y}^{t}\neq z_{y}^{b}$ , and $z_{y}^{t}\neq z_{x}^{c}$ because $XY(x)\cap XY(y)=\emptyset$ . Then, (C4) and (C5) implies that $A_{t}\cap XY\neq A\cap XY$ , and so $A\neq A_{t}$ .

Finally, suppose that $b\geq d+2$ . By Claim 2.3 we have that $\delta\leq m+2$ . Thus, it is enough to construct two $X-Y$ paths, say ${\mathcal{P}}$ and ${\mathcal{P}}^{\prime}$ , such that $\{{\mathcal{P}},{\mathcal{P}}^{\prime}\}\cup\mathbb{T}$ is a set of pairwise internally disjoint paths.

Since $b\geq d+2$ and $a+b\leq c+d$ , then $c\geq a+2$ . Now we use $z_{y}^{b},z_{y}^{b-1},z_{x}^{c}$ , and $z_{x}^{c-1}$ to construct ${\mathcal{P}}$ and ${\mathcal{P}}^{\prime}$ as follows.

{\mathcal{P}}:=z_{y}^{b}\rightarrow y;x\rightarrow v;z_{x}^{c}\rightarrow x;y\rightarrow z_{y}^{b};v\rightarrow y;x\rightarrow z_{x}^{c},\text{ and }

{\mathcal{P}}^{\prime}:=z_{y}^{b-1}\rightarrow y;x\rightarrow v;z_{x}^{c-1}\rightarrow x;y\rightarrow z_{y}^{b-1};v\rightarrow y;x\rightarrow z_{x}^{c-1}.

Note that a similar argument to the one used above (for the case $b=d+1$ ) can be applied to show that ${\mathcal{P}}$ and ${\mathcal{P}}^{\prime}$ are internally disjoint of each path in $\mathbb{T}$ . Hence all that remains to be checked is that ${\mathcal{P}}$ and ${\mathcal{P}}^{\prime}$ are internally disjoint.

Let $A$ and $A^{\prime}$ be inner vertices of ${\mathcal{P}}$ and ${\mathcal{P}}^{\prime}$ , respectively. From the definition of ${\mathcal{P}}$ (respectively, ${\mathcal{P}}^{\prime}$ ) we know that either $A\cap XY=XY\setminus\{z_{y}^{b}\}$ , $A\cap XY=XY\setminus\{z_{x}^{c}\}$ , or $A\cap XY=XY\setminus\{z_{y}^{b},z_{x}^{c}\}$ (respectively, $A^{\prime}\cap XY=XY\setminus\{z_{y}^{b-1}\}$ , $A^{\prime}\cap XY=XY\setminus\{z_{x}^{c-1}\}$ , or $A^{\prime}\cap XY=XY\setminus\{z_{y}^{b-1},z_{x}^{c-1}\}$ ). Since $\{z_{y}^{b},z_{x}^{c}\}\cap\{z_{y}^{b-1},z_{x}^{c-1}\}=\emptyset$ , then in all the arising cases, we always have $A\neq A^{\prime}$ , as required. This completes the proof of Claim 2.4, and hence the proof of Case 1. $\triangle$

2.2 Case 2: $|XY|=k-2$

From Proposition 1.2 (2) we know that $T$ has two independent edges $x_{1}y_{1}$ and $x_{2}y_{2}$ such that $X\setminus Y=\{x_{1},x_{2}\}$ and $Y\setminus X=\{y_{1},y_{2}\}$ . Then, we can assume that $X$ and $Y$ are as in Figure 5 ( $i$ ). Similarly as in Case 1, for $i\in\{1,2\}$ , let us define

	$\displaystyle\overline{XY}(x_{i})$	$\displaystyle:=\{w\in\overline{XY}:w\text{ is adjacent to }x_{i}\}=\{w_{x_{i}}^{1},\ldots,w_{x_{i}}^{a_{i}}\},$
	$\displaystyle\overline{XY}(y_{i})$	$\displaystyle:=\{w\in\overline{XY}:w\text{ is adjacent to }y_{i}\}=\{w_{y_{i}}^{1},\ldots,w_{y_{i}}^{d_{i}}\},$
	$\displaystyle XY(x_{i})$	$\displaystyle:=\{z\in XY:z\text{ is adjacent to }x_{i}\}=\{z_{x_{i}}^{1},\ldots,z_{x_{i}}^{c_{i}}\},$
	$\displaystyle XY(y_{i})$	$\displaystyle:=\{z\in XY:z\text{ is adjacent to }y_{i}\}=\{z_{y_{i}}^{1},\ldots,z_{y_{i}}^{b_{i}}\},$

where $a_{i}:=|\overline{XY}(x_{i})|$ , $b_{i}:=|XY(y_{i})|$ , $c_{i}:=|XY(x_{i})|$ , and $d_{i}:=|\overline{XY}(y_{i})|$ .

The next observation follows easily from the involved definitions and the fact that $T$ is a tree.

Observation 2.5.

Let $i\in\{1,2\}$ . Then $\overline{XY}(x_{i})\cap\overline{XY}(y_{i})=\emptyset$ and $XY(x_{i})\cap XY(y_{i})=\emptyset$ , and at most one of the following occurs: $|\overline{XY}(x_{1})\cap\overline{XY}(x_{2})|=1$ , $|\overline{XY}(y_{1})\cap\overline{XY}(y_{2})|=1$ , $|XY(x_{1})\cap XY(x_{2})|=1$ , or $|XY(y_{1})\cap XY(y_{2})|=1$ .

Let us define

E_{XY,\overline{XY}}:=\{z_{i}w_{j}\in E(G):z_{i}\in XY\text{ and }w_{j}\in\overline{XY}\},\text{ and let }\eta:=|E_{XY,\overline{XY}}|.

Then

deg(X)=\begin{cases}a_{1}+a_{2}+b_{1}+b_{2}+\eta+2&\text{ if $x_{1}y_{2}\notin E(T)$ and $x_{2}y_{1}\notin E(T)$,}\\ a_{1}+a_{2}+b_{1}+b_{2}+\eta+3&\text{ otherwise. }\end{cases}

and,

deg(Y)=\begin{cases}c_{1}+c_{2}+d_{1}+d_{2}+\eta+2&\text{ if $x_{1}y_{2}\notin E(T)$ and $x_{2}y_{1}\notin E(T)$, }\\ c_{1}+c_{2}+d_{1}+d_{2}+\eta+3&\text{ otherwise. }\end{cases}

Note that the term “+3” in $deg(X)$ and $deg(Y)$ means that $T$ has 3 edges with an end in $\{x_{1},x_{2}\}$ and the other end in $\{y_{1},y_{2}\}$ . Then it is impossible to have $deg(X)=a_{1}+a_{2}+b_{1}+b_{2}+\eta+2$ and $deg(Y)=c_{1}+c_{2}+d_{1}+d_{2}+\eta+3$ simultaneously. Similarly, $deg(X)=a_{1}+a_{2}+b_{1}+b_{2}+\eta+3$ and $deg(Y)=c_{1}+c_{2}+d_{1}+d_{2}+\eta+2$ cannot occur simultaneously.

Without loss of generality we assume that $deg(X)\leq deg(Y)$ . This assumption together with the assertions of the previous paragraph imply that $a_{1}+a_{2}+b_{1}+b_{2}\leq c_{1}+c_{2}+d_{1}+d_{2}$ . For $i\in\{1,2\}$ , let $m_{x_{i}}:=\min\{a_{i},c_{i}\},m_{y_{i}}:=\min\{b_{i},d_{i}\},$ and $m:=m_{x_{1}}+m_{x_{2}}+m_{y_{1}}+m_{y_{2}}+\eta+2.$

2.2.1 Step 1 of Case 2

We proceed similarly as in Case 1. In particular, we often use slight adaptation of many arguments given in Case 1. We start by producing $m$ $X-Y$ paths by means of six types of constructions.

1.

Let us define ${\mathcal{P}}_{x_{1}}$ and ${\mathcal{P}}_{x_{2}}$ as follows:

${\mathcal{P}}_{x_{1}}:=x_{1}\rightarrow y_{1};x_{2}\rightarrow y_{2}$

${\mathcal{P}}_{x_{2}}:=x_{2}\rightarrow y_{2};x_{1}\rightarrow y_{1}.$

Let ${\mathbb{L}}_{1}:=\{{\mathcal{P}}_{x_{1}},{\mathcal{P}}_{x_{2}}\}$ . Let ${\mathcal{P}}\in{\mathbb{L}}_{1}$ , and let $A$ be an inner vertex of ${\mathcal{P}}$ . Then

(D1)

$A\cap XY=XY$ and $A\cap\overline{XY}=\emptyset$ .
2.

For each edge $z_{i}w_{j}\in E_{XY,\overline{XY}}$ , let

${\mathcal{P}}_{i,j}:=z_{i}\rightarrow w_{j};x_{1}\rightarrow y_{1};x_{2}\rightarrow y_{2};w_{j}\rightarrow z_{i}.$

Let ${\mathbb{L}}_{2}:=\{{\mathcal{P}}_{i,j}:z_{i}w_{j}\in E_{XY,\overline{XY}}\}.$ Let ${\mathcal{P}}_{i,j}\in{\mathbb{L}}_{2}$ , and let $A_{i,j}$ be an inner vertex of ${\mathcal{P}}_{i,j}$ . Then

(D2)

$A_{i,j}\cap XY=XY\setminus\{z_{i}\}$ and $A_{i,j}\cap\overline{XY}=\{w_{j}\}$ .

For each $i\in[m_{x_{1}}]$ , we define the path ${\mathcal{P}}_{i}$ as follows:

{\mathcal{P}}_{i}:=x_{1}\longrightarrow w_{x_{1}}^{i};z_{x_{1}}^{i}\longrightarrow x_{1}\longrightarrow y_{1};x_{2}\longrightarrow y_{2};w_{x_{1}}^{i}\longrightarrow x_{1}\longrightarrow z_{x_{1}}^{i}.

Let ${\mathbb{L}}_{3}:=\{{\mathcal{P}}_{i}:i\in[m_{x_{1}}]\}$ . Let ${\mathcal{P}}_{i}\in{\mathbb{L}}_{3}$ , and let $A_{i}$ be an inner vertex of ${\mathcal{P}}_{i}$ . Then

(D3): Either $A_{i}\cap XY=XY$ or $A_{i}\cap XY=XY\setminus\{z_{x_{1}}^{i}\}$ , and either $A_{i}\cap\overline{XY}=\emptyset$ or $A_{i}\cap\overline{XY}=\{w_{x_{1}}^{i}\}$ , and at least one of the following holds: $A_{i}\cap\overline{XY}=\{w_{x_{1}}^{i}\}$ or $A_{i}\cap XY=XY\setminus\{z_{x_{1}}^{i}\}$ .

For each $j\in[m_{y_{1}}]$ , we define the path ${\mathcal{Q}}_{j}$ as follows:

{\mathcal{Q}}_{j}:=z_{y_{1}}^{j}\longrightarrow y_{1}\longrightarrow w_{y_{1}}^{j};x_{2}\longrightarrow y_{2};x_{1}\longrightarrow y_{1}\longrightarrow z_{y_{1}}^{j};w_{y_{1}}^{j}\longrightarrow y_{1}.

Let ${\mathbb{L}}_{4}:=\{{\mathcal{Q}}_{j}:j\in[m_{y_{1}}]\}$ . Let ${\mathcal{Q}}_{j}\in{\mathbb{L}}_{4}$ , and let $A_{j}$ be an inner vertex of ${\mathcal{Q}}_{j}$ . Then

(D4): Either $A_{j}\cap XY=XY\setminus\{z_{y_{1}}^{j}\}$ or $A_{j}\cap XY=XY$ , and either $A_{j}\cap\overline{XY}=\emptyset$ or $A_{j}\cap\overline{XY}=\{w_{y_{1}}^{j}\}$ , and at least one of the following holds: $A_{j}\cap XY=XY\setminus\{z_{y_{1}}^{j}\}$ or $A_{j}\cap\overline{XY}=\{w_{y_{1}}^{j}\}$ .

For each $i\in[m_{x_{2}}]$ , we define ${\mathcal{P}}^{*}_{i}$ as follows:

{\mathcal{P}}^{*}_{i}:=x_{2}\longrightarrow w_{x_{2}}^{i};z_{x_{2}}^{i}\longrightarrow x_{2}\longrightarrow y_{2};x_{1}\longrightarrow y_{1};w_{x_{2}}^{i}\longrightarrow x_{2}\longrightarrow z_{x_{2}}^{i}.

Let ${\mathbb{L}}^{*}_{3}:=\{{\mathcal{P}}^{*}_{i}:i\in[m_{x_{2}}]\}$ . Let ${\mathcal{P}}^{*}_{i}\in{\mathbb{L}}_{3}^{*}$ , and let $A^{*}_{i}$ be an inner vertex of ${\mathcal{P}}^{*}_{i}$ . Then

(D3*): Either $A^{*}_{i}\cap XY=XY$ or $A_{i}^{*}\cap XY=XY\setminus\{z_{x_{2}}^{i}\}$ , and either $A_{i}^{*}\cap\overline{XY}=\emptyset$ or $A_{i}^{*}\cap\overline{XY}=\{w_{x_{2}}^{i}\}$ , and at least one of the following holds: $A_{i}^{*}\cap\overline{XY}=\{w_{x_{2}}^{i}\}$ or $A_{i}^{*}\cap XY=XY\setminus\{z_{x_{2}}^{i}\}$ .

For each $j\in[m_{y_{2}}]$ , we define ${\mathcal{Q}}^{*}_{j}$ as follows:

{\mathcal{Q}}^{*}_{j}:=z_{y_{2}}^{j}\longrightarrow y_{2}\longrightarrow w_{y_{2}}^{j};x_{1}\longrightarrow y_{1};x_{2}\longrightarrow y_{2}\longrightarrow z_{y_{2}}^{j};w_{y_{2}}^{j}\longrightarrow y_{2}.

Let ${\mathbb{L}}_{4}^{*}:=\{Q^{*}_{j}:j\in[m_{y_{2}}]\}$ . Let ${\mathcal{Q}}^{*}_{j}\in{\mathbb{L}}_{4}^{*}$ , and let $A^{*}_{j}$ be an inner vertex of ${\mathcal{Q}}^{*}_{j}$ , then

(D4*): Either $A_{j}^{*}\cap XY=XY\setminus\{z_{y_{2}}^{j}\}$ or $A^{*}_{j}\cap XY=XY$ , and either $A_{j}^{*}\cap\overline{XY}=\emptyset$ or $A_{j}^{*}\cap\overline{XY}=\{w_{y_{2}}^{j}\}$ , and at least one of the following holds: $A_{j}^{*}\cap XY=XY\setminus\{z_{y_{2}}^{j}\}$ or $A_{j}^{*}\cap\overline{XY}=\{w_{y_{2}}^{j}\}$ .

Let ${\mathbb{L}}:={\mathbb{L}}_{1}\cup{\mathbb{L}}_{2}\cup{\mathbb{L}}_{3}\cup{\mathbb{L}}_{4}\cup{\mathbb{L}}^{*}_{3}\cup{\mathbb{L}}^{*}_{4}$ . Since $|{\mathbb{L}}_{1}|=2,|{\mathbb{L}}_{2}|=\eta,|{\mathbb{L}}_{3}|=m_{x_{1}},|{\mathbb{L}}_{4}|=m_{y_{1}},|{\mathbb{L}}^{*}_{3}|=m_{x_{2}},|{\mathbb{L}}^{*}_{4}|=m_{y_{2}}$ , and $m=2+\eta+m_{x_{1}}+m_{y_{1}}+m_{x_{2}}+m_{y_{2}}$ , then in order to finish the Step 1 of Case 2, it is enough to show that the paths in ${\mathbb{L}}$ are pairwise internally disjoint.

Claim 2.6.

The $X-Y$ paths in ${\mathbb{L}}$ are pairwise internally disjoint.

Proof of Claim 2.6: We start by noting that, in some sense, the four ways in which the paths of $\mathbb{T}$ were constructed in Step 1 of Case 1 have been “repeated” in the construction of the paths of ${\mathbb{L}}$ . This close relationship between $\mathbb{T}$ and ${\mathbb{L}}$ is the main ingredient in the proof of Claim 2.6.

Before moving on any further, let us verify that the two paths of ${\mathbb{L}}_{1}$ are internally disjoint. Let $A_{1}$ and $A_{2}$ be the inner vertices of ${\mathcal{P}}_{x_{1}}$ and ${\mathcal{P}}_{x_{2}}$ , respectively. Then $A_{1}=(X\setminus\{x_{1}\})\cup\{y_{1}\}$ and $A_{2}=(X\setminus\{x_{2}\})\cup\{y_{2}\}$ , and so $A_{1}\neq A_{2}$ .

The analogies between the paths of $\mathbb{T}$ and ${\mathbb{L}}$ are given by the interactions that the inner vertices of the $X-Y$ paths have with $XY$ and $\overline{XY}^{\prime}$ in the Case 1 and with $XY$ and $\overline{XY}$ in the Case 2. More formally, let ${\mathcal{T}}\in{\mathbb{T}}$ and ${\mathcal{L}}\in{\mathbb{L}}$ . We say that ${\mathcal{T}}$ and ${\mathcal{L}}$ are analogous, if $A\cap\overline{XY}^{\prime}=B\cap\overline{XY}$ and $A\cap XY=B\cap XY$ , for any $A$ and $B$ inner vertices of ${\mathcal{T}}$ and ${\mathcal{L}}$ , respectively. For ${\mathbb{T}}^{\prime}\subseteq{\mathbb{T}}$ and ${\mathbb{L}}^{\prime}\subseteq{\mathbb{L}}$ we write ${\mathbb{T}}^{\prime}\sim{\mathbb{L}}^{\prime}$ to mean that any path of ${\mathbb{T}}^{\prime}$ is analogous to any path of ${\mathbb{L}}^{\prime}$ . For instance, note that ${\mathbb{T}}_{1}\sim{\mathbb{L}}_{1}$ . Indeed, let ${\mathcal{P}}_{0}\in{\mathbb{T}}_{1}$ and ${\mathcal{P}}_{x_{i}}\in{\mathbb{L}}_{1}$ , and let $A_{0}$ and $A$ be inner vertices of ${\mathcal{P}}_{0}$ and ${\mathcal{P}}_{x_{i}}$ , respectively. From (C1) we know that $A_{0}\cap XY=XY$ , and from (D1) we have that $A\cap XY=XY$ . Similarly, from (C1) it follows that $A_{0}\cap\overline{XY}^{\prime}=\emptyset$ , and from (D1) that $A\cap\overline{XY}=\emptyset$ . Analogously, we can verify that:

•

(C1) and (D1) imply that ${\mathbb{T}}_{1}\sim{\mathbb{L}}_{1}$ . For completeness of this list, we include this case here again.
•

(C2), (C2.1) and (D2) imply that ${\mathbb{T}}^{\prime}_{2}\sim{\mathbb{L}}_{2}$ , where ${\mathbb{T}}^{\prime}_{2}$ is the subset of paths in ${\mathbb{T}}_{2}$ with $w_{j}\neq v$ .
•

(C3) and (D3) imply that ${\mathbb{T}}_{3}\sim{\mathbb{L}}_{3}$ .
•

(C3) and (D3*) imply that ${\mathbb{T}}_{3}\sim{\mathbb{L}}^{*}_{3}$ .
•

(C4) and (D4) imply that ${\mathbb{T}}_{4}\sim{\mathbb{L}}_{4}$ .
•

(C4) and (D4*) imply that ${\mathbb{T}}_{4}\sim{\mathbb{L}}^{*}_{4}$ .

We recall that the strategy in the proof of Claim 2.2 was the following. Given two inner vertices $A$ and $B$ belonging to distinct paths of ${\mathbb{T}}$ , we always conclude that $A\neq B$ by showing that at least one of $A\cap\overline{XY}^{\prime}\neq B\cap\overline{XY}^{\prime}$ or $A\cap XY\neq B\cap XY$ holds. From this fact, the definition of $\sim$ , and the above list, it is not hard to see that analogous arguments as those used in the proof of Claim 2.2 imply that the $X-Y$ paths belonging to ${\mathbb{L}}_{1}\cup{\mathbb{L}}_{2}\cup{\mathbb{L}}_{3}\cup{\mathbb{L}}_{4}$ (resp. ${\mathbb{L}}_{1}\cup{\mathbb{L}}_{2}\cup{\mathbb{L}}^{*}_{3}\cup{\mathbb{L}}^{*}_{4}$ ) are pairwise internally disjoint. Thus, it remains to show that the paths in ${\mathbb{L}}_{3}$ (resp. ${\mathbb{L}}_{4}$ ) are pairwise internally disjoint from the paths in ${\mathbb{L}}^{*}_{3}\cup{\mathbb{L}}^{*}_{4}$ .

Let $A_{i},A_{j},A^{*}_{s}$ , and $A^{*}_{t}$ be inner vertices of ${\mathcal{P}}_{i}\in{\mathbb{L}}_{3}$ , ${\mathcal{Q}}_{j}\in{\mathbb{L}}_{4}$ , ${\mathcal{P}}^{*}_{s}\in{\mathbb{L}}^{*}_{3}$ , and ${\mathcal{Q}}^{*}_{t}\in{\mathbb{L}}^{*}_{4}$ , respectively. We analyze these cases separately.

$\{A_{i},A^{*}_{s}\}$ :: By Observation 2.5, either $z_{x_{1}}^{i}\neq z_{x_{2}}^{s}$ or $w_{x_{1}}^{i}\neq w_{x_{2}}^{s}$ .
Suppose that $z_{x_{1}}^{i}\neq z_{x_{2}}^{s}$ . If $A_{i}\cap XY=XY\setminus\{z_{x_{1}}^{i}\}$ or $A^{*}_{s}\cap XY=XY\setminus\{z_{x_{2}}^{s}\}$ , then $A_{i}\cap XY\neq A^{*}_{s}\cap XY$ , as required. Suppose then that $A_{i}\cap XY=XY=A^{*}_{s}\cap XY$ . From the definitions of ${\mathcal{P}}_{i}$ and ${\mathcal{P}}^{*}_{s}$ we know that $A_{i}=(X\setminus\{x_{1}\})\cup\{w_{x_{1}}^{i}\}$ and $A^{*}_{s}=(X\setminus\{x_{2}\})\cup\{w_{x_{2}}^{s}\}$ , and so $A_{i}\neq A^{*}_{s}$ .
Suppose now that $w_{x_{1}}^{i}\neq w_{x_{2}}^{s}$ . If $A_{i}\cap\overline{XY}=\{w_{x_{1}}^{i}\}$ or $A^{*}_{s}\cap\overline{XY}=\{w_{x_{2}}^{s}\}$ , then $A_{i}\cap\overline{XY}\neq A^{*}_{s}\cap\overline{XY}$ . Suppose then that $A_{i}\cap\overline{XY}=\emptyset=A^{*}_{s}\cap\overline{XY}$ . Again, from the definitions of ${\mathcal{P}}_{i}$ and ${\mathcal{P}}^{*}_{s}$ we have that $A_{i}=(Y\setminus\{z_{x_{1}}^{i}\})\cup\{x_{1}\}$ and $A^{*}_{s}=(Y\setminus\{z_{x_{2}}^{s}\})\cup\{x_{2}\}$ , and so $A_{i}\neq A^{*}_{s}$ .
$\{A_{i},A^{*}_{t}\}$ :: Again, by Observation 2.5, we have that either $z_{x_{1}}^{i}\neq z_{y_{2}}^{t}$ or $w_{x_{1}}^{i}\neq w_{y_{2}}^{t}$ .
Suppose that $z_{x_{1}}^{i}\neq z_{y_{2}}^{t}$ . If $A_{i}\cap XY=XY\setminus\{z_{x_{1}}^{i}\}$ or $A^{*}_{t}\cap XY=XY\setminus\{z_{y_{2}}^{t}\}$ , then (D3) and (D4*) imply $A_{i}\cap XY\neq A^{*}_{t}\cap XY$ , as required. Suppose then that $A_{i}\cap XY=XY=A^{*}_{t}\cap XY$ . From the definitions of ${\mathcal{P}}_{i}$ and ${\mathcal{Q}}^{*}_{t}$ it follows that $A_{i}=(X\setminus\{x_{1}\})\cup\{w_{x_{1}}^{i}\}$ and $A^{*}_{t}=(Y\setminus\{y_{2}\})\cup\{w_{y_{2}}^{t}\}$ , and so $y_{1}\in A^{*}_{t}\setminus A_{i}$ , which implies that $A_{i}\neq A^{*}_{t}$ .
Now suppose that $w_{x_{1}}^{i}\neq w_{y_{2}}^{t}$ . If $A_{i}\cap\overline{XY}=\{w_{x_{1}}^{i}\}$ or $A^{*}_{t}\cap\overline{XY}=\{w_{y_{2}}^{t}\}$ , then (D3) and (D4*) imply that $A_{i}\cap\overline{XY}\neq A^{*}_{t}\cap\overline{XY}$ . Suppose then that $A_{i}\cap\overline{XY}=\emptyset=A^{*}_{t}\cap\overline{XY}$ . Again, from the definitions of ${\mathcal{P}}_{i}$ and ${\mathcal{Q}}^{*}_{t}$ we have that $A_{i}=(Y\setminus\{z_{x_{1}}^{i}\})\cup\{x_{1}\}$ and $A^{*}_{t}=(X\setminus\{z_{y_{2}}^{t}\})\cup\{y_{2}\}$ , and so $y_{1}\in A_{i}\setminus A^{*}_{t}$ , which implies that $A_{i}\neq A^{*}_{t}$ .
$\{A_{j},A^{*}_{s}\}$ :: This case can be handled in the same manner as case $\{A_{i},A^{*}_{t}\}$ .
$\{A_{j},A^{*}_{t}\}$ :: Again, this case can be handled in the same manner as case $\{A_{i},A^{*}_{s}\}$ .

$\triangle$

2.2.2 Step 2 of Case 2

We recall that $\deg(X)\leq\deg(Y)$ imply that

a_{1}+a_{2}+b_{1}+b_{2}\leq c_{1}+c_{2}+d_{1}+d_{2}.

(2)

We now proceed to show that $\delta-m\leq 1$ .

Claim 2.7.

Let $\delta,m,m_{x_{1}},m_{y_{1}},m_{x_{2}},m_{y_{2}},$ and $\eta$ be as above. Then, $\delta-m\leq 1$ , and moreover, if $\delta-m=1$ then, without loss of generality, we may assume that one of the following holds:

(J1)

$a_{1}>c_{1}$ , $a_{2}>c_{2}$ , $b_{1}>d_{1}$ , $b_{2}<d_{2}$ and exactly one of $\{x_{2}y_{1},y_{1}y_{2}\}$ is in $T$ ,
(J2)

$a_{1}>c_{1}$ , $b_{1}>d_{1}$ , either $a_{2}<c_{2}$ or $b_{2}<d_{2}$ , and exactly one of $\{x_{1}x_{2},y_{1}y_{2}\}$ is in $T$ ,
(J3)

$a_{1}>c_{1}$ , $a_{2}\leq c_{2}$ , $b_{1}\leq d_{1}$ , $b_{2}<d_{2}$ and exactly one of $\{x_{1}x_{2},x_{2}y_{1}\}$ is in $T$ ,
(J4)

$a_{2}\leq c_{2}$ , $b_{1}\leq d_{1}$ , either $a_{1}<c_{1}$ or $b_{2}<d_{2}$ , and $x_{1}y_{2}$ is in $T$ .

Proof of Claim 2.7: We analyze several cases separately, depending on the order relations between the elements of the sets $\{a_{i},c_{i}\}$ and $\{b_{i},d_{i}\}$ , for $i,j\in\{1,2\}$ . The possible cases are the following:

(1) $a_{1}>c_{1}$ , $a_{2}>c_{2}$ , $b_{1}>d_{1}$ and $b_{2}>d_{2}$	(9) $a_{1}\leq c_{1}$ , $a_{2}>c_{2}$ , $b_{1}>d_{1}$ and $b_{2}>d_{2}$
(2) $a_{1}>c_{1}$ , $a_{2}>c_{2}$ , $b_{1}>d_{1}$ and $b_{2}\leq d_{2}$	(10) $a_{1}\leq c_{1}$ , $a_{2}>c_{2}$ , $b_{1}>d_{1}$ and $b_{2}\leq d_{2}$
(3) $a_{1}>c_{1}$ , $a_{2}>c_{2}$ , $b_{1}\leq d_{1}$ and $b_{2}>d_{2}$	(11) $a_{1}\leq c_{1}$ , $a_{2}>c_{2}$ , $b_{1}\leq d_{1}$ and $b_{2}>d_{2}$
(4) $a_{1}>c_{1}$ , $a_{2}>c_{2}$ , $b_{1}\leq d_{1}$ and $b_{2}\leq d_{2}$	(12) $a_{1}\leq c_{1}$ , $a_{2}>c_{2}$ , $b_{1}\leq d_{1}$ and $b_{2}\leq d_{2}$
(5) $a_{1}>c_{1}$ , $a_{2}\leq c_{2}$ , $b_{1}>d_{1}$ and $b_{2}>d_{2}$	(13) $a_{1}\leq c_{1}$ , $a_{2}\leq c_{2}$ , $b_{1}>d_{1}$ and $b_{2}>d_{2}$
(6) $a_{1}>c_{1}$ , $a_{2}\leq c_{2}$ , $b_{1}>d_{1}$ and $b_{2}\leq d_{2}$	(14) $a_{1}\leq c_{1}$ , $a_{2}\leq c_{2}$ , $b_{1}>d_{1}$ and $b_{2}\leq d_{2}$
(7) $a_{1}>c_{1}$ , $a_{2}\leq c_{2}$ , $b_{1}\leq d_{1}$ and $b_{2}>d_{2}$	(15) $a_{1}\leq c_{1}$ , $a_{2}\leq c_{2}$ , $b_{1}\leq d_{1}$ and $b_{2}>d_{2}$
(8) $a_{1}>c_{1}$ , $a_{2}\leq c_{2}$ , $b_{1}\leq d_{1}$ and $b_{2}\leq d_{2}$	(16) $a_{1}\leq c_{1}$ , $a_{2}\leq c_{2}$ , $b_{1}\leq d_{1}$ and $b_{2}\leq d_{2}$

As a first observation, the case (1) is impossible because of Inequality 2. Let us next show that it is enough to consider only six cases: (2), (4), (6), (7), (8) and (16), because each of the rest of cases is similar to one of these cases.

In the cases (3), (9)–(12) and (15) interchange the labels of the elements in each of the following sets: $\{x_{1},x_{2}\}$ and $\{y_{1},y_{2}\}$ . These interchanges automatically produce the interchange of the values in each of the following sets $\{a_{1},a_{2}\}$ , $\{b_{1},b_{2}\}$ , $\{c_{1},c_{2}\}$ and $\{d_{1},d_{2}\}$ . By performing these relabelings, we can see that: case (3) is similar to case (2), case (9) is similar to case (5), case (10) is similar to case (7), case (11) is similar to case (6), case (12) is similar to case (8), and case (15) is similar to case (14). Thus, we may restrict our analysis to the cases (2), (4)–(8), (13), (14), and (16).

In the cases (5), (13) and (14) we consider the graph $F_{n-k}(T)$ instead of $F_{k}(T)$ with the following relabeling. For $i\in\{1,2\}$ , let $x^{\prime}_{i}:=y_{i}$ and $y^{\prime}_{i}:=x_{i}$ . Consider the vertices $X^{\prime}=\phi(X)=V(T)\setminus X$ and $Y^{\prime}=\phi(Y)=V(T)\setminus Y$ in $F_{n-k}(T)$ . Let $XY^{\prime}:=\overline{XY}$ and $\overline{XY}^{\prime}:=XY$ , and define the values $a^{\prime}_{i},b^{\prime}_{i},c^{\prime}_{i}$ and $d^{\prime}_{i}$ analogously to $a_{i},b_{i},c_{i}$ and $d_{i}$ . Then we have $a^{\prime}_{i}=b_{i}$ , $b^{\prime}_{i}=a_{i}$ , $c^{\prime}_{i}=d_{i}$ and $d^{\prime}_{i}=c_{i}$ , and so case (5) is similar to case (2), case (13) is similar to case (4), and case (14) is similar to case (8). Then, we may assume that one of cases (2), (4), (6), (7), (8) and (16) holds.

Our strategy is as follows. In any of the analyzed cases we show that $F_{k}(G)$ has a vertex $X_{1}$ “close to” $X$ whose degree is at most $m+1$ . Recall that we need to consider only the cases (2), (4), (6), (7), (8) and (16).

(2)

$a_{1}>c_{1}$ , $a_{2}>c_{2}$ , $b_{1}>d_{1}$ and $b_{2}\leq d_{2}$ .

Then $a_{1}>0$ and $a_{2}>0$ . Moreover, our suppositions and (2) imply that $d_{2}>b_{2}$ . Let $U:=\overline{XY}\cup\{x_{1},x_{2},y_{1},y_{2}\}$ . From $a_{1}>0,a_{2}>0,$ and $d_{2}>0$ it follows that $x_{1},x_{2},$ and $y_{2}$ have degree at least 2 in $T[U]$ . Since $T[U]$ is a forest, then there is a vertex $u\in U\setminus\{x_{1},x_{2},y_{1},y_{2}\}$ such that $deg_{T[U]}(u)\leq 1$ . Let $X_{1}:=(X\setminus\{x_{1},x_{2}\})\cup\{y_{1},u\}$ .

(2.1)

If $y_{1}$ is not adjacent to neither $x_{2}$ nor $y_{2}$ , then

	$\displaystyle\delta\leq\deg(X_{1})$	$\displaystyle\leq c_{1}+c_{2}+d_{1}+b_{2}+\eta+1+deg_{T[U]}(u)$
		$\displaystyle\leq m_{x_{1}}+m_{x_{2}}+m_{y_{1}}+m_{y_{2}}+\eta+2=m.$

(2.2)

If $y_{1}$ is adjacent to some of $x_{2}$ or $y_{2}$ , then it is adjacent to exactly one of them, because $T$ has no cycles. Hence, in this case

	$\displaystyle\delta\leq\deg(X_{1})$	$\displaystyle\leq c_{1}+c_{2}+d_{1}+b_{2}+\eta+2+deg_{T[U]}(u)$
		$\displaystyle=m_{x_{1}}+m_{x_{2}}+m_{y_{1}}+m_{y_{2}}+\eta+3=m+1,$

and so (J1) holds.

(4)

$a_{1}>c_{1}$ , $a_{2}>c_{2}$ , $b_{1}\leq d_{1}$ and $b_{2}\leq d_{2}$ .

If $d_{1}>0$ and $d_{2}>0$ , then $\deg_{T[U]}(y_{i})=d_{i}+1\geq 2$ and $\deg_{T[U]}(x_{i})=a_{i}+1\geq 2$ , for $U:=\overline{XY}\cup\{x_{1},x_{2},y_{1},y_{2}\}$ and $i\in\{1,2\}$ . These and the fact that $T[U]$ is a forest imply the existence of two vertices $u_{1},u_{2}\in U\setminus\{x_{1},x_{2},y_{1},y_{2}\}$ such that $\deg_{T[U]}(u_{i})\leq 1$ for $i\in\{1,2\}$ . Let $X_{1}:=(X\setminus\{x_{1},x_{2}\})\cup\{u_{1},u_{2}\}$ . Then

	$\displaystyle\delta\leq\deg(X_{1})$	$\displaystyle\leq c_{1}+c_{2}+b_{1}+b_{2}+\eta+\deg_{T[U]}(u_{1})+\deg_{T[U]}(u_{2})$
		$\displaystyle\leq m_{x_{1}}+m_{x_{2}}+m_{y_{1}}+m_{y_{2}}+\eta+2=m.$

We now suppose $d_{1}>0$ and $d_{2}>0$ does not hold. Then $d_{1}=0$ or $d_{2}=0$ . By symmetry, we may assume that $d_{1}=0$ . Then $b_{1}=0$ , and $d_{2}>0$ by (2). Then for $U:=\overline{XY}\cup\{x_{1},x_{2},y_{1},y_{2}\}$ , we have that $\deg_{T[U]}(x_{i})=a_{i}+1\geq 2$ for $i\in\{1,2\}$ and $\deg_{T[U]}(y_{2})=d_{2}+1\geq 2$ . Since $T[U]$ has no cycles, then $y_{1}$ is adjacent to at most one of $x_{2}$ or $y_{2}$ . From this fact, $b_{1}=d_{1}=0$ , and $x_{1}y_{1}\in E(T[U])$ it follows that $1\leq\deg_{T[U]}(y_{1})\leq 2$ . Again, these and the fact that $T[U]$ is a forest imply the existence of two distinct vertices $u_{1},u_{2}\in U\setminus\{x_{1},x_{2},y_{2}\}$ such that $\deg_{T[U]}(u_{i})\leq 1$ for $i\in\{1,2\}$ . Let $X_{1}=(X\setminus\{x_{1},x_{2}\})\cup\{u_{1},u_{2}\}$ , then

	$\displaystyle\delta\leq\deg(X_{1})$	$\displaystyle\leq c_{1}+c_{2}+b_{1}+b_{2}+\eta+\deg_{T[U]}(u_{1})+\deg_{T[U]}(u_{2})$
		$\displaystyle\leq m_{x_{1}}+m_{x_{2}}+m_{y_{1}}+m_{y_{2}}+\eta+2=m.$

(6)

$a_{1}>c_{1}$ , $a_{2}\leq c_{2}$ , $b_{1}>d_{1}$ and $b_{2}\leq d_{2}$ .

From (2) and these inequalities it follows that at least one of $c_{2}>a_{2}$ or $d_{2}>b_{2}$ holds. Let $X_{1}:=(X\setminus\{x_{1}\})\cup\{y_{1}\}$ . Since $T$ has no cycles, then it contains at most one of $x_{1}x_{2}$ or $y_{1}y_{2}$ .

(6.1)

Suppose that none of $x_{1}x_{2}$ or $y_{1}y_{2}$ is in $T$ . Then

	$\displaystyle\delta\leq\deg(X_{1})$	$\displaystyle\leq c_{1}+a_{2}+d_{1}+b_{2}+\eta+2$
		$\displaystyle=m_{x_{1}}+m_{x_{2}}+m_{y_{1}}+m_{y_{2}}+\eta+2=m.$

(6.2)

Suppose that exactly one of $x_{1}x_{2}$ or $y_{1}y_{2}$ is in $T$ . Then

	$\displaystyle\delta\leq\deg(X_{1})$	$\displaystyle\leq c_{1}+a_{2}+d_{1}+b_{2}+\eta+3$
		$\displaystyle=m_{x_{1}}+m_{x_{2}}+m_{y_{1}}+m_{y_{2}}+\eta+3=m+1,$

and so (J2) holds.

(7)

$a_{1}>c_{1}$ , $a_{2}\leq c_{2}$ , $b_{1}\leq d_{1}$ and $b_{2}>d_{2}$ .

Let $X_{1}:=(X\setminus\{x_{1}\})\cup\{y_{2}\}$ . Again, since $T$ has no cycles, then there is at most one edge in $T$ with one endvertex in $\{x_{1},y_{1}\}$ and the other endvertex in $\{x_{2},y_{2}\}$ . Then

	$\displaystyle\delta\leq\deg(X_{1})$	$\displaystyle\leq c_{1}+a_{2}+b_{1}+d_{2}+\eta+1$
		$\displaystyle=m_{x_{1}}+m_{x_{2}}+m_{y_{1}}+m_{y_{2}}+\eta+1<m.$

(8)

$a_{1}>c_{1}$ , $a_{2}\leq c_{2}$ , $b_{1}\leq d_{1}$ and $b_{2}\leq d_{2}$ .

As we have mentioned above, $T$ has at most one edge with one end in $\{x_{1},y_{1}\}$ and the other end in $\{x_{2},y_{2}\}$ .

(8.1)

Suppose that $d_{2}\leq b_{2}+1$ . Then $X_{1}:=(X\setminus\{x_{1}\})\cup\{y_{2}\}$ satisfies the following

	$\displaystyle\delta\leq\deg(X_{1})$	$\displaystyle\leq c_{1}+a_{2}+b_{1}+d_{2}+\eta+1$
		$\displaystyle\leq c_{1}+a_{2}+b_{1}+(b_{2}+1)+\eta+1$
		$\displaystyle\leq m_{x_{1}}+m_{x_{2}}+m_{y_{1}}+m_{y_{2}}+\eta+2=m.$

(8.2)

Suppose that $d_{2}\geq b_{2}+2$ . Then $a_{1}>0$ and $d_{2}\geq 2$ , and hence $x_{1}$ and $y_{2}$ have degree at least 2 in $T[U]$ , for $U:=\overline{XY}\cup\{x_{1},y_{1},y_{2}\}$ . Since $T[U]$ is a forest, then there is a vertex $u\in U\setminus\{y_{1},x_{1},y_{2}\}$ such that $\deg_{T[U]}(u)\leq 1$ . Let $X_{1}:=(X\setminus\{x_{1}\})\cup\{u\}$ .

(8.2.1)

Suppose that $x_{2}$ is not adjacent to neither $x_{1}$ nor $y_{1}$ . Then,

	$\displaystyle\delta\leq\deg(X_{1})$	$\displaystyle\leq c_{1}+a_{2}+b_{1}+b_{2}+\eta+2$
		$\displaystyle=m_{x_{1}}+m_{x_{2}}+m_{y_{1}}+m_{y_{2}}+\eta+2=m.$

(8.2.2)

Suppose that $x_{2}$ is adjacent to some of $x_{1}$ or $y_{1}$ . Since there is at most one edge with one end in $\{x_{1},y_{1}\}$ and the other end in $\{x_{2},y_{2}\}$ , then $x_{2}$ is adjacent to exactly one of $x_{1}$ or $y_{1}$ . Then,

	$\displaystyle\delta\leq\deg(X_{1})$	$\displaystyle\leq c_{1}+a_{2}+b_{1}+b_{2}+\eta+3$
		$\displaystyle=m_{x_{1}}+m_{x_{2}}+m_{y_{1}}+m_{y_{2}}+\eta+3=m+1,$

implying that (J3) holds.

(16)

$a_{1}\leq c_{1}$ , $a_{2}\leq c_{2}$ , $b_{1}\leq d_{1}$ and $b_{2}\leq d_{2}$ .

Since there is at most one edge with one end in $\{x_{1},y_{1}\}$ and the other end in $\{x_{2},y_{2}\}$ , then $T$ contains at most one of $x_{1}y_{2}$ or $x_{2}y_{1}$ .

(16.1)

Suppose that neither $x_{1}y_{2}$ nor $x_{2}y_{1}$ is in $T$ . Then,

	$\displaystyle\delta\leq\deg(X)$	$\displaystyle\leq a_{1}+a_{2}+b_{1}+b_{2}+\eta+2$
		$\displaystyle=m_{x_{1}}+m_{x_{2}}+m_{y_{1}}+m_{y_{2}}+\eta+2=m.$

(16.2)

Suppose that some of $x_{1}y_{2}$ or $x_{2}y_{1}$ is in $T$ . Then exactly one of $x_{1}y_{2}$ or $x_{2}y_{1}$ belongs to $T$ . By symmetry, we may assume that $x_{1}$ is adjacent to $y_{2}$ . Let $X_{1}:=(X\setminus\{x_{1}\})\cup\{y_{2}\}$ . Then,

\displaystyle\delta\leq\deg(X_{1})

\displaystyle\leq c_{1}+a_{2}+b_{1}+d_{2}+\eta+1

(16.2.1)

If $a_{1}=c_{1}$ and $b_{2}=d_{2}$ , then

$\delta\leq\deg(X_{1})\leq m_{x_{1}}+m_{x_{2}}+m_{y_{1}}+m_{y_{2}}+\eta+1\leq m.$

(16.2.2)

If $a_{1}<c_{1}$ or $b_{2}<d_{2}$ , then

	$\displaystyle\delta\leq\deg(X)$	$\displaystyle\leq a_{1}+a_{2}+b_{1}+b_{2}+\eta+3$
		$\displaystyle=m_{x_{1}}+m_{x_{2}}+m_{y_{1}}+m_{y_{2}}+\eta+3=m+1,$

and so (J4) holds.

$\triangle$

Claim 2.7 shows that almost all $X-Y$ paths claimed by Lemma 2.1 are provided by $\mathbb{L}$ , when $|XY|=k-2$ . We finish the proof of Case 2 with the construction of the remaining $\delta-m$ $X-Y$ paths.

Claim 2.8.

If $|XY|=k-2$ , then $F_{k}(T)$ has at least $\delta$ $X-Y$ pairwise internally disjoint paths.

Proof of Claim 2.8: Consider the $m$ $X-Y$ paths of ${\mathbb{L}}$ . Clearly, if $m\geq\delta$ , then we are done. Then by Claim 2.7 we can assume that $m+1=\delta$ , and that one of (J1), (J2), (J3) or (J4) holds.

In view of these facts, it is enough to exhibit a new $X-Y$ path ${\mathcal{P}}^{\ell}\notin{\mathbb{L}}$ with ${\mathcal{P}}^{\ell}$ internally disjoint from any path in ${\mathbb{L}}$ . We note that in any of these four cases, $T$ has one edge $e$ with an endvertex in $\{x_{1},y_{1}\}$ and the other endvertex in $\{x_{2},y_{2}\}$ . Since $T$ has no cycles, then $e$ is the only edge of $T$ with this property. Then $\overline{XY}(x_{1}),\overline{XY}(x_{2}),\overline{XY}(y_{1}),\overline{XY}(y_{2}),XY(x_{1}),\-XY(x_{2}),XY(y_{1})$ , and $XY(y_{2})$ are pairwise disjoint, as otherwise $T$ has a cycle.

Our strategy is as follows. First we define a set ${\mathbb{P}}=\{{\mathcal{P}}^{1},{\mathcal{P}}^{2},{\mathcal{P}}^{3},{\mathcal{P}}^{4}\}$ consisting of four new $X-Y$ paths of $F_{k}(T)$ . Then we show that for each of the four cases mentioned in previous paragraph, there is a path in ${\mathbb{P}}$ which is internally disjoint from any path of ${\mathbb{L}}$ , providing the additional required path.

If $a_{1}>c_{1}$ and $d_{2}>b_{2}$ , then we define the $X-Y$ path ${\mathcal{P}}^{1}$ as follows:

{\mathcal{P}}^{1}:=x_{1}\rightarrow w_{x_{1}}^{a_{1}};x_{2}\rightarrow y_{2}\rightarrow w_{y_{2}}^{d_{2}};w_{x_{1}}^{a_{1}}\rightarrow x_{1}\rightarrow y_{1};w_{y_{2}}^{d_{2}}\rightarrow y_{2}.

From the definition of ${\mathcal{P}}^{1}$ it follows that if $A^{1}$ is an inner vertex of ${\mathcal{P}}^{1}$ , then

(E1): $A^{1}\cap XY=XY$ , and $A^{1}\cap\overline{XY}\in\left\{\{w_{x_{1}}^{a_{1}}\},\{w_{y_{2}}^{d_{2}}\},\{w_{x_{1}}^{a_{1}},w_{y_{2}}^{d_{2}}\}\right\}$ .

If $a_{1}>c_{1}$ and $c_{2}>a_{2}$ , then we define the $X-Y$ path ${\mathcal{P}}^{2}$ as follows:

{\mathcal{P}}^{2}:=x_{1}\longrightarrow w_{x_{1}}^{a_{1}};x_{2}\longrightarrow y_{2};z_{x_{2}}^{c_{2}}\longrightarrow x_{2};w_{x_{1}}^{a_{1}}\longrightarrow x_{1}\longrightarrow y_{1};x_{2}\longrightarrow z_{x_{2}}^{c_{2}}.

From the definition of ${\mathcal{P}}^{2}$ it follows that if $A^{2}$ is an inner vertex of ${\mathcal{P}}^{2}$ , then

(E2): Either $A^{2}\cap XY=XY$ or $A^{2}\cap XY=XY\setminus\{z_{x_{2}}^{c_{2}}\}$ , and either $A^{2}\cap\overline{XY}=\emptyset$ or $A^{2}\cap\overline{XY}=\{w_{x_{1}}^{a_{1}}\}$ , and at least one of the following holds: $A^{2}\cap\overline{XY}=\{w_{x_{1}}^{a_{1}}\}$ or $A^{2}\cap XY=XY\setminus\{z_{x_{2}}^{c_{2}}\}$ .

If $c_{1}>a_{1}$ and $x_{1}y_{2}\in E(T)$ , then we define the $X-Y$ path ${\mathcal{P}}^{3}$ as follows:

{\mathcal{P}}^{3}:=x_{1}\longrightarrow y_{2};z_{x_{1}}^{c_{1}}\longrightarrow x_{1}\longrightarrow y_{1};y_{2}\longrightarrow x_{1};x_{2}\longrightarrow y_{2};x_{1}\longrightarrow z_{x_{1}}^{c_{1}}.

From the definition of ${\mathcal{P}}^{3}$ it follows that if $A^{3}$ is an inner vertex of ${\mathcal{P}}^{3}$ , then

(E3): $A^{3}\cap\overline{XY}=\emptyset$ , and $A^{3}\cap XY\in\left\{XY,XY\setminus\{z_{x_{1}}^{c_{1}}\}\right\}$ .

If $d_{2}>b_{2}$ and $x_{1}y_{2}\in E(T)$ , then we define the $X-Y$ path ${\mathcal{P}}^{4}$ as follows:

{\mathcal{P}}^{4}:=x_{1}\longrightarrow y_{2}\longrightarrow w_{y_{2}}^{d_{2}};x_{2}\longrightarrow y_{2}\longrightarrow x_{1}\longrightarrow y_{1};w_{y_{2}}^{d_{2}}\longrightarrow y_{2}.

From the definition of ${\mathcal{P}}^{4}$ it follows that if $A^{4}$ is an inner vertex of ${\mathcal{P}}^{4}$ , then

(E4): $A^{4}\cap XY=XY$ , and $A^{4}\cap\overline{XY}\in\left\{\emptyset,\{w_{y_{2}}^{d_{2}}\}\right\}$ .

We now proceed to show that for $i\in\{1,2,3,4\}$ , the $X-Y$ paths in $\{{\mathcal{P}}^{i}\}\cup{\mathbb{L}}$ are internally disjoint. For this, let us assume that $A^{1},A^{2},A^{3},A^{4},A,A_{i,j},A_{i},A_{j},A^{*}_{s}$ , and $A^{*}_{t}$ are inner vertices of ${\mathcal{P}}^{1},{\mathcal{P}}^{2},{\mathcal{P}}^{3},{\mathcal{P}}^{4},{\mathcal{P}}\in{\mathbb{L}}_{1}$ , ${\mathcal{P}}_{i,j}\in{\mathbb{L}}_{2}$ , ${\mathcal{P}}_{i}\in{\mathbb{L}}_{3}$ , ${\mathcal{Q}}_{j}\in{\mathbb{L}}_{4}$ , ${\mathcal{P}}^{*}_{s}\in{\mathbb{L}}_{3}^{*}$ , and ${\mathcal{Q}}^{*}_{t}\in{\mathbb{L}}_{4}^{*}$ , respectively.

$\{{\mathcal{P}}^{1}\}\cup{\mathbb{L}}$ :: We have $A\cap\overline{XY}=\emptyset$ while $A^{1}\cap\overline{XY}\neq\emptyset$ , so $A^{1}\neq A$ . Also we have $A_{i,j}\cap XY\neq XY$ and $A^{1}\cap XY=XY$ , thus $A^{1}\neq A_{i,j}$ . Let $\overline{XY}_{1}:=\{w_{x_{1}}^{a_{1}},w_{y_{2}}^{d_{2}}\}$ and $\overline{XY}_{2}:=(\overline{XY}(x_{1})\cup\overline{XY}(x_{2})\cup\overline{XY}(y_{1})\cup\overline{XY}(y_{2}))\setminus\overline{XY}_{1}$ . Note that $\overline{XY}_{1}$ and $\overline{XY}_{2}$ are disjoint. For $A^{\prime}\in\{A_{i},A_{j},A_{s}^{*},A_{t}^{*}\}$ we may assume that $A^{\prime}\cap\overline{XY}\neq\emptyset$ (as otherwise we have $A^{\prime}\cap\overline{XY}=\emptyset\neq A^{1}\cap\overline{XY}$ , and so $A^{1}\neq A^{\prime}$ ). Then, $A^{1}\cap\overline{XY}\subset\overline{XY}_{1}$ while $A^{\prime}\cap\overline{XY}\subset\overline{XY}_{2}$ , since $\overline{XY}_{1}\cap\overline{XY}_{2}=\emptyset$ , it follows that $A^{1}\neq A^{\prime}$ .
$\{{\mathcal{P}}^{2}\}\cup{\mathbb{L}}$ :: By (E2) we know that $A^{2}\cap XY\in\{XY,XY\setminus\{z_{x_{2}}^{c_{2}}\}\}$ .

First suppose that $A^{2}\cap XY=XY$ , so $A^{2}\cap\overline{XY}=\{w_{x_{1}}^{a_{1}}\}$ . Since $A\cap\overline{XY}=\emptyset$ we have $A^{2}\neq A$ . Also, since $A_{i,j}\cap XY\neq XY$ , we have $A^{2}\neq A_{i,j}$ . Let $\overline{XY}_{1}:=\{w_{x_{1}}^{a_{1}}\}$ and $\overline{XY}_{2}:=(\overline{XY}(x_{1})\cup\overline{XY}(x_{2})\cup\overline{XY}(y_{1})\cup\overline{XY}(y_{2}))\setminus\overline{XY}_{1}$ . Note that $\overline{XY}_{1}$ and $\overline{XY}_{2}$ are disjoint. For $A^{\prime}\in\{A_{i},A_{j},A_{s}^{*},A_{t}^{*}\}$ we may assume that $A^{\prime}\cap\overline{XY}\neq\emptyset$ (as otherwise we have $A^{\prime}\cap\overline{XY}=\emptyset\neq A^{2}\cap\overline{XY}$ , and so $A^{2}\neq A^{\prime}$ ). Then, as in the previous case, we have $A^{2}\cap\overline{XY}\subset\overline{XY}_{1}$ while $A^{\prime}\cap\overline{XY}\subset\overline{XY}_{2}$ , since $\overline{XY}_{1}\cap\overline{XY}_{2}=\emptyset$ , it follows that $A^{2}\neq A^{\prime}$ .

Suppose now that $A^{2}\cap XY=XY\setminus\{z_{x_{2}}^{c_{2}}\}$ . We have $A\cap XY=XY$ , so $A^{2}\neq A$ . Let $XY_{1}:=\{z_{x_{2}}^{c_{2}}\}$ and $XY_{2}:=(XY(x_{1})\cup XY(x_{2})\cup XY(y_{1})\cup XY(y_{2}))\setminus XY_{1}$ . For $A^{\prime}\in\{A_{i},A_{j},A_{s}^{*},A_{t}^{*}\}$ , if $A^{\prime}\cap XY=XY$ then $A^{2}\neq A^{\prime}$ . Suppose now that $A^{\prime}\cap XY\neq XY$ . Then, $A^{\prime}\cap XY\subset XY_{2}$ , while $A^{2}\cap XY=XY_{1}$ ; and since $XY_{1}\cap XY_{2}=\emptyset$ it follows that $A^{2}\neq A^{\prime}$ . Consider now the vertex $A_{i,j}$ . Note that $z_{x_{2}}^{c_{2}}\neq z_{i}$ or $w_{x_{1}}^{a_{1}}\neq w_{j}$ , as otherwise the subgraph of $T$ induced by $z_{i},w_{j},x_{1},x_{2},y_{1},y_{2},$ and $e$ contains a cycle. If $z_{x_{2}}^{c_{2}}\neq z_{i}$ , then (D2) and (E2) imply $A_{i,j}\cap XY\neq A^{2}\cap XY$ , as required. On the other hand, if $w_{x_{1}}^{a_{1}}\neq w_{j}$ , again (D2) and (E2) imply that $A_{i,j}\cap\overline{XY}\neq A^{2}\cap\overline{XY}$ , and so $A_{i,j}\neq A^{2}$ .
$\{{\mathcal{P}}^{3}\}\cup{\mathbb{L}}$ :: By (E3) we have $A^{3}\cap\overline{XY}=\emptyset$ and $A^{3}\cap XY\in\{XY,XY\setminus\{z_{x_{1}}^{c_{1}}\}\}$ .

First suppose that $A^{3}\cap XY=XY$ . Then $A^{3}=(X\setminus\{x_{1}\})\cup\{y_{2}\}$ , and so $x_{2},y_{2}\in A^{3}$ . On the other hand, for any $A^{\prime}\in\{A,A_{i,j},A_{i},A_{j},A_{s}^{*},A_{t}^{*}\}$ we have that $x_{2}$ and $y_{2}$ do not belong to $A^{\prime}$ simultaneously, which implies that $A^{3}\neq A^{\prime}$ .

Suppose now that $A^{3}\cap XY=XY\setminus\{z_{x_{1}}^{c_{1}}\}$ . In this case proceed in a similar way to the case $\{{\mathcal{P}}^{2}\}\cup{\mathbb{L}}$ when $A^{2}\cap XY=XY\setminus\{z_{x_{2}}^{c_{2}}\}$ .
$\{{\mathcal{P}}^{4}\}\cup{\mathbb{L}}$ :: By (E4) we have $A^{4}\cap XY=XY$ and $A^{4}\cap\overline{XY}\in\{\emptyset,\{w_{y_{2}}^{d_{2}}\}\}$ . As a first observation, $A^{4}\neq A_{i,j}$ because $A_{i,j}\cap XY\neq XY$ .

Suppose that $A^{4}\cap\overline{XY}=\emptyset$ , then $A^{4}=(X\setminus\{x_{1}\})\cup\{y_{2}\}$ , and so $x_{2},y_{2}\in A_{4}$ . Similar to case $\{{\mathcal{P}}_{3}\}\cup{\mathbb{L}}$ , for $A^{\prime}\in\{A,A_{i},A_{j},A_{s}^{*},A_{t}^{*}\}$ we have that $x_{2}$ and $y_{2}$ do not belong to $A^{\prime}$ simultaneously. Thus, $A^{3}\neq A^{\prime}$ .

Suppose now that $A^{4}\cap\overline{XY}=\{w_{y_{2}}^{d_{2}}\}$ . We have $A^{4}\neq A$ because $A\cap\overline{XY}=\emptyset$ . Let $\overline{XY}_{1}:=\{w_{y_{2}}^{d_{2}}\}$ and $\overline{XY}_{2}:=(\overline{XY}(x_{1})\cup\overline{XY}(x_{2})\cup\overline{XY}(y_{1})\cup\overline{XY}(y_{2}))\setminus\overline{XY}_{1}$ . Next, for $A^{\prime}\in\{A_{i},A_{j},A_{s}^{*},A_{t}^{*}\}$ proceed as in the case $\{{\mathcal{P}}^{1}\}\cup{\mathbb{L}}$ to show that $A^{4}\neq A^{\prime}$ .

Summarizing: for $i\in\{1,2,3,4\}$ , we have shown that if ${\mathcal{P}}^{i}$ exists, then ${\mathbb{L}}\cup\{{\mathcal{P}}^{i}\}$ is a set of $\delta=m+1$ pairwise internally disjoint $X-Y$ paths of $F_{k}(T)$ . It remains to show that one of ${\mathcal{P}}^{1},{\mathcal{P}}^{2},{\mathcal{P}}^{3},{\mathcal{P}}^{4}$ exists. We have the following: if (J1) holds, then ${\mathcal{P}}^{1}$ exists; if (J2) holds with $a_{2}<c_{2}$ (resp. $b_{2}<d_{2}$ ), then ${\mathcal{P}}^{2}$ (resp. ${\mathcal{P}}^{1}$ ) exists; if (J3) holds, then ${\mathcal{P}}^{1}$ exists; and if (J4) holds with $a_{1}<c_{1}$ (resp. $b_{2}<d_{2}$ ), then ${\mathcal{P}}^{3}$ (resp. ${\mathcal{P}}^{4}$ ) exists. $\triangle$

Clearly, the proof of Claim 2.8 finishes the proof of Lemma 2.1, which implies Theorem 1. ∎

3 Concluding remarks

The trees and the complete graphs are two families of graphs which are extremely distinct from the point of view of the connectivity. Here we have shown that if $G$ is a tree, then $\kappa(F_{k}(G))=\lambda(F_{k}(G))=\delta(F_{k}(G))$ . Surprisingly, these same equalities hold for the case of the complete graph. More precisely, from Leaños and Trujillo-Negrete (2018) and Leaños and Ndjatchi (2021) we know that the connectivity and the edge-connectivity of $F_{k}(K_{n})$ are equal to $\delta(F_{k}(K_{n}))$ the minimum degree of $F_{k}(K_{n})$ . However, these equalities do not hold in general. For instance, it is not hard to see that for the graph $H$ of Figure 7 we have $\kappa(F_{2}(H))=m-1=\lambda(F_{2}(H))$ and $\delta(F_{2}(H))=2(m-2)$ .

On the other hand, based on computational experimentation and on some analytic approaches we have the following conjecture.

Conjecture 3.1.

If $G$ is a connected graph with girth at least five, then $\kappa(F_{k}(G))=\delta(F_{k}(G))$ , for each $k\in\{2,3,\ldots,n-2\}$ .

Acknowledgements.

This work was initiated at the 3rd Reunion of Optimization, Mathematics, and Algorithms (ROMA 2019), held in Mexico city in August 2019. We thank the participants for providing a fruitful research environment. We specially thank Birgit Vogtenhuber and Daniel Perz for various helpful and insightful discussions.

References

Alavi (2015) S. H. Alavi. A generalisation of Johnson graphs with an application to triple factorisations. Discrete Math., 338(11):2026–2036, 2015.
Alavi et al. (1991) Y. Alavi, M. Behzad, P. Erdős, and D. R. Lick. Double vertex graphs. J. Combin. Inform. System Sci., 16(1):37–50, 1991.
Alzaga et al. (2010) A. Alzaga, R. Iglesias, and R. Pignol. Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements. J. Combin. Theory Ser. B, 100(6):671–682, 2010.
Audenaert et al. (2007) K. Audenaert, C. Godsil, G. Royle, and T. Rudolph. Symmetric squares of graphs. J. Combin. Theory Ser. B, 97(1):74–90, 2007.
Barghi and Ponomarenko (2009) A. R. Barghi and I. Ponomarenko. Non-isomorphic graphs with cospectral symmetric powers. Electron. J. Combin., 16(1):Research Paper 120, 14, 2009.
(6) A. E. Brouwer and T. Etzion. Some new distance-4 constant weight codes. Adv. Math. Commun., 5(3):417–424.
Carballosa et al. (2017) W. Carballosa, R. Fabila-Monroy, J. Leaños, and L. M. Rivera. Regularity and planarity of token graphs. Discuss. Math. Graph Theory, 37(3):573–586, 2017.
de Alba et al. (2017) H. de Alba, W. Carballosa, D. Duarte, and L. M. Rivera. Cohen-Macaulayness of triangular graphs. Bull. Math. Soc. Sci. Math. Roumanie (N.S.), 60(108)(2):103–112, 2017.
Etzion and Bitan (1996) T. Etzion and S. Bitan. On the chromatic number, colorings, and codes of the Johnson graph. Discrete Appl. Math., 70(2):163–175, 1996.
Fabila-Monroy et al. (2012) R. Fabila-Monroy, D. Flores-Peñaloza, C. Huemer, F. Hurtado, J. Urrutia, and D. R. Wood. Token graphs. Graphs Combin., 28(3):365–380, 2012.
Gómez Soto et al. (2018) J. M. Gómez Soto, J. Leaños, L. M. Ríos-Castro, and L. M. Rivera. The packing number of the double vertex graph of the path graph. Discrete Appl. Math., 247:327–340, 2018.
Ito et al. (2011) T. Ito, E. D. Demaine, N. J. A. Harvey, C. H. Papadimitriou, M. Sideri, R. Uehara, and Y. Uno. On the complexity of reconfiguration problems. Theoret. Comput. Sci., 412(12):1054–1065, 2011.
Johns (1988) G. L. Johns. Generalized distance in graphs. ProQuest LLC, Ann Arbor, MI, 1988. Thesis (Ph.D.)–Western Michigan University.
Leaños and Trujillo-Negrete (2018) J. Leaños and A. L. Trujillo-Negrete. The connectivity of token graphs. Graphs Combin., 34(4):777–790, 2018.
Leaños and Ndjatchi (2021) J. Leaños and C. Ndjatchi. The edge-connectivity of token graphs. Graphs Combin., 37(3):1013–1023, 2021.
Ouyang (2019) Y. Ouyang. Computing spectral bounds of the Heisenberg ferromagnet from geometric considerations. J. Math. Phys., 60(7):071901, 18, 2019.
Riyono (2007) H. Riyono. Hamiltonicity of the graph $G(n,k)$ of the Johnson scheme. Jurnal Informatika, 3(1):41– 47, 2007.
Rudolph (2002) T. Rudolph. Constructing physically intuitive graph invariants. eprint arXiv:quant-ph/0206068, 2002.
Terwilliger (1986) P. Terwilliger. The Johnson graph $J(d,r)$ is unique if $(d,r)\not=(2,8)$ . Discrete Math., 58(2):175–189, 1986.
Yamanaka et al. (2015) K. Yamanaka, E. D. Demaine, T. Ito, J. Kawahara, M. Kiyomi, Y. Okamoto, T. Saitoh, A. Suzuki, K. Uchizawa, and T. Uno. Swapping labeled tokens on graphs. Theoret. Comput. Sci., 586:81–94, 2015.
Zhu et al. (1992) B. W. Zhu, J. Liu, D. R. Lick, and Y. Alavi. $n$ -tuple vertex graphs. Congr. Numer., 89:97–106, 1992.

On the Connectivity of Token Graphs of Trees

Abstract

keywords:

1 Introduction

Theorem 1.

1.1 Constructing Paths of Fk​(G)F_{k}(G) from Paths of GG

1.2 Some basic facts

Proposition 1.1.

Proof.

Proposition 1.2.

Proof.

Proposition 1.3.

Proof.

2 Proof of Theorem 1

Lemma 2.1.

Proof.

2.1 Case 1: |X​Y|=k−1|XY|=k-1

2.1.1 Step 1 of Case 1

Claim 2.2.

2.1.2 Step 2 of Case 1

Claim 2.3.

Claim 2.4.

2.2 Case 2: |X​Y|=k−2|XY|=k-2

Observation 2.5.

2.2.1 Step 1 of Case 2

Claim 2.6.

2.2.2 Step 2 of Case 2

Claim 2.7.

Claim 2.8.

3 Concluding remarks

Conjecture 3.1.

Acknowledgements.

References

1.1 Constructing Paths of $F_{k}(G)$ from Paths of $G$

2.1 Case 1: $|XY|=k-1$

2.2 Case 2: $|XY|=k-2$