# Paired $(n-1)$-to-$(n-1)$ Disjoint Path Covers in Bipartite Transposition-
Like Graphs

Anna Coleman<EMAIL_ADDRESS>Department of Mathematics, Southeastern
University  Gabrielle Fischberg<EMAIL_ADDRESS>Department of
Mathematics, Tufts University  Charles Gong<EMAIL_ADDRESS>Department of Mathematical Sciences, Carnegie Mellon University  Joshua
Harrington<EMAIL_ADDRESS>Department of Mathematics, Cedar
Crest College  Tony W. H. Wong<EMAIL_ADDRESS>Department of Mathematics,
Kutztown University of Pennsylvania

###### Abstract

A paired $k$-to-$k$ disjoint path cover of a graph $G$ is a collection of
pairwise disjoint path subgraphs $P_{1},P_{2},\dotsc,P_{k}$ such that each
$P_{i}$ has prescribed vertices $s_{i}$ and $t_{i}$ as endpoints and the union
of $P_{1},P_{2},\dotsc,P_{k}$ contains all vertices of $G$. In this paper, we
introduce bipartite transposition-like graphs, which are inductively
constructed from lower ranked bipartite transposition-like graphs. We show
that every rank $n$ bipartite transposition-like graph $G$ admit a paired
$(n-1)$-to-$(n-1)$ disjoint path cover for all choices of
$S=\\{s_{1},s_{2},\dotsc,s_{n-1}\\}$ and $T=\\{t_{1},t_{2},\dotsc,t_{n-1}\\}$,
provided that $S$ is in one partite set of $G$ and $T$ is in the other.
MSC: (Primary) 05C45; (Secondary) 05C70, 05C75.
Keywords: Disjoint path covers, transposition graphs, Hamiltonian laceable.

##  1 Introduction

For any positive integer $n$, let $[n]$ denote the set $\\{1,2,\dotsc,n\\}$.
Given a graph $G$, let $S=\\{s_{1},s_{2},\dotsc,s_{k}\\}$ and
$T=\\{t_{1},t_{2},\dotsc,t_{k}\\}$ be two disjoint $k$-subsets of $V(G)$. A
_paired $k$-to-$k$ disjoint path cover_ (sometimes abbreviated as _$k$ -PDPC_)
of $G$ is a collection of path subgraphs $P_{1},P_{2},\dotsc,P_{k}$ of $G$
such that $V(P_{1}),V(P_{2}),\dotsc,V(P_{k})$ form a partition of $V(G)$ and
$P_{i}$ has $s_{i}$ and $t_{i}$ as its endpoints for each $i\in[k]$. If $G$
admits a $k$-PDPC for every choice of disjoint $k$-subsets $S$ and $T$, then
$G$ is said to be _paired $k$-to-$k$ disjoint path coverable_. Note that a
paired $1$-to-$1$ disjoint path coverable graph is also said to be
_Hamiltonian-connected_.

If $G$ is bipartite with partite sets $V_{1}$ and $V_{2}$, then $S\cup T$ must
be _balanced_ , i.e.,

$|(S\cup T)\cap V_{1}|-|(S\cup T)\cap V_{2}|=2(|V_{1}|-|V_{2}|),$

in order for a $k$-PDPC to exist in $G$. In particular, if $G$ is an
_equitable_ bipartite graph, i.e., $|V_{1}|=|V_{2}|$, then $S\cup T$ is
balanced if and only if $|(S\cup T)\cap V_{1}|=|(S\cup T)\cap V_{2}|$. A
bipartite graph $G$ is said to be _balanced paired $k$-to-$k$ disjoint path
coverable_ if there is a $k$-PDPC whenever $S\cup T$ is balanced. Another name
for a balanced paired $1$-to-$1$ disjoint path coverable graph is
_Hamiltonian-laceable_.

Due to the following proposition, research in this area often focuses on
finding the largest $k$ for which a graph is paired $k$-to-$k$ disjoint path
coverable or balanced paired $k$-to-$k$ disjoint path coverable.

######  Proposition 1.1.

  1. $(a)$

Let $G$ be paired $k$-to-$k$ disjoint path coverable for some positive integer
$k$. Then $G$ is paired $\ell$-to-$\ell$ disjoint path coverable for all
$\ell\in[k]$.

  2. $(b)$

Let $G$ be balanced paired $k$-to-$k$ disjoint path coverable for some
positive integer $k$. If $G$ is equitable, then $G$ is balanced paired
$\ell$-to-$\ell$ disjoint path coverable for all $\ell\in[k]$.

  3. $(c)$

Let $G$ be an equitable bipartite graph with partite sets $V_{1}$ and $V_{2}$.
If $G$ admits a $k$-PDPC for every choice of $k$-subsets
$\overline{S}\subseteq V_{1}$ and $\overline{T}\subseteq V_{2}$, then for all
$\ell\in[k]$, $G$ admits an $\ell$-PDPC for every choice of $\ell$-subsets
$S\subseteq V_{1}$ and $T\subseteq V_{2}$.

###### Proof.

$(\ref{item:differentk})$ It suffices to show that $G$ is paired
$(k-1)$-to-$(k-1)$ disjoint path coverable. Given two disjoint $(k-1)$-subsets
$S=\\{s_{1},s_{2},\dotsc,s_{k-1}\\}$ and $T=\\{t_{1},t_{2},\dotsc,t_{k-1}\\}$
of $V(G)$, let
$\overline{S}=\\{\overline{s}_{1},\overline{s}_{2},\dotsc,\overline{s}_{k}\\}$
and
$\overline{T}=\\{\overline{t}_{1},\overline{t}_{2},\dotsc,\overline{t}_{k}\\}$
such that $\overline{s}_{i}=s_{i}$ and $\overline{t}_{i}=t_{i}$ for all
$i\in[k-2]$, $\overline{s}_{k-1}=s_{k-1}$, $\overline{t}_{k}=t_{k-1}$, and
$\overline{s}_{k},\overline{t}_{k-1}\in V(G)\setminus(S\cup T)$ are two
adjacent vertices. We note that the adjacent pair
$\overline{s}_{k},\overline{t}_{k-1}$ exists since $G$ is paired $k$-to-$k$
disjoint path coverable. By the assumption, $G$ admits a $k$-PDPC
$\overline{P}_{1},\overline{P}_{2},\dotsc,\overline{P}_{k}$ such that
$\overline{P}_{i}$ has endpoints $\overline{s}_{i}$ and $\overline{t}_{i}$ for
each $i\in[k]$. Letting $P_{i}=\overline{P}_{i}$ for all $i\in[k-2]$ and
$P_{k-1}=\overline{P}_{k-1}\cup\overline{t}_{k-1}\overline{s}_{k}\cup\overline{P}_{k}$,
we obtain a desired $(k-1)$-PDPC of $G$.

$(\ref{item:differentkbalanced})\text{ and }(\ref{item:ours})$ A similar proof
as in part $(\ref{item:differentk})$ works by imposing the additional
condition that $\overline{s}_{k}\in V_{1}$ and $\overline{t}_{k-1}\in V_{2}$.
This ensures that $\overline{S}\cup\overline{T}$ is balanced if $S\cup T$ is
balanced. ∎

Paired disjoint path covers is a subject of interest in the literature. They
are particularly important in structured networks, many of which are Cayley
graphs. Let $\mathcal{G}$ be a group and $\mathcal{S}\subseteq\mathcal{G}$
such that $\mathcal{S}$ is closed under inversion. An _undirected Cayley
graph_ $\Gamma(\mathcal{G},\mathcal{S})$ has a vertex set $\mathcal{G}$, and
there is an edge between $\rho,\sigma\in\mathcal{G}$ if and only if
$\rho^{-1}\sigma\in\mathcal{S}$. Of particular note, if
$\mathcal{G}=\mathbb{Z}_{2}^{d}$ with addition as the binary operation and
$\mathcal{S}=\\{\textup{{e}}_{1},\textup{{e}}_{2},\dotsc,\textup{{e}}_{d}\\}$,
where $\textup{{e}}_{i}$ is an ordered $d$-tuple with $1$ in the $i$-th entry
and $0$ everywhere else, then $\Gamma(\mathcal{G},\mathcal{S})$ is a
$d$-dimensional hypercube. More generally, if
$\mathcal{G}=\mathbb{Z}_{m_{1}}\times\mathbb{Z}_{m_{2}}\times\dotsb\times\mathbb{Z}_{m_{d}}$
and
$\mathcal{S}=\\{\pm\textup{{e}}_{1},\pm\textup{{e}}_{2},\dotsc,\pm\textup{{e}}_{d}\\}$,
then $\Gamma(\mathcal{G},\mathcal{S})$ is a $d$-dimensional hypertorus.

Paired disjoint path covers have been studied in hypercubes [1, 3, 4, 6, 7,
8], hypertori [5, 11, 23, 19], and graphs with a similar structure [9, 10, 18,
20, 22, 25]. It is worth mentioning that a variant topic, namely the
_unpaired_ disjoint path covers, has also received a lot of attention [2, 10,
12, 13, 15, 16, 17, 21, 27, 28].

Similar research has been conducted on Cayley graphs other than hypercubes and
hypertori. For example, star graphs, investigated by Park and Kim [24], are
Cayley graphs with $\mathcal{G}$ the symmetric group $S_{n}$ and $\mathcal{S}$
the collection of transpositions $\\{(1,i):2\leq i\leq n\\}$, while Li, Yang,
and Meng [14] as well as Qiao, Sabir, and Meng [26] studied Cayley graphs
generated by transposition trees. If $\mathcal{G}=S_{n}$ and
$\mathcal{T}_{n}=\\{(i,j):1\leq i<j\leq n\\}$, then the Cayley graph
$\Gamma(S_{n},\mathcal{T}_{n})$ is called the _transposition graph of rank
$n$_. Note that for $n\geq 2$, the transposition graph
$\Gamma(S_{n},\mathcal{T}_{n})$ has a structural property that it is composed
of $n$ subgraphs $\Gamma_{1},\Gamma_{2},\dotsc,\Gamma_{n}$, each $\Gamma_{i}$
is an isomorphic copy of $\Gamma(S_{n-1},\mathcal{T}_{n-1})$, and there is a
perfect matching between $\Gamma_{i}$ and $\Gamma_{j}$ for all $1\leq i<j\leq
n$. In view of this, we have the following two definitions.

######  Definition 1.2.

If $G_{1},G_{2},\dotsc,G_{n}$ are $n$ graphs with the same number of vertices,
then $G$ is said to be a _weld_ of $G_{1},G_{2},\dotsc,G_{n}$ if $G$ is
composed of $G_{1},G_{2},\dotsc,G_{n}$ and there is a perfect matching between
$G_{i}$ and $G_{j}$ for all $1\leq i<j\leq n$.

######  Definition 1.3.

A _transposition-like graph of rank $1$_ is a Hamiltonian-connected or
Hamiltonian-laceable graph. For each integer $n\geq 2$, a _transposition-like
graph of rank $n$_ is a weld of $G_{1},G_{2},\dotsc,G_{\ell}$, where $\ell\geq
n$ and each $G_{i}$ is a transposition-like graph of rank $n-1$ with the same
number of vertices.

In this paper, we focus on transposition-like graphs that are bipartite. Note
that these graphs are equitable when the rank is at least $2$, as shown in the
following lemma.

######  Lemma 1.4.

Let $n\geq 2$ be an integer. Then every bipartite transposition-like graph of
rank $n$ is equitable.

###### Proof.

If a graph is bipartite, then all its vertices can be properly colored with
black and white, implying that every subgraph is bipartite. Hence, any rank
$1$ transposition-like subgraph $H$ is Hamiltonian-laceable by Definition 1.3.
If $H$ has an even number of vertices, then $H$ is equitable. If $H$ has an
odd number of vertices, then we claim that the rank $2$ transposition-like
subgraph $K$ containing $H$ is a weld of exactly two rank $1$ transposition-
like subgraphs. To prove this claim, suppose by way of contradiction that $K$
is a weld of $H,H_{2},H_{3},\dotsc,H_{j}$ for some integer $j\geq 3$. We may
assume without loss of generality that there is one more black vertex in $H$
than white. Since there is a perfect matching between $H$ and $H_{i}$ inside
$K$ for all $2\leq i\leq j$, in order to maintain the bipartite property of
$K$, there must be one more white vertex in $H_{i}$ than black. This makes it
impossible to have a perfect matching between $H_{2}$ and $H_{3}$ inside $K$,
which leads to a contradiction. Therefore, $K$ is a weld of $H$ and $H_{2}$,
where $H$ has one more black vertex than white and $H_{2}$ has one more white
vertex than black. As a result, $K$ is equitable. Finally, our result follows
from the simple observation that if $G_{1},G_{2},\dotsc,G_{\ell}$ are
equitable bipartite graphs and their weld $G$ is bipartite, then $G$ is
equitable. ∎

From this lemma, we see that in order for a bipartite transposition-like graph
of rank at least $2$ to have a $k$-PDPC for any positive integer $k$, it is
necessary to have an equal number of black and white vertices in $S\cup T$.
Here is the main theorem that we will prove in Section 2.

######  Theorem 1.5.

Let $n\geq 2$ be an integer, and let $G$ be a bipartite transposition-like
graph of rank $n$ with partite sets $V_{1}$ and $V_{2}$. Assume that during
the welding process to form $G$, every rank $1$ transposition-like graph that
$G$ is built up from is either a single vertex or has an even number of
vertices. Then for every choice of $(n-1)$-subsets $S\subseteq V_{1}$ and
$T\subseteq V_{2}$, $G$ admits an $(n-1)$-PDPC.

Due to Lemma 1.4 and the structure of transposition-like graphs, the key to
prove Theorem 1.5 is to establish the following proposition.

######  Proposition 1.6.

Let $n\geq 3$ be an integer, and let $G_{1},G_{2},\dotsc,G_{\ell}$ be $\ell$
graphs, where $\ell\geq n+1$. Assume that each $G_{j}$

  1. $(a)$

has the same number of vertices with $|V(G_{j})|\geq 4n-2$,

  2. $(b)$

is bipartite and equitable with partite sets $V_{j,1}$ and $V_{j,2}$, and

  3. $(c)$

admits an $(n-1)$-PDPC for all $(n-1)$-subsets $S_{j}\subseteq V_{j,1}$ and
$T_{j}\subseteq V_{j,2}$.

Let $G$ be a weld of $G_{1},G_{2},\dotsc,G_{\ell}$. If $G$ is bipartite with
partite sets $V_{1}$ and $V_{2}$, then for every choice of $n$-subsets
$S\subseteq V_{1}$ and $T\subseteq V_{2}$, $G$ admits an $n$-PDPC.

##  2 Main Results

From this point onward, if $G$ is bipartite with partite sets $V_{1}$ and
$V_{2}$, then we color the vertices in $V_{1}$ black and the vertices in
$V_{2}$ white. Since we assume that $S\subseteq V_{1}$ and $T\subseteq V_{2}$,
every $s_{i}\in S$ is black and every $t_{i}\in T$ is white. For any two
vertices $u$ and $v$, we use $u\sim v$ to denote a path that connects the
endpoints $u$ and $v$. This notation allows $u=v$, and in such case, $u\sim v$
is simply a trivial path with one vertex. Furthermore, for any $v\in V(G)$,
let $N(v)$ denote the set of neighbors of $v$ in $G$, and for any $X\subseteq
V(G)$, let $N(X)$ denote the union of $N(v)$ for all $v\in X$.

######  Lemma 2.1.

Let $G_{1},G_{2},\dotsc,G_{\ell}$ be equitable Hamiltonian-laceable graphs
with the same number of vertices, and let $G$ be a bipartite weld of
$G_{1},G_{2},\dotsc,G_{\ell}$. Let $H$ be a subgraph of $G$ such that $H$ is a
weld of $G_{\sigma_{1}},G_{\sigma_{2}},\dotsc,G_{\sigma_{j}}$ for some
$\\{\sigma_{1},\sigma_{2},\dotsc,\sigma_{j}\\}\subseteq[\ell]$. If $H$ admits
a $k$-PDPC with endpoints $S\cup T\subseteq V(H)$, then $G$ also admits a
$k$-PDPC with endpoints $S\cup T$.

###### Proof.

Without loss of generality, assume that $H$ is a weld of
$G_{1},G_{2},\dotsc,G_{j}$. Let $S=\\{s_{1},s_{2},\dotsc,s_{k}\\}$ and
$T=\\{t_{1},t_{2},\dotsc,t_{k}\\}$ be two disjoint $k$-subsets of $V(H)$, and
let $\overline{P}_{1},\overline{P}_{2},\dotsc,\overline{P}_{k}$ be a $k$-PDPC
of $H$. In particular, let $\overline{P}_{1}=s_{1}\sim u_{j}v_{j}\sim t_{1}$,
where $u_{j}$ or $v_{j}$ are not required to be distinct from $s_{1}$ or
$t_{1}$. Note that $u_{j}$ and $v_{j}$ are of opposite color, so the neighbors
of $u_{j}$ and $v_{j}$ are also of opposite color. For each $j\leq
i\leq\ell-1$, let $u_{i}^{*},v_{i}^{*}\in V(G_{i+1})$ be the neighbors of
$u_{i}$ and $v_{i}$, respectively, and let $\overline{P}_{i+1}=u_{i}^{*}\sim
u_{i+1}v_{i+1}\sim v_{i}^{*}$ be a Hamiltonian path of $G_{i+1}$ that connects
$u_{i}^{*}$ and $v_{i}^{*}$, where $u_{i+1}$ and $v_{i+1}$ are not required to
be distinct from $u_{i}^{*}$ or $v_{i}^{*}$. Let

$P_{1}=\underset{\text{from }\overline{P}_{1}}{\underbrace{s_{1}\sim
u_{j}}}\underset{\text{from }\overline{P}_{j+1}}{\underbrace{u_{j}^{*}\sim
u_{j+1}}}\underset{\text{from }\overline{P}_{j+2}}{\underbrace{u_{j+1}^{*}\sim
u_{j+2}}}\;\dotsb\;\underset{\text{from
}\overline{P}_{\ell}}{\underbrace{u_{\ell-1}^{*}\sim
u_{\ell}}}\underset{\text{from }\overline{P}_{\ell}}{\underbrace{v_{\ell}\sim
v_{\ell-1}^{*}}}\;\dotsb\;\underset{\text{from
}\overline{P}_{j+1}}{\underbrace{v_{j+1}\sim v_{j}^{*}}}\underset{\text{from
}\overline{P}_{1}}{\underbrace{v_{j}\sim t_{1}}}$

and $P_{i}=\overline{P}_{i}$ for $2\leq i\leq k$. Then
$P_{1},P_{2},\dotsc,P_{k}$ is a $k$-PDPC of $G$.∎

Next, we are going to prove Proposition 1.6, which provides the inductive step
for the proof of Theorem 1.5.

###### Proof of Proposition 1.6.

Let $S=\\{s_{1},s_{2},\dotsc,s_{n}\\}\subseteq V_{1}$ and
$T=\\{t_{1},t_{2},\dotsc,t_{n}\\}\subseteq V_{2}$ be $n$-subsets of $V(G)$.
For each $j\in[\ell]$, let $S_{j}=V(G_{j})\cap S$, $T_{j}=V(G_{j})\cap T$,
$S_{j}^{\prime}=\\{s_{i}\in S_{j}:t_{i}\notin T_{j}\\}$,
$S_{j}^{\prime\prime}=\\{s_{i}\in S_{j}:t_{i}\in T_{j}\\}$,
$T_{j}^{\prime}=\\{t_{i}\in T_{j}:s_{i}\notin S_{j}\\}$,
$T_{j}^{\prime\prime}=\\{t_{i}\in T_{j}:s_{i}\in S_{j}\\}$, and
$w_{j}=|\\{i\in[n]:V(G_{j})\cap\\{s_{i},t_{i}\\}\neq\emptyset\\}|$. Note that
$|S_{j}^{\prime\prime}|=|T_{j}^{\prime\prime}|$ and
$|S_{j}|+|T_{j}^{\prime}|=|S_{j}^{\prime}|+|T_{j}|=w_{j}$. Furthermore, let
$\tau:V(G)\to[\ell]$ such that $v\in V(G_{\tau(v)})$ for all $v\in V(G)$. Due
to condition $(\ref{item:cond1})$ on $G_{j}$ for all $j\in[\ell]$, there are
at least $4n-2$ vertices in $V(G_{j})$; by condition $(\ref{item:cond2})$,
there are at least $2n-1$ black and $2n-1$ white vertices in $V(G_{j})$.

  1. Case $1$:

$w_{j}\leq n-1$ for all $j\in[\ell]$.

For each $i\in[n]$ such that $\tau(s_{i})\neq\tau(t_{i})$, we define
$v_{i},u_{i}\in V(G)$ inductively. Initially, let
$\mathcal{V}=\mathcal{U}=\emptyset$. Let $j=\tau(s_{i})$ and
$j^{*}=\tau(t_{i})$. We can define $v_{i}$ to be a white vertex in
$V(G_{j})\setminus\big{(}T_{j}\cup(\mathcal{V}\cap V(G_{j}))\cup
N(S_{j^{*}}\cup(\mathcal{U}\cap V(G_{j^{*}}))\big{)}$ since

$\displaystyle\;\big{|}T_{j}\cup(\mathcal{V}\cap
V(G_{j}))\cup\big{(}N(S_{j^{*}}\cup(\mathcal{U}\cap V(G_{j^{*}}))\cap
V(G_{j})\big{)}\big{|}$ $\displaystyle\leq$
$\displaystyle\;|T_{j}|+|\mathcal{V}\cap
V(G_{j})|+|S_{j^{*}}|+|\mathcal{U}\cap V(G_{j^{*}})|$ $\displaystyle\leq$
$\displaystyle\;|T_{j}|+|S_{j}^{\prime}|-1+|S_{j^{*}}|+|T_{j^{*}}^{\prime}|-1$
$\displaystyle=$ $\displaystyle\;w_{j}+w_{j^{*}}-2$ $\displaystyle\leq$
$\displaystyle\;2(n-1)-2$ $\displaystyle<$ $\displaystyle\;2n-1.$

Let $u_{i}\in V(G_{j^{*}})$ be the unique neighbor of $v_{i}$, and we update
$\mathcal{V}:=\mathcal{V}\cup\\{v_{i}\\}$ and
$\mathcal{U}:=\mathcal{U}\cup\\{u_{i}\\}$.

By condition $(\ref{item:cond3})$ on each $G_{j}$ and Proposition
1.1$(\ref{item:ours})$, there is a $w_{j}$-PDPC in $G_{j}$ with endpoints
$S_{j}^{\prime}\cup\\{u_{i}:t_{i}\in T_{j}^{\prime}\\}\cup
S_{j}^{\prime\prime}$ and $\\{v_{i}:s_{i}\in S_{j}^{\prime}\\}\cup
T_{j}^{\prime}\cup T_{j}^{\prime\prime}$, where paths are of the form
$s_{i}\sim v_{i}$, $u_{i}\sim t_{i}$, or $s_{i}\sim t_{i}$. For each
$i\in[n]$, let

$P_{i}=\underset{G_{\tau(s_{i})}}{\underbrace{s_{i}\sim
v_{i}}}\underset{G_{\tau(t_{i})}}{\underbrace{u_{i}\sim t_{i}}}$

if $s_{i}\in S_{\tau(s_{i})}^{\prime}$ and let

$P_{i}=\underset{G_{\tau(s_{i})}}{\underbrace{s_{i}\sim t_{i}}}$

if $s_{i}\in S_{\tau(s_{i})}^{\prime\prime}$. Then $P_{1},P_{2},\dotsc,P_{n}$
form an $n$-PDPC of the weld of the graphs in $\\{G_{j}:j\in[\ell]\text{ and
}w_{j}>0\\}$, and we obtain a desired $n$-PDPC of $G$ by Lemma 2.1.

  2. Case $2$:

There exists $j\in[\ell]$ such that $S\cup T\subseteq V(G_{j})$.

Without loss of generality, assume that $S\cup T\subseteq V(G_{1})$. By
condition $(\ref{item:cond3})$ on $G_{1}$, there is an $(n-1)$-PDPC
$\overline{P}_{1},\overline{P}_{2},\dotsc,\overline{P}_{n-1}$ in $G_{1}$ with
endpoints $\\{s_{1},s_{2},\dotsc,s_{n-1}\\}$ and
$\\{t_{1},t_{2},\dotsc,t_{n-1}\\}$.

If there exists $i\in[n-1]$ such that the path $s_{i}\sim t_{i}$ contains both
$s_{n}$ and $t_{n}$, then without loss of generality, assume that
$\overline{P}_{1}$ is either $s_{1}\sim v_{1}s_{n}\sim t_{n}u_{1}\sim t_{1}$
or $s_{1}\sim u_{1}t_{n}\sim s_{n}v_{1}\sim t_{1}$, where $u_{1}$ is black,
$v_{1}$ is white, and $u_{1},v_{1}$ are not required to be distinct from
$s_{1},t_{1}$, respectively. Let $u_{1}^{*},v_{1}^{*}\in V(G_{2})$ be the
unique neighbors of $u_{1},v_{1}$, respectively. By condition
$(\ref{item:cond3})$ on $G_{2}$ and Proposition 1.1$(\ref{item:ours})$, there
is a Hamiltonian path in $G_{2}$ with endpoints $v_{1}^{*}$ and $u_{1}^{*}$.
Let $P_{1}$ be either

$\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
v_{1}}}\underset{G_{2}}{\underbrace{v_{1}^{*}\sim
u_{1}^{*}}}\underset{\overline{P}_{1}}{\underbrace{u_{1}\sim
t_{1}}}\quad\text{or}\quad\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
u_{1}}}\underset{G_{2}}{\underbrace{u_{1}^{*}\sim
v_{1}^{*}}}\underset{\overline{P}_{1}}{\underbrace{v_{1}\sim t_{1}}},$

$P_{i}=\overline{P}_{i}$ for $2\leq i\leq n-1$, and

$P_{n}=\underset{\overline{P}_{1}}{\underbrace{s_{n}\sim t_{n}}}.$

Then $P_{1},P_{2},\dotsc,P_{n}$ form an $n$-PDPC of the weld of $G_{1}$ and
$G_{2}$, and we obtain a desired $n$-PDPC of $G$ by Lemma 2.1.

If there does not exist $i\in[n-1]$ such that the path $s_{i}\sim t_{i}$
contains both $s_{n}$ and $t_{n}$, then without loss of generality, assume
that $\overline{P}_{1}=s_{1}\sim u_{1}v_{n}s_{n}v_{1}\sim t_{1}$ and
$\overline{P}_{2}=s_{2}\sim u_{2}t_{n}u_{n}v_{2}\sim t_{2}$, where
$u_{1},u_{2},u_{n}$ are black, $v_{1},v_{2},v_{n}$ are white, and
$u_{1},v_{1},u_{2},v_{2}$ are not required to be distinct from
$s_{1},t_{1},s_{2},t_{2}$, respectively. Let
$u_{1}^{*},u_{2}^{*},v_{1}^{*},v_{2}^{*}\in V(G_{2})$ and
$u_{n}^{*},v_{n}^{*}\in V(G_{3})$ be the unique neighbors of
$u_{1},u_{2},v_{1},v_{2},u_{n},v_{n}$, respectively. By condition
$(\ref{item:cond3})$ on $G_{2}$ and $G_{3}$ and Proposition
1.1$(\ref{item:ours})$, there is a $2$-PDPC in $G_{2}$ with endpoints
$\\{v_{1}^{*},v_{2}^{*}\\}$ and $\\{u_{1}^{*},u_{2}^{*}\\}$ and a Hamiltonian
path in $G_{3}$ with endpoints $v_{n}^{*}$ and $u_{n}^{*}$. Let

$P_{1}=\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
u_{1}}}\underset{G_{2}}{\underbrace{u_{1}^{*}\sim
v_{1}^{*}}}\underset{\overline{P}_{1}}{\underbrace{v_{1}\sim t_{1}}},$
$P_{2}=\underset{\overline{P}_{2}}{\underbrace{s_{2}\sim
u_{2}}}\underset{G_{2}}{\underbrace{u_{2}^{*}\sim
v_{2}^{*}}}\underset{\overline{P}_{2}}{\underbrace{v_{2}\sim t_{2}}},$

$P_{i}=\overline{P}_{i}$ for $3\leq i\leq n-1$, and

$P_{n}=\underset{\overline{P}_{1}}{\underbrace{s_{n}v_{n}}}\underset{G_{3}}{\underbrace{v_{n}^{*}\sim
u_{n}^{*}}}\underset{\overline{P}_{2}}{\underbrace{u_{n}t_{n}}}.$

Then $P_{1},P_{2},\dotsc,P_{n}$ form an $n$-PDPC of the weld of $G_{1}$,
$G_{2}$, and $G_{3}$, and we obtain a desired $n$-PDPC of $G$ by Lemma 2.1.

  3. Case $3$:

There exist $j_{1},j_{2}\in[\ell]$, where $j_{1}\neq j_{2}$, such that
$S\subseteq V(G_{j_{1}})$ and $T\subseteq V(G_{j_{2}})$.

Without loss of generality, assume that $S\subseteq V(G_{1})$ and $T\subseteq
V(G_{2})$. Let $v_{1},v_{2},\dotsc,v_{n-1}\in V(G_{1})$ be distinct white
vertices. By condition $(\ref{item:cond3})$ on $G_{1}$, there is an
$(n-1)$-PDPC $\overline{P}_{1},\overline{P}_{2},\dotsc,\overline{P}_{n-1}$ in
$G_{1}$ with endpoints $\\{s_{1},s_{2},\dotsc,s_{n-1}\\}$ and
$\\{v_{1},v_{2},\dotsc,v_{n-1}\\}$. Without loss of generality, assume that
$\overline{P}_{1}$ contains $s_{n}$, i.e., $\overline{P}_{1}=s_{1}\sim
v_{n}s_{n}\sim v_{1}$, where $v_{n}$ is white. Rename the vertices $v_{1}$ and
$v_{n}$ as $v_{n}$ and $v_{1}$, respectively, so $\overline{P}_{1}=s_{1}\sim
v_{1}s_{n}\sim v_{n}$. Let $v_{1}^{*},v_{2}^{*},\dotsc,v_{n-1}^{*}\in
V(G_{2})$ be the unique neighbors of $v_{1},v_{2},\dotsc,v_{n-1}$,
respectively. By condition $(\ref{item:cond3})$ on $G_{2}$, there is an
$(n-1)$-PDPC $\widehat{P}_{1},\widehat{P}_{2},\dotsc,\widehat{P}_{n-1}$ in
$G_{2}$ with endpoints $\\{v_{1}^{*},v_{2}^{*},\dotsc,v_{n-1}^{*}\\}$ and
$\\{t_{1},t_{2},\dotsc,t_{n-1}\\}$. Again without loss of generality, assume
that $\widehat{P}_{1}$ contains $t_{n}$, i.e., $\widehat{P}_{1}=v_{1}^{*}\sim
u_{0}t_{n}u_{n}v_{0}\sim t_{1}$, where $u_{0}$ and $u_{n}$ are black, $v_{0}$
is white, and $u_{0},v_{0}$ are not required to be distinct from
$v_{1}^{*},t_{1}$, respectively. Let $u_{0}^{*},v_{0}^{*}\in V(G_{3})$ and
$u_{n}^{*},v_{n}^{*}\in V(G_{4})$ be the unique neighbors of
$u_{0},v_{0},u_{n},v_{n}$, respectively. By condition $(\ref{item:cond3})$ on
$G_{3}$ and $G_{4}$ together with Proposition 1.1$(\ref{item:ours})$, there is
a Hamiltonian path of $G_{3}$ with endpoints $v_{0}^{*}$ and $u_{0}^{*}$ and a
Hamiltonian path of $G_{4}$ with endpoints $v_{n}^{*}$ and $u_{n}^{*}$. Let

$P_{1}=\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
v_{1}}}\underset{\widehat{P}_{1}}{\underbrace{v_{1}^{*}\sim
u_{0}}}\underset{G_{3}}{\underbrace{u_{0}^{*}\sim
v_{0}^{*}}}\underset{\widehat{P}_{1}}{\underbrace{v_{0}\sim t_{1}}},$
$P_{i}=\underset{\overline{P}_{i}}{\underbrace{s_{i}\sim
v_{i}}}\underset{\widehat{P}_{i}}{\underbrace{v_{i}^{*}\sim t_{i}}}$

for $2\leq i\leq n-1$, and

$P_{n}=\underset{\overline{P}_{1}}{\underbrace{s_{n}\sim
v_{n}}}\underset{G_{4}}{\underbrace{v_{n}^{*}\sim
u_{n}^{*}}}\underset{\widehat{P}_{1}}{\underbrace{u_{n}t_{n}}}.$

Then $P_{1},P_{2},\dotsc,P_{n}$ form an $n$-PDPC of the weld of
$G_{1},G_{2},G_{3},G_{4}$, and we obtain a desired $n$-PDPC of $G$ by Lemma
2.1.

  4. Case $4$:

There exists $j_{0}\in[\ell]$ such that $S\subseteq V(G_{j_{0}})$ or
$T\subseteq V(G_{j_{0}})$ but not both, and $w_{j}\leq n-1$ for all
$j\in[\ell]\setminus\\{j_{0}\\}$.

Without loss of generality, assume that $S\subseteq V(G_{1})$ and $t_{n}\notin
V(G_{1})$. Note that $T_{1}=T_{1}^{\prime\prime}$ and $T_{j}=T_{j}^{\prime}$
for $2\leq j\leq\ell$. For every $s_{i}\in
S_{1}^{\prime}\setminus\\{s_{n}\\}$, let $v_{i}\in V(G_{1})$ be a white vertex
such that $\\{v_{i}:s_{i}\in S_{1}^{\prime}\setminus\\{s_{n}\\}\\}\cup T_{1}$
is an $(n-1)$-subset of $V(G_{1})$. By condition $(\ref{item:cond3})$ on
$G_{1}$, there is an $(n-1)$-PDPC
$\overline{P}_{1},\overline{P}_{2},\dotsc,\overline{P}_{n-1}$ in $G_{1}$ with
endpoints $\\{s_{1},s_{2},\dotsc,s_{n-1}\\}$ and $\\{v_{i}:s_{i}\in
S_{1}^{\prime}\setminus\\{s_{n}\\}\\}\cup T_{1}$, where paths are of the form
$s_{i}\sim v_{i}$ or $s_{i}\sim t_{i}$. Without loss of generality, assume
that the path $\overline{P}_{1}$ contains $s_{n}$.

If $\overline{P}_{1}=s_{1}\sim v_{n}s_{n}\sim v_{1}$ where $v_{n}$ is white,
then rename the vertices $v_{1}$ and $v_{n}$ as $v_{n}$ and $v_{1}$,
respectively, so $\overline{P}_{1}=s_{1}\sim v_{1}s_{n}\sim v_{n}$. For each
$s_{i}\in S_{1}^{\prime}$, let $v_{i}^{*}\in V(G_{\tau(t_{i})})$ be the unique
neighbor of $v_{i}$. By condition $(\ref{item:cond3})$ on $G_{j}$ for $2\leq
j\leq\ell$ and Proposition 1.1$(\ref{item:ours})$, there is a $w_{j}$-PDPC in
$G_{j}$ with endpoints $\\{v_{i}^{*}:t_{i}\in T_{j}\\}$ and $T_{j}$. Let

$P_{i}=\underset{G_{1}}{\underbrace{s_{i}\sim
v_{i}}}\underset{G_{\tau(t_{i})}}{\underbrace{v_{i}^{*}\sim t_{i}}}$

for each $s_{i}\in S_{1}^{\prime}$ and $P_{i}=\overline{P}_{i}$ for each
$s_{i}\in S_{1}^{\prime\prime}$. Then $P_{1},P_{2},\dotsc,P_{n}$ form an
$n$-PDPC of the weld of the graphs in $\\{G_{j}:j\in[\ell]\text{ and
}w_{j}>0\\}$, and we obtain a desired $n$-PDPC of $G$ by Lemma 2.1.

Otherwise, $\overline{P}_{1}=s_{1}\sim u_{0}v_{n}s_{n}v_{0}\sim t_{1}$, where
$u_{0}$ is black, $v_{0}$ and $v_{n}$ are white, and $u_{0},v_{0}$ are not
required to be distinct from $s_{1},t_{1}$, respectively. For each $s_{i}\in
S_{1}^{\prime}$, let $v_{i}^{*}\in V(G_{\tau(t_{i})})$ be the unique neighbor
of $v_{i}$. Since $|T\setminus T_{1}|<n\leq\ell-1$, we can assume without loss
of generality that $T\cap V(G_{\ell})=\emptyset$. Let $u_{0}^{*},v_{0}^{*}\in
V(G_{\ell})$ be the unique neighbors of $u_{0}$ and $v_{0}$, respectively. By
condition $(\ref{item:cond3})$ on $G_{\ell}$ and Proposition
1.1$(\ref{item:ours})$, there is a Hamiltonian path in $G_{\ell}$ with
endpoints $v_{0}^{*}$ and $u_{0}^{*}$. For each $s_{i}\in S_{1}^{\prime}$, let
$v_{i}^{*}\in V(G_{\tau(t_{i})})$ be the unique neighbor of $v_{i}$. By
condition $(\ref{item:cond3})$ on $G_{j}$ for $2\leq j\leq\ell$ and
Proposition 1.1$(\ref{item:ours})$, there is a $w_{j}$-PDPC in $G_{j}$ with
endpoints $\\{v_{i}^{*}:t_{i}\in T_{j}\\}$ and $T_{j}$. Let

$P_{1}=\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
u_{0}}}\underset{G_{\ell}}{\underbrace{u_{0}^{*}\sim
v_{0}^{*}}}\underset{\overline{P}_{1}}{\underbrace{v_{0}\sim t_{1}}},$
$P_{i}=\underset{\overline{P}_{i}}{\underbrace{s_{i}\sim
v_{i}}}\underset{G_{\tau(t_{i})}}{\underbrace{v_{i}^{*}\sim t_{i}}}$

for each $s_{i}\in S_{1}^{\prime}\setminus\\{s_{n}\\}$,
$P_{i}=\overline{P}_{i}$ for each $s_{i}\in
S_{1}^{\prime\prime}\setminus\\{s_{1}\\}$, and

$P_{n}=\underset{\overline{P}_{1}}{\underbrace{s_{n}v_{n}}}\underset{G_{\tau(t_{n})}}{\underbrace{v_{n}^{*}\sim
t_{n}}}.$

Then $P_{1},P_{2},\dotsc,P_{n}$ form an $n$-PDPC of the weld of the graphs in
$\\{G_{j}:j\in[\ell]\text{ and }w_{j}>0\\}\cup\\{G_{\ell}\\}$, and we obtain a
desired $n$-PDPC of $G$ by Lemma 2.1.

  5. Case $5$:

There exists $j_{0}\in[\ell]$ such that $w_{j_{0}}=n$, $S\nsubseteq
V(G_{j_{0}})$, $T\nsubseteq V(G_{j_{0}})$, and $w_{j}\leq n-1$ for all
$j\in[\ell]\setminus\\{j_{0}\\}$.

Without loss of generality, assume that $w_{1}=n$. Since $|S_{1}|+|T_{1}|\geq
n\geq 3$, we have $\max(|S_{1}|,|T_{1}|)\geq 2$. Without loss of generality,
assume that $|T_{1}|\geq 2$ and $s_{n}\in S_{1}^{\prime}$. Note that
$S_{j}=S_{j}^{\prime}$ and $T_{j}=T_{j}^{\prime}$ for $2\leq j\leq\ell$.
Similar to Case 1, for each $i\in[n-1]$ such that
$\tau(s_{i})\neq\tau(t_{i})$, we define $v_{i},u_{i}\in V(G)$ inductively.
Initially, let $\mathcal{V}=\mathcal{U}=\emptyset$. Let $j=\tau(s_{i})$ and
$j^{*}=\tau(t_{i})$, where $1\in\\{j,j^{*}\\}$. We can define $v_{i}$ to be a
white vertex in $V(G_{j})\setminus\big{(}T_{j}\cup(\mathcal{V}\cap
V(G_{j}))\cup N(S_{j^{*}}\cup(\mathcal{U}\cap V(G_{j^{*}}))\big{)}$ since

$\displaystyle\;\big{|}T_{j}\cup(\mathcal{V}\cap
V(G_{j}))\cup\big{(}N(S_{j^{*}}\cup(\mathcal{U}\cap V(G_{j^{*}}))\cap
V(G_{j})\big{)}\big{|}$ $\displaystyle\leq$
$\displaystyle\;|T_{j}|+|\mathcal{V}\cap
V(G_{j})|+|S_{j^{*}}|+|\mathcal{U}\cap V(G_{j^{*}})|$ $\displaystyle\leq$
$\displaystyle\;\max(|T_{1}|+|S_{1}^{\prime}|-2+|S_{j^{*}}|+|T_{j^{*}}|-1,\;|T_{j}|+|S_{j}|-1+|S_{1}|+|T_{1}^{\prime}|-1)$
$\displaystyle=$ $\displaystyle\;w_{j}+w_{j^{*}}-2$ $\displaystyle\leq$
$\displaystyle\;2n-3$ $\displaystyle<$ $\displaystyle\;2n-1.$

Let $u_{i}\in V(G_{j^{*}})$ be the unique neighbor of $v_{i}$, and we update
$\mathcal{V}:=\mathcal{V}\cup\\{v_{i}\\}$ and
$\mathcal{U}:=\mathcal{U}\cup\\{u_{i}\\}$.

By condition $(\ref{item:cond3})$ on $G_{1}$, there is an $(n-1)$-PDPC
$\overline{P}_{1},\overline{P}_{2},\dotsc,\overline{P}_{n-1}$ in $G_{1}$ with
endpoints $(S_{1}^{\prime}\setminus\\{s_{n}\\})\cup\\{u_{i}:t_{i}\in
T_{1}^{\prime}\\}\cup S_{1}^{\prime\prime}$ and $\\{v_{i}:s_{i}\in
S_{1}^{\prime}\setminus\\{s_{n}\\}\\}\cup T_{1}^{\prime}\cup
T_{1}^{\prime\prime}$, where paths are of the form $s_{i}\sim v_{i}$,
$u_{i}\sim t_{i}$, or $s_{i}\sim t_{i}$. Without loss of generality, assume
that $\overline{P}_{1}$ contains $s_{n}$. Then $\overline{P}_{1}$ is either
$s_{1}\sim u_{0}v_{n}s_{n}v_{0}\sim v_{1}$, $u_{1}\sim
u_{0}v_{n}s_{n}v_{0}\sim t_{1}$, or $s_{1}\sim u_{0}v_{n}s_{n}v_{0}\sim
t_{1}$, where $u_{0}$ is black, $v_{0}$ and $v_{n}$ are white, $u_{0}$ is not
required to be distinct from $s_{1}$ or $u_{1}$, and $v_{0}$ is not required
to be distinct from $v_{1}$ or $t_{1}$.

If there exists $j\in[\ell]$ such that $w_{j}=0$, then assume without loss of
generality that $w_{\ell}=0$. Let $u_{0}^{*},v_{0}^{*},v_{n}^{*}\in
V(G_{\ell})$ be the unique neighbors of $u_{0},v_{0},v_{n}$, respectively.
Furthermore, we define $u_{n}$ to be a black vertex in
$V(G_{\tau(t_{n})})\setminus\big{(}S_{\tau(t_{n})}\cup(\mathcal{U}\cap
V(G_{\tau(t_{n})}))\cup N(u_{0}^{*})\big{)}$. Let $u_{n}^{*}\in V(G_{\ell})$
be the unique neighbor of $u_{n}$. By condition $(\ref{item:cond3})$ on each
$G_{j}$ and Proposition 1.1$(\ref{item:ours})$, there is a $w_{j}$-PDPC in
$G_{j}$ for $2\leq j\leq\ell-1$ with endpoints $S_{j}\cup\\{u_{i}:t_{i}\in
T_{j}\\}$ and $\\{v_{i}:s_{i}\in S_{j}\\}\cup T_{j}$, where paths are of the
form $s_{i}\sim v_{i}$ or $u_{i}\sim t_{i}$, and there is a $2$-PDPC in
$G_{\ell}$ with endpoints $\\{v_{0}^{*},v_{n}^{*}\\}$ and
$\\{u_{0}^{*},u_{n}^{*}\\}$. Let $P_{1}$ be either

$\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
u_{0}}}\underset{G_{\ell}}{\underbrace{u_{0}^{*}\sim
v_{0}^{*}}}\underset{\overline{P}_{1}}{\underbrace{v_{0}\sim
v_{1}}}\underset{G_{\tau(t_{1})}}{\underbrace{u_{1}\sim t_{1}}},$
$\underset{G_{\tau(s_{1})}}{\underbrace{s_{1}\sim
v_{1}}}\underset{\overline{P}_{1}}{\underbrace{u_{1}\sim
u_{0}}}\underset{G_{\ell}}{\underbrace{u_{0}^{*}\sim
v_{0}^{*}}}\underset{\overline{P}_{1}}{\underbrace{v_{0}\sim t_{1}}},$

or

$\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
u_{0}}}\underset{G_{\ell}}{\underbrace{u_{0}^{*}\sim
v_{0}^{*}}}\underset{\overline{P}_{1}}{\underbrace{v_{0}\sim t_{1}}}.$

Let

$P_{i}=\underset{G_{\tau(s_{i})}}{\underbrace{s_{i}\sim
v_{i}}}\underset{G_{\tau(t_{i})}}{\underbrace{u_{i}\sim t_{i}}}$

if $s_{i}\in S_{1}^{\prime}\setminus\\{s_{n}\\}$ or $t_{i}\in T_{1}^{\prime}$,
$P_{i}=\overline{P}_{i}$ if $s_{i}\in S_{1}^{\prime\prime}$, and

$P_{n}=\underset{\overline{P}_{1}}{\underbrace{s_{n}v_{n}}}\underset{G_{\ell}}{\underbrace{v_{n}^{*}\sim
u_{n}^{*}}}\underset{G_{\tau(t_{n})}}{\underbrace{u_{n}\sim t_{n}}}.$

Then $P_{1},P_{2},\dotsc,P_{n}$ form an $n$-PDPC of the weld of the graphs in
$\\{G_{j}:j\in[\ell]\text{ and }w_{j}>0\\}\cup\\{G_{\ell}\\}$, and we obtain a
desired $n$-PDPC of $G$ by Lemma 2.1.

If $w_{j}>0$ for all $j\in[\ell]$, then since $|(S\cup T)\setminus(S_{1}\cup
T_{1})|\leq n\leq\ell-1$, we know that $G_{j}$ contains exactly one vertex
from $(S\cup T)\setminus(S_{1}\cup T_{1})$ for each $2\leq j\leq\ell$.
Furthermore, since $|T_{1}|\geq 2$, there exist $2\leq j_{1}<j_{2}\leq\ell$
such that $T_{j_{1}}=T_{j_{2}}=\emptyset$, so we may assume without loss of
generality that $T_{2}=\emptyset$ and $S_{2}=\\{s_{2}\\}$. Let $u_{0}^{*}\in
V(G_{2})$ and $v_{0}^{*},v_{n}^{*}\in V(G_{\tau(t_{n})})$ be the unique
neighbors of $u_{0},v_{0},v_{n}$, respectively. Note that $u_{0}^{*}\neq
v_{2}$ since $v_{2}$ is a neighbor of $u_{2}\in G_{1}$ and $u_{2}\neq u_{0}$.
We define $x_{0}$ to be a black vertex in
$V(G_{2})\setminus\big{(}\\{s_{2}\\}\cup N(t_{n})\big{)}$. Let $y_{0}\in
V(G_{\tau(t_{n})})$ be the unique neighbor of $x_{0}$. By condition
$(\ref{item:cond3})$ on each $G_{j}$ and Proposition 1.1$(\ref{item:ours})$,
there is a $2$-PDPC in $G_{2}$ with endpoints $\\{s_{2},x_{0}\\}$ and
$\\{v_{2},u_{0}^{*}\\}$, a $2$-PDPC in $G_{\tau(t_{n})}$ with endpoints
$\\{v_{0}^{*},v_{n}^{*}\\}$ and $\\{y_{0},t_{n}\\}$, and a Hamiltonian path in
$G_{j}$ with endpoints $s_{i}$ and $v_{i}$ or endpoints $u_{i}$ and $t_{i}$
for $j\in[\ell]\setminus\\{1,2,\tau(t_{n})\\}$. Let $P_{1}$ be either

$\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
u_{0}}}\underset{G_{2}}{\underbrace{u_{0}^{*}\sim
x_{0}}}\underset{G_{\tau(t_{n})}}{\underbrace{y_{0}\sim
v_{0}^{*}}}\underset{\overline{P}_{1}}{\underbrace{v_{0}\sim
v_{1}}}\underset{G_{\tau(t_{1})}}{\underbrace{u_{1}\sim t_{1}}},$
$\underset{G_{\tau(s_{1})}}{\underbrace{s_{1}\sim
v_{1}}}\underset{\overline{P}_{1}}{\underbrace{u_{1}\sim
u_{0}}}\underset{G_{2}}{\underbrace{u_{0}^{*}\sim
x_{0}}}\underset{G_{\tau(t_{n})}}{\underbrace{y_{0}\sim
v_{0}^{*}}}\underset{\overline{P}_{1}}{\underbrace{v_{0}\sim t_{1}}},$

or

$\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
u_{0}}}\underset{G_{2}}{\underbrace{u_{0}^{*}\sim
x_{0}}}\underset{G_{\tau(t_{n})}}{\underbrace{y_{0}\sim
v_{0}^{*}}}\underset{\overline{P}_{1}}{\underbrace{v_{0}\sim t_{1}}}.$

Let

$P_{i}=\underset{G_{\tau(s_{i})}}{\underbrace{s_{i}\sim
v_{i}}}\underset{G_{\tau(t_{i})}}{\underbrace{u_{i}\sim t_{i}}}$

for $2\leq i\leq n-1$ and

$P_{n}=\underset{\overline{P}_{1}}{\underbrace{s_{n}v_{n}}}\underset{G_{\tau(t_{n})}}{\underbrace{v_{n}^{*}\sim
t_{n}}}.$

Then $P_{1},P_{2},\dotsc,P_{n}$ form an $n$-PDPC of $G$.

  6. Case $6$:

There exist $j_{1},j_{2}\in[\ell]$, where $j_{1}\neq j_{2}$, such that
$w_{j_{1}}=w_{j_{2}}=n$ and $S\nsubseteq V(G_{j_{1}})$.

Without loss of generality, assume that $w_{1}=w_{2}=n$ and $s_{n}\in
S_{1}^{\prime}$. Note that $S_{j}=S_{j}^{\prime}$ and $T_{j}=T_{j}^{\prime}$
for $j\in\\{1,2\\}$. Similar to Case 1, for each $i\in[n-1]$, we define
$v_{i},u_{i}\in V(G)$ inductively. Initially, let
$\mathcal{V}=\mathcal{U}=\emptyset$. Let $j=\tau(s_{i})$ and
$j^{*}=\tau(t_{i})$, where $\\{j,j^{*}\\}=\\{1,2\\}$. Let $v_{i}$ be a white
vertex in $V(G_{j})\setminus\big{(}T_{j}\cup(\mathcal{V}\cap V(G_{j}))\cup
N(S_{j^{*}}\cup(\mathcal{U}\cap V(G_{j^{*}}))\big{)}$ and let $u_{i}\in
V(G_{j^{*}})$ be the unique neighbor of $v_{i}$. Note that $\mathcal{V}\cap
V(G_{j})=N(\mathcal{U}\cap V(G_{j^{*}}))\cap V(G_{j})$, so our definition of
$v_{i}$ and $u_{i}$ is valid since

$\displaystyle\;\big{|}T_{j}\cup(\mathcal{V}\cap
V(G_{j}))\cup\big{(}N(S_{j^{*}}\cup(\mathcal{U}\cap V(G_{j^{*}}))\cap
V(G_{j})\big{)}\big{|}$ $\displaystyle\leq$
$\displaystyle\;|T_{j}|+|\mathcal{V}\cap V(G_{j})|+|S_{j^{*}}|$
$\displaystyle\leq$
$\displaystyle\;\max(|T_{1}|+|S_{1}|-2+|S_{2}|,\;|T_{2}|+|S_{2}|-1+|S_{1}|)$
$\displaystyle\leq$ $\displaystyle\;\max(n-2+n-1,\;n-1+n-1)$ $\displaystyle=$
$\displaystyle\;2n-2$ $\displaystyle<$ $\displaystyle\;2n-1.$

After each $v_{i}$ and $u_{i}$ are defined, we update
$\mathcal{V}:=\mathcal{V}\cup\\{v_{i}\\}$ and
$\mathcal{U}:=\mathcal{U}\cup\\{u_{i}\\}$.

By condition $(\ref{item:cond3})$ on $G_{1}$, there is an $(n-1)$-PDPC
$\overline{P}_{1},\overline{P}_{2},\dotsc,\overline{P}_{n-1}$ in $G_{1}$ with
endpoints $(S_{1}\setminus\\{s_{n}\\})\cup\\{u_{i}:t_{i}\in T_{1}\\}$ and
$\\{v_{i}:s_{i}\in S_{1}\setminus\\{s_{n}\\}\\}\cup T_{1}$, where paths are of
the form $s_{i}\sim v_{i}$ or $u_{i}\sim t_{i}$. Without loss of generality,
assume that $\overline{P}_{1}$ contains $s_{n}$.

If $\overline{P}_{1}=s_{1}\sim v_{n}s_{n}\sim v_{1}$ where $v_{n}$ is white,
then rename the vertices $v_{1},v_{n},u_{1}$ as $v_{n},v_{1},u_{n}$,
respectively, so $\overline{P}_{1}=s_{1}\sim v_{1}s_{n}\sim v_{n}$. By
condition $(\ref{item:cond3})$ on $G_{2}$, there is an $(n-1)$-PDPC
$\widehat{P}_{2},\widehat{P}_{3},\dotsc,\widehat{P}_{n}$ in $G_{2}$ with
endpoints $S_{2}\cup\\{u_{i}:t_{i}\in T_{2}\setminus\\{t_{1}\\}\\}$ and
$\\{v_{i}:s_{i}\in S_{2}\\}\cup(T_{2}\setminus\\{t_{1}\\})$, where paths are
of the form $s_{i}\sim v_{i}$ or $u_{i}\sim t_{i}$. Without loss of
generality, assume that $\widehat{P}_{2}$ contains $t_{1}$. Let
$\widehat{P}_{2}$ be either $s_{2}\sim x_{2}t_{1}u_{1}y_{2}\sim v_{2}$ or
$u_{2}\sim x_{2}t_{1}u_{1}y_{2}\sim t_{2}$, where $u_{1}$ and $x_{2}$ are
black, $y_{2}$ is white, $x_{2}$ is not required to be distinct from $s_{2}$
or $u_{2}$, and $y_{2}$ is not required to be distinct from $v_{2}$ or
$t_{2}$. Let $u_{1}^{*},v_{1}^{*}\in V(G_{3})$ and $x_{2}^{*},y_{2}^{*}\in
V(G_{4})$ be the unique neighbors of $u_{1},v_{1},x_{2},y_{2}$, respectively.
By condition $(\ref{item:cond3})$ on $G_{3}$ and $G_{4}$ together with
Proposition 1.1$(\ref{item:ours})$, there is a Hamiltonian path of $G_{3}$
with endpoints $v_{1}^{*}$ and $u_{1}^{*}$ and a Hamiltonian path of $G_{4}$
with endpoints $y_{2}^{*}$ and $x_{2}^{*}$. Let

$P_{1}=\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
v_{1}}}\underset{G_{3}}{\underbrace{v_{1}^{*}\sim
u_{1}^{*}}}\underset{\widehat{P}_{2}}{\underbrace{u_{1}t_{1}}},$

$P_{2}$ be either

$\underset{\widehat{P}_{2}}{\underbrace{s_{2}\sim
x_{2}}}\underset{G_{4}}{\underbrace{x_{2}^{*}\sim
y_{2}^{*}}}\underset{\widehat{P}_{2}}{\underbrace{y_{2}\sim
v_{2}}}\underset{\overline{P}_{2}}{\underbrace{u_{2}\sim
t_{2}}}\quad\text{or}\quad\underset{\overline{P}_{2}}{\underbrace{s_{2}\sim
v_{2}}}\underset{\widehat{P}_{2}}{\underbrace{u_{2}\sim
x_{2}}}\underset{G_{4}}{\underbrace{x_{2}^{*}\sim
y_{2}^{*}}}\underset{\widehat{P}_{2}}{\underbrace{y_{2}\sim t_{2}}},$

and

$P_{i}=\underset{G_{\tau(s_{i})}}{\underbrace{s_{i}\sim
v_{i}}}\underset{G_{\tau(t_{i})}}{\underbrace{u_{i}\sim t_{i}}}$

for $3\leq i\leq n$. Then $P_{1},P_{2},\dotsc,P_{n}$ form an $n$-PDPC of the
weld of $G_{1},G_{2},G_{3},G_{4}$, and we obtain a desired $n$-PDPC of $G$ by
Lemma 2.1.

It remains to consider that $\overline{P}_{1}=u_{1}\sim
x_{0}v_{n}s_{n}y_{0}\sim t_{1}$, where $x_{0}$ is black, $v_{n}$ and $y_{0}$
are white, and $x_{0},y_{0}$ are not required to be distinct from
$u_{1},t_{1}$, respectively. By condition $(\ref{item:cond3})$ on $G_{2}$,
there is an $(n-1)$-PDPC
$\widehat{P}_{1},\widehat{P}_{2},\dotsc,\widehat{P}_{n-1}$ in $G_{2}$ with
endpoints $S_{2}\cup\\{u_{i}:t_{i}\in T_{2}\setminus\\{t_{n}\\}\\}$ and
$\\{v_{i}:s_{i}\in S_{2}\\}\cup(T_{2}\setminus\\{t_{n}\\})$, where paths are
of the form $s_{i}\sim v_{i}$ or $u_{i}\sim t_{i}$. Let $\widehat{P}_{\iota}$
contain $t_{n}$ for some $\iota\in[n-1]$. Let $\widehat{P}_{\iota}$ be either
$s_{\iota}\sim x_{\iota}t_{n}u_{n}y_{\iota}\sim v_{\iota}$ or $u_{\iota}\sim
x_{\iota}t_{n}u_{n}y_{\iota}\sim t_{\iota}$, where $u_{n}$ and $x_{\iota}$ are
black, $y_{\iota}$ is white, $x_{\iota}$ is not required to be distinct from
$s_{\iota}$ or $u_{\iota}$, and $y_{\iota}$ is not required to be distinct
from $v_{\iota}$ or $t_{\iota}$. Let $v_{n}^{*},x_{0}^{*},y_{0}^{*}\in
V(G_{3})$ and $u_{n}^{*},x_{\iota}^{*},y_{\iota}^{*}\in V(G_{4})$ be the
unique neighbors of $v_{n},x_{0},y_{0},u_{n},x_{\iota},y_{\iota}$,
respectively. Let $y_{n}$ be a white vertex in
$V(G_{3})\setminus\big{(}\\{x_{0}^{*}\\}\cup N(y_{\iota}^{*})\big{)}$, and let
$x_{n}\in V(G_{4})$ be the unique neighbor of $y_{n}$. By condition
$(\ref{item:cond3})$ on $G_{3}$ and $G_{4}$ together with Proposition
1.1$(\ref{item:ours})$, there is a $2$-PDPC in $G_{3}$ with endpoints
$\\{v_{n}^{*},y_{0}^{*}\\}$ and $\\{y_{n},x_{0}^{*}\\}$ and a $2$-PDPC in
$G_{4}$ with endpoints $\\{x_{n},y_{\iota}^{*}\\}$ and
$\\{u_{n}^{*},x_{\iota}^{*}\\}$. If $\iota=1$, then let

$P_{1}=\underset{\widehat{P}_{1}}{\underbrace{s_{1}\sim
x_{1}}}\underset{G_{4}}{\underbrace{x_{1}^{*}\sim
y_{1}^{*}}}\underset{\widehat{P}_{1}}{\underbrace{y_{1}\sim
v_{1}}}\underset{\overline{P}_{1}}{\underbrace{u_{1}\sim
x_{0}}}\underset{G_{3}}{\underbrace{x_{0}^{*}\sim
y_{0}^{*}}}\underset{\overline{P}_{1}}{\underbrace{y_{0}\sim t_{1}}},$
$P_{i}=\underset{G_{\tau(s_{i})}}{\underbrace{s_{i}\sim
v_{i}}}\underset{G_{\tau(t_{i})}}{\underbrace{u_{i}\sim t_{i}}}$

for $2\leq i\leq n-1$, and

$P_{n}=\underset{\overline{P}_{1}}{\underbrace{s_{n}v_{n}}}\underset{G_{3}}{\underbrace{v_{n}^{*}\sim
y_{n}}}\underset{G_{4}}{\underbrace{x_{n}\sim
u_{n}^{*}}}\underset{\widehat{P}_{1}}{\underbrace{u_{n}t_{n}}};$

if $\iota\neq 1$, then assuming without loss of generality that $\iota=2$, let

$P_{1}=\underset{\widehat{P}_{1}}{\underbrace{s_{1}\sim
v_{1}}}\underset{\overline{P}_{1}}{\underbrace{u_{1}\sim
x_{0}}}\underset{G_{3}}{\underbrace{x_{0}^{*}\sim
y_{0}^{*}}}\underset{\overline{P}_{1}}{\underbrace{y_{0}\sim t_{1}}},$

$P_{2}$ be either

$\underset{\widehat{P}_{2}}{\underbrace{s_{2}\sim
x_{2}}}\underset{G_{4}}{\underbrace{x_{2}^{*}\sim
y_{2}^{*}}}\underset{\widehat{P}_{2}}{\underbrace{y_{2}\sim
v_{2}}}\underset{\overline{P}_{2}}{\underbrace{u_{2}\sim
t_{2}}}\quad\text{or}\quad\underset{\overline{P}_{2}}{\underbrace{s_{2}\sim
v_{2}}}\underset{\widehat{P}_{2}}{\underbrace{u_{2}\sim
x_{2}}}\underset{G_{4}}{\underbrace{x_{2}^{*}\sim
y_{2}^{*}}}\underset{\widehat{P}_{2}}{\underbrace{y_{2}\sim t_{2}}},$
$P_{i}=\underset{G_{\tau(s_{i})}}{\underbrace{s_{i}\sim
v_{i}}}\underset{G_{\tau(t_{i})}}{\underbrace{u_{i}\sim t_{i}}}$

for $3\leq i\leq n-1$, and

$P_{n}=\underset{\overline{P}_{1}}{\underbrace{s_{n}v_{n}}}\underset{G_{3}}{\underbrace{v_{n}^{*}\sim
y_{n}}}\underset{G_{4}}{\underbrace{x_{n}\sim
u_{n}^{*}}}\underset{\widehat{P}_{2}}{\underbrace{u_{n}t_{n}}}.$

Then $P_{1},P_{2},\dotsc,P_{n}$ form an $n$-PDPC of the weld of
$G_{1},G_{2},G_{3},G_{4}$, and we obtain a desired $n$-PDPC of $G$ by Lemma
2.1.∎

Before we prove our main theorem, we provide an equivalent form of Theorem
1.5.

######  Restatement of Theorem 1.5.

Let $n$ be a positive integer, and let $G$ be a bipartite transposition-like
graph of rank $n+1$ with partite sets $V_{1}$ and $V_{2}$. Assume that during
the welding process to form $G$, every rank $1$ transposition-like graph that
$G$ is built up from is either a single vertex or has an even number of
vertices. Then for every choice of $n$-subsets $S\subseteq V_{1}$ and
$T\subseteq V_{2}$, $G$ admits an $n$-PDPC.

###### Proof of Theorem 1.5.

Let $G$ be a weld of $G_{1},G_{2},\dotsc,G_{\ell}$, where $\ell\geq n+1$ and
each $G_{i}$ is a bipartite transposition-like graph of rank $n$ with the same
number of vertices. Note that if $n=3$, then the number of vertices in each
$G_{j}$ needs to be at least $4n-2=10$ in order to satisfy condition
$(\ref{item:cond1})$ in Proposition 1.6, and if $n\geq 4$, then the number of
vertices in each $G_{j}$ will be at least $n!=(n-1)!n\geq 6n>4n-2$. Hence, in
view of Proposition 1.6, it suffices to show the following statements.

  1. $(a)$

If $G$ is of rank $2$, then $G$ is Hamiltonian-laceable.

  2. $(b)$

If $G$ is of rank $3$, then for every choice of $2$-subsets $S\subseteq V_{1}$
and $T\subseteq V_{2}$, $G$ admits a $2$-PDPC.

  3. $(c)$

If $G$ is of rank $4$ and every rank $3$ transposition-like graph that $G$ is
built up from has at most $8$ vertices, then for every choice of $3$-subsets
$S\subseteq V_{1}$ and $T\subseteq V_{2}$, $G$ admits a $3$-PDPC.

We begin by proving $(\ref{item:baserank2})$.

  1. Case $1$:

$|V(G_{j})|=1$ for all $j\in[\ell]$.

Note that $G$ is the complete graph $K_{\ell}$, which is bipartite if and only
if $\ell=2$. Hence, $G=K_{2}$ is Hamiltonian-laceable.

  2. Case $2$:

$|V(G_{j})|$ is even for all $j\in[\ell]$.

Let $S=\\{s\\}$ and $T=\\{t\\}$. If $s,t\in V(G_{j})$ for some $j\in[\ell]$,
then since $G_{j}$ is a bipartite rank $1$ transposition-like graph, by
Definition 1.3, there exists a Hamiltonian path in $G_{j}$ with endpoints $s$
and $t$, and we obtain a desired Hamiltonian path of $G$ by Lemma 2.1.
Otherwise, assume without loss of generality that $s\in V(G_{1})$ and $t\in
V(G_{2})$. Let $v\in V(G_{1})$ be a white vertex and let $u\in V(G_{2})$ be
the unique neighbor of $v$. By Definition 1.3 on $G_{1}$ and $G_{2}$, there is
a Hamiltonian path in $G_{1}$ with endpoints $s$ and $v$ and a Hamiltonian
path in $G_{2}$ with endpoints $u$ and $t$. Then $s\sim vu\sim t$ is a
Hamiltonian path of the weld of $G_{1}$ and $G_{2}$, and we obtain a desired
Hamiltonian path of $G$ by Lemma 2.1.

Next, we provide the proof of $(\ref{item:baserank3})$.

  1. Case $1$:

$w_{j}\leq 1$ for all $j\in[\ell]$.

For each $i\in\\{1,2\\}$ such that $\tau(s_{i})\neq\tau(t_{i})$, let
$j=\tau(s_{i})$ and $j^{*}=\tau(t_{i})$. Let $v_{i}$ be a white vertex in
$V(G_{j})$ and let $u_{i}\in V(G_{j^{*}})$ be the unique neighbor of $v_{i}$.
By the result in part $(\ref{item:baserank2})$ on each $G_{j}$, there is a
Hamiltonian path in $G_{j}$ with endpoints
$S_{j}^{\prime}\cup\\{u_{i}:t_{i}\in T_{j}^{\prime}\\}\cup
S_{j}^{\prime\prime}$ and $\\{v_{i}:s_{i}\in S_{j}^{\prime}\\}\cup
T_{j}^{\prime}\cup T_{j}^{\prime\prime}$, where paths are of the form
$s_{i}\sim v_{i}$, $u_{i}\sim t_{i}$, or $s_{i}\sim t_{i}$. For each
$i\in\\{1,2\\}$, let

$P_{i}=\underset{G_{\tau(s_{i})}}{\underbrace{s_{i}\sim
v_{i}}}\underset{G_{\tau(t_{i})}}{\underbrace{u_{i}\sim t_{i}}}$

if $s_{i}\in S_{\tau(s_{i})}^{\prime}$ and let

$P_{i}=\underset{G_{\tau(s_{i})}}{\underbrace{s_{i}\sim t_{i}}}$

if $s_{i}\in S_{\tau(s_{i})}^{\prime\prime}$. Then $P_{1},P_{2}$ form a
$2$-PDPC of the weld of the graphs in $\\{G_{j}:j\in[\ell]\text{ and
}w_{j}>0\\}$, and we obtain a desired $2$-PDPC of $G$ by Lemma 2.1.

  2. Case $2$:

There exists $j\in[\ell]$ such that $S\cup T\subseteq V(G_{j})$.

Without loss of generality, assume that $S\cup T\subseteq V(G_{1})$. By the
result in part $(\ref{item:baserank2})$ on $G_{1}$, there is a Hamiltonian
path $\overline{P}_{1}$ in $G_{1}$ with endpoints $s_{1}$ and $t_{1}$. Then
$\overline{P}_{1}$ is either $s_{1}\sim v_{1}s_{2}\sim t_{2}u_{1}\sim t_{1}$
or $s_{1}\sim u_{1}t_{2}\sim s_{2}v_{1}\sim t_{1}$, where $u_{1}$ is black,
$v_{1}$ is white, and $u_{1},v_{1}$ are not required to be distinct from
$s_{1},t_{1}$, respectively. Let $u_{1}^{*},v_{1}^{*}\in V(G_{2})$ be the
unique neighbors of $u_{1},v_{1}$, respectively. By the result in part
$(\ref{item:baserank2})$ on $G_{2}$, there is a Hamiltonian path in $G_{2}$
with endpoints $v_{1}^{*}$ and $u_{1}^{*}$. Let $P_{1}$ be either

$\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
v_{1}}}\underset{G_{2}}{\underbrace{v_{1}^{*}\sim
u_{1}^{*}}}\underset{\overline{P}_{1}}{\underbrace{u_{1}\sim
t_{1}}}\quad\text{or}\quad\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
u_{1}}}\underset{G_{2}}{\underbrace{u_{1}^{*}\sim
v_{1}^{*}}}\underset{\overline{P}_{1}}{\underbrace{v_{1}\sim t_{1}}}$

and

$P_{2}=\underset{\overline{P}_{1}}{\underbrace{s_{2}\sim t_{2}}}.$

Then $P_{1},P_{2}$ form a $2$-PDPC of the weld of $G_{1}$ and $G_{2}$, and we
obtain a desired $2$-PDPC of $G$ by Lemma 2.1.

  3. Case $3$:

There exist $j_{1},j_{2}\in[\ell]$, where $j_{1}\neq j_{2}$, such that
$S\subseteq V(G_{j_{1}})$ and $T\subseteq V(G_{j_{2}})$.

Without loss of generality, assume that $S\subseteq V(G_{1})$ and $T\subseteq
V(G_{2})$. Let $v_{1}\in V(G_{1})$ be a white vertex. By the result in part
$(\ref{item:baserank2})$ on $G_{1}$, there is a Hamiltonian path
$\overline{P}_{1}$ in $G_{1}$ with endpoints $s_{1}$ and $v_{1}$. Then
$\overline{P}_{1}=s_{1}\sim v_{2}s_{2}\sim v_{1}$, where $v_{2}$ is white.
Rename the vertices $v_{1}$ and $v_{2}$ as $v_{2}$ and $v_{1}$, respectively,
so $\overline{P}_{1}=s_{1}\sim v_{1}s_{2}\sim v_{2}$. Let
$v_{1}^{*},v_{2}^{*}\in V(G_{2})$ be the unique neighbors of $v_{1},v_{2}$,
respectively. By the result in part $(\ref{item:baserank2})$ on $G_{2}$, there
is a Hamiltonian path $\widehat{P}_{1}$ in $G_{2}$ with endpoints $v_{1}^{*}$
and $t_{1}$. Then $\widehat{P}_{1}$ is either $v_{1}^{*}\sim
v_{0}v_{2}^{*}\sim t_{2}u_{0}\sim t_{1}$ or $v_{1}^{*}\sim u_{0}t_{2}\sim
v_{2}^{*}v_{0}\sim t_{1}$, where $u_{0}$ is black, $v_{0}$ is white, and
$u_{0},v_{0}$ are not required to be distinct from $v_{1}^{*},t_{1}$,
respectively. Let $u_{0}^{*},v_{0}^{*}\in V(G_{3})$ be the unique neighbors of
$u_{0},v_{0}$, respectively. By the result in part $(\ref{item:baserank2})$ on
$G_{3}$, there is a Hamiltonian path in $G_{3}$ with endpoints $v_{0}^{*}$ and
$u_{0}^{*}$. Let $P_{1}$ be either

$\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
v_{1}}}\underset{\widehat{P}_{1}}{\underbrace{v_{1}^{*}\sim
v_{0}}}\underset{G_{3}}{\underbrace{v_{0}^{*}\sim
u_{0}^{*}}}\underset{\widehat{P}_{1}}{\underbrace{u_{0}\sim
t_{1}}}\quad\text{or}\quad\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
v_{1}}}\underset{\widehat{P}_{1}}{\underbrace{v_{1}^{*}\sim
u_{0}}}\underset{G_{3}}{\underbrace{u_{0}^{*}\sim
v_{0}^{*}}}\underset{\widehat{P}_{1}}{\underbrace{v_{0}\sim t_{1}}}$

and

$P_{2}=\underset{\overline{P}_{1}}{\underbrace{s_{2}\sim
v_{2}}}\underset{\widehat{P}_{1}}{\underbrace{v_{2}^{*}\sim t_{2}}}.$

Then $P_{1},P_{2}$ form a $2$-PDPC of the weld of $G_{1},G_{2},G_{3}$, and we
obtain a desired $2$-PDPC of $G$ by Lemma 2.1.

  4. Case $4$:

There exists $j_{0}\in[\ell]$ such that $S\subseteq V(G_{j_{0}})$ or
$T\subseteq V(G_{j_{0}})$ but not both, and $w_{j}\leq 1$ for all
$j\in[\ell]\setminus\\{j_{0}\\}$.

Without loss of generality, assume that $S\subseteq V(G_{1})$ and $t_{2}\notin
V(G_{1})$. If $t_{1}\notin V(G_{1})$, then without loss of generality, assume
that $t_{1}\in V(G_{2})$ and $t_{2}\in V(G_{3})$. Let $v_{1}\in V(G_{1})$ be a
white vertex. By the result in part $(\ref{item:baserank2})$ on $G_{1}$, there
is a Hamiltonian path $\overline{P}_{1}$ in $G_{1}$ with endpoints $s_{1}$ and
$v_{1}$. Then $\overline{P}_{1}=s_{1}\sim v_{2}s_{2}\sim v_{1}$, where $v_{2}$
is white. Rename the vertices $v_{1}$ and $v_{2}$ as $v_{2}$ and $v_{1}$,
respectively, so $\overline{P}_{1}=s_{1}\sim v_{1}s_{2}\sim v_{2}$. Let
$v_{1}^{*}\in V(G_{2})$ and $v_{2}^{*}\in V(G_{3})$ be the unique neighbors of
$v_{1},v_{2}$, respectively. By the result in part $(\ref{item:baserank2})$ on
$G_{2}$ and $G_{3}$, there is a Hamiltonian path in $G_{2}$ with endpoints
$v_{1}^{*}$ and $t_{1}$ and a Hamiltonian path in $G_{3}$ with endpoints
$v_{2}^{*}$ and $t_{2}$. Let

$P_{1}=\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
v_{1}}}\underset{G_{2}}{\underbrace{v_{1}^{*}\sim t_{1}}}$

and

$P_{2}=\underset{\overline{P}_{1}}{\underbrace{s_{2}\sim
v_{2}}}\underset{G_{3}}{\underbrace{v_{2}^{*}\sim t_{2}}}.$

Then $P_{1},P_{2}$ form a $2$-PDPC of the weld of $G_{1},G_{2},G_{3}$, and we
obtain a desired $2$-PDPC of $G$ by Lemma 2.1.

If $t_{1}\in V(G_{1})$, then without loss of generality, assume that $t_{2}\in
V(G_{2})$. By the result in part $(\ref{item:baserank2})$ on $G_{1}$, there is
a Hamiltonian path $\overline{P}_{1}$ in $G_{1}$ with endpoints $s_{1}$ and
$t_{1}$. Let $\overline{P}_{1}=s_{1}\sim u_{1}v_{2}s_{2}v_{1}\sim t_{1}$,
where $u_{1}$ is black, $v_{1}$ is white, and $u_{1},v_{1}$ are not required
to be distinct from $s_{1},t_{1}$, respectively. Let $u_{1}^{*},v_{1}^{*}\in
V(G_{3})$ and $v_{2}^{*}\in V(G_{2})$ be the unique neighbors of
$u_{1},v_{1},v_{2}$, respectively. By the result in part
$(\ref{item:baserank2})$ on $G_{2}$ and $G_{3}$, there is a Hamiltonian path
in $G_{2}$ with endpoints $v_{2}^{*}$ and $t_{2}$ and a Hamiltonian path in
$G_{3}$ with endpoints $v_{1}^{*}$ and $u_{1}^{*}$. Let

$P_{1}=\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
u_{1}}}\underset{G_{3}}{\underbrace{u_{1}^{*}\sim
v_{1}^{*}}}\underset{\overline{P}_{1}}{\underbrace{v_{1}\sim t_{1}}}$

and

$P_{2}=\underset{\overline{P}_{1}}{\underbrace{s_{2}v_{2}}}\underset{G_{2}}{\underbrace{v_{2}^{*}\sim
t_{2}}}.$

Then $P_{1},P_{2}$ form a $2$-PDPC of the weld of $G_{1},G_{2},G_{3}$, and we
obtain a desired $2$-PDPC of $G$ by Lemma 2.1.

  5. Case $5$:

There exists $j_{0}\in[\ell]$ such that $w_{j_{0}}=2$, $S\not\subseteq
V(G_{j_{0}})$, $T\not\subseteq V(G_{j_{0}})$, and $w_{j}\leq 1$ for all
$j\in[\ell]\setminus\\{j_{0}\\}$.

Without loss of generality, assume that $\\{s_{1},t_{2}\\}\subseteq V(G_{1})$,
$t_{1}\in V(G_{2})$, and $s_{2}\in V(G_{3})$. If $|V(G_{j})|=2$ for all
$j\in[\ell]$, then let $V(G_{2})=\\{u,t_{1}\\}$ and $V(G_{3})=\\{s_{2},v\\}$,
where $u$ is black and $v$ is white. Let $P_{1}=s_{1}vut_{1}$ and
$P_{2}=s_{2}t_{2}$. Then $P_{1},P_{2}$ form a $2$-PDPC of the weld of
$G_{1},G_{2},G_{3}$, and we obtain a desired $2$-PDPC of $G$ by Lemma 2.1.

If $|V(G_{j})|>2$ for all $j\in[\ell]$, then by the result in part
$(\ref{item:baserank2})$ on $G_{1}$, there is a Hamiltonian path
$\overline{P}_{1}$ in $G_{1}$ with endpoints $s_{1}$ and $t_{2}$. Let
$\overline{P}_{1}=s_{1}\sim vu\sim t_{2}$, where $u$ is black and $v$ is
white. Let $u^{*}\in V(G_{3})$ and $v^{*}\in V(G_{2})$ be the unique neighbors
of $u$ and $v$, respectively. By the result in part $(\ref{item:baserank2})$
on $G_{2}$ and $G_{3}$, there is a Hamiltonian path in $G_{2}$ with endpoints
$v^{*}$ and $t_{1}$ and a Hamiltonian path in $G_{3}$ with endpoints $s_{2}$
and $u^{*}$. Let

$P_{1}=\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
v}}\underset{G_{2}}{\underbrace{v^{*}\sim t_{1}}}$

and

$P_{2}=\underset{G_{3}}{\underbrace{s_{2}\sim
u^{*}}}\underset{\overline{P}_{1}}{\underbrace{u\sim t_{2}}}.$

Then $P_{1},P_{2}$ form a $2$-PDPC of the weld of $G_{1},G_{2},G_{3}$, and we
obtain a desired $2$-PDPC of $G$ by Lemma 2.1.

  6. Case $6$:

There exist $j_{1},j_{2}\in[\ell]$, where $j_{1}\neq j_{2}$, such that
$w_{j_{1}}=w_{j_{2}}=2$ and $S\not\subseteq V(G_{j_{1}})$.

Without loss of generality, assume that $\\{s_{1},t_{2}\\}\subseteq V(G_{1})$
and $\\{s_{2},t_{1}\\}\subseteq V(G_{2})$. Let $u_{1}\in V(G_{1})$ be the
unique neighbor of $t_{1}$, where $u_{1}$ is not required to be distinct from
$s_{1}$. By the result in part $(\ref{item:baserank2})$ on $G_{1}$ and
$G_{2}$, there is a Hamiltonian path $\overline{P}_{1}$ in $G_{1}$ with
endpoints $s_{1}$ and $t_{2}$ and a Hamiltonian path $\overline{P}_{2}$ in
$G_{2}$ with endpoints $s_{2}$ and $t_{1}$. Let $\overline{P}_{1}=s_{1}\sim
u_{1}v_{2}\sim t_{2}$ and $\overline{P}_{2}=s_{2}\sim u_{2}t_{1}$, where
$u_{2}$ is black, $v_{2}$ is white, and $u_{2},v_{2}$ are not required to be
distinct from $s_{2},t_{2}$, respectively. Let $u_{2}^{*},v_{2}^{*}\in
V(G_{3})$ be the unique neighbors of $u_{2},v_{2}$, respectively. By the
result in part $(\ref{item:baserank2})$ on $G_{3}$, there is a Hamiltonian
path in $G_{3}$ with endpoints $v_{2}^{*}$ and $u_{2}^{*}$. Let

$P_{1}=\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
u_{1}}}\underset{\overline{P}_{2}}{\underbrace{t_{1}}}$

and

$P_{2}=\underset{\overline{P}_{2}}{\underbrace{s_{2}\sim
u_{2}}}\underset{G_{3}}{\underbrace{u_{2}^{*}\sim
v_{2}^{*}}}\underset{\overline{P}_{1}}{\underbrace{v_{2}\sim t_{2}}}.$

Then $P_{1},P_{2}$ form a $2$-PDPC of the weld of $G_{1},G_{2},G_{3}$, and we
obtain a desired $2$-PDPC of $G$ by Lemma 2.1.

Lastly, we prove $(\ref{item:baserank4})$. Since $G_{j}$ is a bipartite
transposition-like graph of rank $3$ for all $j\in[\ell]$, there are at least
$3!=6$ vertices in $V(G_{j})$. By Lemma 1.4, there are at least $3$ black and
$3$ white vertices in $V(G_{j})$.

  1. Case $1$:

$w_{j}\leq 2$ for all $j\in[\ell]$.

The proof of Case 1 in Proposition 1.6 applies due to $2(3-1)-2=2<3$ and the
result in part $(\ref{item:baserank3})$ on each $G_{j}$.

  2. Case $2$:

There exists $j\in[\ell]$ such that $S\cup T\subseteq V(G_{j})$.

The proof of Case 2 in Proposition 1.6 applies due to the result in part
$(\ref{item:baserank3})$ on each $G_{j}$.

  3. Case $3$:

There exist $j_{1},j_{2}\in[\ell]$, where $j_{1}\neq j_{2}$, such that
$S\subseteq V(G_{j_{1}})$ and $T\subseteq V(G_{j_{2}})$.

The proof of Case 3 in Proposition 1.6 applies due to the result in part
$(\ref{item:baserank3})$ on each $G_{j}$.

  4. Case $4$:

There exists $j_{0}\in[\ell]$ such that $S\subseteq V(G_{j_{0}})$ or
$T\subseteq V(G_{j_{0}})$ but not both, and $w_{j}\leq 2$ for all
$j\in[\ell]\setminus\\{j_{0}\\}$.

The proof of Case 4 in Proposition 1.6 applies due to the result in part
$(\ref{item:baserank3})$ on each $G_{j}$.

  5. Case $5$:

There exists $j_{0}\in[\ell]$ such that $w_{j_{0}}=3$, $S\nsubseteq
V(G_{j_{0}})$, $T\nsubseteq V(G_{j_{0}})$, and $w_{j}\leq 2$ for all
$j\in[\ell]\setminus\\{j_{0}\\}$.

Without loss of generality, assume that $\\{s_{1},s_{2},t_{3}\\}\subseteq
V(G_{1})$.

    1. Case $5.$$1$:

$\\{t_{1},t_{2}\\}\cap V(G_{1})\neq\emptyset$.

Without loss of generality, assume that $t_{1}\in V(G_{1})$ and $t_{2}\in
V(G_{2})$. By the result in part $(\ref{item:baserank3})$ on $G_{1}$, there is
a $2$-PDPC $\overline{P}_{1},\overline{P}_{2}$ in $G_{1}$ with endpoints
$\\{s_{1},s_{2}\\}$ and $\\{t_{1},t_{3}\\}$. Let
$\overline{P}_{2}=s_{2}v_{3}\sim t_{3}$, where $v_{3}$ is white and $v_{3}$ is
not required to be distinct from $t_{3}$. If $s_{3}\in V(G_{2})$, then let
$v_{3}^{*}\in V(G_{2})$ be the unique neighbor of $v_{3}$, where $v_{3}^{*}$
is not required to be distinct from $s_{3}$. By the result in part
$(\ref{item:baserank3})$ on $G_{2}$ together with Proposition
1.1$(\ref{item:ours})$, there is a Hamiltonian path $\widehat{P}_{2}$ of
$G_{2}$ with endpoints $s_{3}$ and $t_{2}$. Let $\widehat{P}_{2}=s_{3}\sim
v_{3}^{*}v_{2}\sim t_{2}$, where $v_{2}$ is white and $v_{2}$ is not required
to be distinct from $t_{2}$. Let $u_{2}^{*},v_{2}^{*}\in V(G_{3})$ be the
unique neighbors of $s_{2},v_{2}$, respectively. By the result in part
$(\ref{item:baserank3})$ on $G_{3}$ together with Proposition
1.1$(\ref{item:ours})$, there is a Hamiltonian path of $G_{3}$ with endpoints
$v_{2}^{*}$ and $u_{2}^{*}$. Let $P_{1}=\overline{P}_{1}$,

$P_{2}=\underset{\overline{P}_{2}}{\underbrace{s_{2}}}\underset{G_{3}}{\underbrace{u_{2}^{*}\sim
v_{2}^{*}}}\underset{\widehat{P}_{2}}{\underbrace{v_{2}\sim t_{2}}},$

and

$P_{3}=\underset{\widehat{P}_{2}}{\underbrace{s_{3}\sim
v_{3}^{*}}}\underset{\overline{P}_{2}}{\underbrace{v_{3}\sim t_{3}}}.$

Then $P_{1},P_{2},P_{3}$ form a $3$-PDPC of the weld of $G_{1},G_{2},G_{3}$,
and we obtain a desired $3$-PDPC of $G$ by Lemma 2.1.

If $s_{3}\notin V(G_{2})$, then assume without loss of generality that
$s_{3}\in V(G_{3})$. Let $v_{2},v_{3}^{*}\in V(G_{2})$ be the unique neighbors
of $s_{2},v_{3}$, respectively, where $v_{2}$ is not required to be distinct
from $t_{2}$. By the result in part $(\ref{item:baserank3})$ on $G_{2}$
together with Proposition 1.1$(\ref{item:ours})$, there is a Hamiltonian path
$\widehat{P}_{2}$ of $G_{2}$ with endpoints $v_{3}^{*}$ and $t_{2}$. Let
$\widehat{P}_{2}=v_{3}^{*}\sim u_{3}v_{2}\sim t_{2}$, where $u_{3}$ is black
and $u_{3}$ is not required to be distinct from $v_{3}^{*}$. Let $u_{3}^{*}\in
V(G_{3})$ be the unique neighbor of $u_{3}$. By the result in part
$(\ref{item:baserank3})$ on $G_{3}$ together with Proposition
1.1$(\ref{item:ours})$, there is a Hamiltonian path of $G_{3}$ with endpoints
$s_{3}$ and $u_{3}^{*}$. Let $P_{1}=\overline{P}_{1}$,

$P_{2}=\underset{\overline{P}_{2}}{\underbrace{s_{2}}}\underset{\widehat{P}_{2}}{\underbrace{v_{2}\sim
t_{2}}},$

and

$P_{3}=\underset{G_{3}}{\underbrace{s_{3}\sim
u_{3}^{*}}}\underset{\widehat{P}_{2}}{\underbrace{u_{3}\sim
v_{3}^{*}}}\underset{\overline{P}_{2}}{\underbrace{v_{3}\sim t_{3}}}.$

Then $P_{1},P_{2},P_{3}$ form a $3$-PDPC of the weld of $G_{1},G_{2},G_{3}$,
and we obtain a desired $3$-PDPC of $G$ by Lemma 2.1.

    2. Case $5.$$2$:

$\\{t_{1},t_{2}\\}\cap V(G_{1})=\emptyset$.

Without loss of generality, assume that $s_{3}\in V(G_{2})$. If
$\\{t_{1},t_{2}\\}\cap V(G_{2})\neq\emptyset$, then assume without loss of
generality that $t_{1}\in V(G_{2})$ and $t_{2}\in V(G_{3})$. Let $v_{1}\in
V(G_{1})\setminus(\\{t_{3}\\}\cup N(s_{3}))$ be a white vertex and let
$u_{1}\in V(G_{2})$ be the unique neighbor of $v_{1}$. By the result in part
$(\ref{item:baserank3})$ on $G_{1}$, there is a $2$-PDPC
$\overline{P}_{1},\overline{P}_{2}$ in $G_{1}$ with endpoints
$\\{s_{1},s_{2}\\}$ and $\\{v_{1},t_{3}\\}$. Let
$\overline{P}_{2}=s_{2}v_{3}\sim t_{3}$, where $v_{3}$ is white and $v_{3}$ is
not required to be distinct from $t_{3}$. Let $v_{3}^{*}\in V(G_{3})$ be the
unique neighbor of $v_{3}$. Let $u_{3}\in
V(G_{3})\setminus(\\{v_{3}^{*}\\}\cup N(t_{1}))$ be a black vertex and let
$u_{3}^{*}\in V(G_{2})$ be the unique neighbor of $u_{3}$. By the result in
part $(\ref{item:baserank3})$ on $G_{2}$, there is a $2$-PDPC in $G_{2}$ with
endpoints $\\{u_{1},s_{3}\\}$ and $\\{t_{1},u_{3}^{*}\\}$. Furthermore, by the
result in part $(\ref{item:baserank3})$ on $G_{3}$ together with Proposition
1.1$(\ref{item:ours})$, there is a Hamiltonian path $\widehat{P}_{2}$ of
$G_{3}$ with endpoints $v_{3}^{*}$ and $t_{2}$. Let
$\widehat{P}_{2}=v_{3}^{*}\sim u_{3}v_{2}\sim t_{2}$, where $v_{2}$ is white
and $v_{2}$ is not required to be distinct from $t_{2}$. Let
$u_{2}^{*},v_{2}^{*}\in V(G_{4})$ be the unique neighbors of $s_{2},v_{2}$,
respectively. By the result in part $(\ref{item:baserank3})$ on $G_{4}$
together with Proposition 1.1$(\ref{item:ours})$, there is a Hamiltonian path
of $G_{4}$ with endpoints $v_{2}^{*}$ and $u_{2}^{*}$. Let

$P_{1}=\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
v_{1}}}\underset{G_{2}}{\underbrace{u_{1}\sim t_{1}}},$
$P_{2}=\underset{\overline{P}_{2}}{\underbrace{s_{2}}}\underset{G_{4}}{\underbrace{u_{2}^{*}\sim
v_{2}^{*}}}\underset{\widehat{P}_{2}}{\underbrace{v_{2}\sim t_{2}}},$

and

$P_{3}=\underset{G_{2}}{\underbrace{s_{3}\sim
u_{3}^{*}}}\underset{\widehat{P}_{2}}{\underbrace{u_{3}\sim
v_{3}^{*}}}\underset{\overline{P}_{2}}{\underbrace{v_{3}\sim t_{3}}}.$

Then $P_{1},P_{2},P_{3}$ form a $3$-PDPC of the weld of
$G_{1},G_{2},G_{3},G_{4}$, and we obtain a desired $3$-PDPC of $G$ by Lemma
2.1.

If $\\{t_{1},t_{2}\\}\cap V(G_{2})=\emptyset$, then without loss of
generality, we have either $\\{t_{1},t_{2}\\}\subseteq V(G_{3})$, or $t_{1}\in
V(G_{3})$ and $t_{2}\in V(G_{4})$. If $\\{t_{1},t_{2}\\}\subseteq V(G_{3})$,
then let $v_{1}\in V(G_{1})\setminus\\{t_{3}\\}$ be a white vertex, and let
$u_{1}\in V(G_{3})$ be the unique neighbor of $v_{1}$. By the result in part
$(\ref{item:baserank3})$ on $G_{1}$, there is a $2$-PDPC
$\overline{P}_{1},\overline{P}_{2}$ in $G_{1}$ with endpoints
$\\{s_{1},s_{2}\\}$ and $\\{v_{1},t_{3}\\}$. Let
$\overline{P}_{2}=s_{2}v_{3}\sim t_{3}$, where $v_{3}$ is white and $v_{3}$ is
not required to be distinct from $t_{3}$. Let $v_{3}^{*}\in V(G_{3})$ be the
unique neighbor of $v_{3}$. By the result in part $(\ref{item:baserank3})$ on
$G_{3}$, there is a $2$-PDPC $\widehat{P}_{1},\widehat{P}_{2}$ in $G_{3}$ with
endpoints $\\{u_{1},v_{3}^{*}\\}$ and $\\{t_{1},t_{2}\\}$. Let
$\widehat{P}_{3}=v_{3}^{*}\sim u_{3}t_{2}$, where $u_{3}$ is black and $u_{3}$
is not required to be distinct from $v_{3}^{*}$. Let $u_{3}^{*}\in V(G_{2})$
and $v_{2},u_{2}\in V(G_{4})$ be the unique neighbors of $u_{3},s_{2},t_{2}$,
respectively. By the result in part $(\ref{item:baserank3})$ on $G_{2}$ and
$G_{4}$ together with Proposition 1.1$(\ref{item:ours})$, there is a
Hamiltonian path of $G_{2}$ with endpoints $s_{3}$ and $u_{3}^{*}$ and a
Hamiltonian path of $G_{4}$ with endpoints $u_{2}$ and $v_{2}$. Let

$P_{1}=\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
v_{1}}}\underset{\widehat{P}_{1}}{\underbrace{u_{1}\sim t_{1}}},$
$P_{2}=\underset{\overline{P}_{2}}{\underbrace{s_{2}}}\underset{G_{4}}{\underbrace{v_{2}\sim
u_{2}}}\underset{\widehat{P}_{3}}{\underbrace{t_{2}}},$

and

$P_{3}=\underset{G_{2}}{\underbrace{s_{3}\sim
u_{3}^{*}}}\underset{\widehat{P}_{3}}{\underbrace{u_{3}\sim
v_{3}^{*}}}\underset{\overline{P}_{2}}{\underbrace{v_{3}\sim t_{3}}}.$

Then $P_{1},P_{2},P_{3}$ form a $3$-PDPC of the weld of
$G_{1},G_{2},G_{3},G_{4}$, and we obtain a desired $3$-PDPC of $G$ by Lemma
2.1.

If $t_{1}\in V(G_{3})$ and $t_{2}\in V(G_{4})$, then $v_{1}\in
V(G_{1})\setminus\\{t_{3}\\}$ be a white vertex, and let $u_{1}\in V(G_{3})$
be the unique neighbor of $v_{1}$. By the result in part
$(\ref{item:baserank3})$ on $G_{1}$, there is a $2$-PDPC
$\overline{P}_{1},\overline{P}_{2}$ in $G_{1}$ with endpoints
$\\{s_{1},s_{2}\\}$ and $\\{v_{1},t_{3}\\}$. Let
$\overline{P}_{2}=s_{2}v_{3}\sim t_{3}$, where $v_{3}$ is white and $v_{3}$ is
not required to be distinct from $t_{3}$. Let $v_{2},v_{3}^{*}\in V(G_{4})$ be
the unique neighbor of $s_{2},v_{3}$, respectively, where $v_{2}$ is not
required to be distinct from $t_{2}$. By the result in part
$(\ref{item:baserank3})$ on $G_{4}$ together with Proposition
1.1$(\ref{item:ours})$, there is a Hamiltonian path $\widehat{P}_{2}$ in
$G_{4}$ with endpoints $v_{3}^{*}$ and $t_{2}$. Let
$\widehat{P}_{2}=v_{3}^{*}\sim u_{3}v_{2}\sim t_{2}$, where $u_{3}$ is black
and $u_{3}$ is not required to be distinct from $v_{3}^{*}$. Let $u_{3}^{*}\in
V(G_{2})$ be the unique neighbor of $u_{3}$. By the result in part
$(\ref{item:baserank3})$ on $G_{2}$ and $G_{3}$ together with Proposition
1.1$(\ref{item:ours})$, there is a Hamiltonian path in $G_{2}$ with endpoints
$s_{3}$ and $u_{3}^{*}$ and a Hamiltonian path in $G_{3}$ with endpoints
$u_{1}$ and $t_{1}$. Let

$P_{1}=\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
v_{1}}}\underset{G_{3}}{\underbrace{u_{1}\sim t_{1}}},$
$P_{2}=\underset{\overline{P}_{2}}{\underbrace{s_{2}}}\underset{\widehat{P}_{2}}{\underbrace{v_{2}\sim
t_{2}}},$

and

$P_{3}=\underset{G_{2}}{\underbrace{s_{3}\sim
u_{3}^{*}}}\underset{\widehat{P}_{2}}{\underbrace{u_{3}\sim
v_{3}^{*}}}\underset{\overline{P}_{2}}{\underbrace{v_{3}\sim t_{3}}}.$

Then $P_{1},P_{2},P_{3}$ form a $3$-PDPC of the weld of
$G_{1},G_{2},G_{3},G_{4}$, and we obtain a desired $3$-PDPC of $G$ by Lemma
2.1.

  6. Case $6$:

There exist $j_{1},j_{2}\in[\ell]$, where $j_{1}\neq j_{2}$, such that
$w_{j_{1}}=w_{j_{2}}=3$ and $S\nsubseteq V(G_{j_{1}})$.

Without loss of generality, assume that $\\{s_{1},s_{2},t_{3}\\}\subseteq
V(G_{1})$ and $\\{s_{3},t_{1},t_{2}\\}\subseteq V(G_{2})$. Let $v_{1}\in
V(G_{1})\setminus(\\{t_{3}\\}\cup N(s_{3}))$ be a white vertex and let
$u_{1}\in V(G_{2})$ be the unique neighbor of $v_{1}$. By the result in part
$(\ref{item:baserank3})$ on $G_{1}$ and $G_{2}$, there is a $2$-PDPC
$\overline{P}_{1},\overline{P}_{2}$ in $G_{1}$ with endpoints
$\\{s_{1},s_{2}\\}$ and $\\{v_{1},t_{3}\\}$ and a $2$-PDPC
$\widehat{P}_{1},\widehat{P}_{2}$ in $G_{2}$ with endpoints
$\\{u_{1},s_{3}\\}$ and $\\{t_{1},t_{2}\\}$. Let
$\overline{P_{2}}=s_{2}v_{3}\sim t_{3}$ and $\widehat{P}_{2}=s_{3}\sim
u_{3}t_{2}$, where $u_{3}$ is black, $v_{3}$ is white, and $u_{3},v_{3}$ are
not required to be distinct from $s_{3},t_{3}$, respectively. Let
$v_{2},u_{2}\in V(G_{3})$ be the unique neighbors of $s_{2},t_{2}$,
respectively, and let $u_{3}^{*},v_{3}^{*}\in V(G_{4})$ be the unique
neighbors of $u_{3},v_{3}$, respectively. By the result in part
$(\ref{item:baserank3})$ on $G_{3}$ and $G_{4}$ together with Proposition
1.1$(\ref{item:ours})$, there is a Hamiltonian path of $G_{3}$ with endpoints
$u_{2}$ and $v_{2}$ and a Hamiltonian path of $G_{4}$ with endpoints
$v_{3}^{*}$ and $u_{3}^{*}$. Let

$P_{1}=\underset{\overline{P}_{1}}{\underbrace{s_{1}\sim
v_{1}}}\underset{\widehat{P}_{1}}{\underbrace{u_{1}\sim t_{1}}},$
$P_{2}=\underset{\overline{P}_{2}}{\underbrace{s_{2}}}\underset{G_{3}}{\underbrace{v_{2}\sim
u_{2}}}\underset{\widehat{P}_{2}}{\underbrace{t_{2}}},$

and

$P_{3}=\underset{\widehat{P}_{2}}{\underbrace{s_{3}\sim
u_{3}}}\underset{G_{4}}{\underbrace{u_{3}^{*}\sim
v_{3}^{*}}}\underset{\overline{P}_{2}}{\underbrace{v_{3}\sim t_{3}}}.$

Then $P_{1},P_{2},P_{3}$ form a $3$-PDPC of the weld of
$G_{1},G_{2},G_{3},G_{4}$, and we obtain a desired $3$-PDPC of $G$ by Lemma
2.1.∎

##  3 Acknowledgements

These results are based on work supported by the National Science Foundation
under grant numbered MPS-2150299.

## References

  * [1] R. Caha and V. Koubek, Spanning multi-paths in hypercubes, Discrete Math. 307 (2007), 2053–2066.
  * [2] X.-B. Chen, Many-to-many disjoint paths in faulty hypercubes, Inform. Sci. 179 (2009), 3110–3115.
  * [3] X.-B. Chen, Paired many-to-many disjoint path covers of hypercubes with faulty edges, Inform. Process. Lett. 112 (2012), 61–66.
  * [4] X.-B. Chen, Paired many-to-many disjoint path covers of the hypercubes, Inform. Sci. 236 (2013), 218–223.
  * [5] X.-B. Chen, Paired 2-disjoint path covers of multidimensional torus networks with faulty edges, Inform. Process. Lett. 116, (2016), 107–110.
  * [6] T. Dvořák and P. Gregor, Partitions of faulty hypercubes into paths with prescribed endvertices, SIAM J. Discrete Math. 22 (2008), 1448–1461.
  * [7] P. Gregor and T. Dvořák, Path partitions of hypercubes, Inform. Process. Lett. 108 (2008), 402–406.
  * [8] S. Jo, J.-H. Park, K.-Y. Chwa, Paired many-to-many disjoint path covers in faulty hypercubes, Theoret. Comput. Sci. 513 (2013), 1–24.
  * [9] S. Jo, J.-H. Park, and K.Y. Chwa, Paired 2-disjoint path covers and strongly Hamiltonian laceability of bipartite hypercube-like graphs, Inform. Sci. 242 (2013), 103–112.
  * [10] S.-Y. Kim and J.-H. Park, Many-to-many two-disjoint path covers in restricted hypercube-like graphs, Theoret. Comput. Sci. 531 (2014), 26–36.
  * [11] B. Kronenthal and W.H.T. Wong, Paired many-to-many disjoint path covers of hypertori, Discrete Appl. Math. 218 (2017), 14–20.
  * [12] X.-J. Li, B. Liu, M. Ma, J.-M. Xu, Many-to-many disjoint paths in hypercubes with faulty vertices, Discrete Appl. Math. 217 (2017), 229–242.
  * [13] J. Li, C. Melekian, S. Zuo, and E. Cheng, Unpaired many-to-many disjoint path covers on bipartite $k$-ary $n$-cube networks with faulty elements, Int. J. Found. Comput. Sci. 31 (2020), 371–383.
  * [14] H. Li, W. Yang, and J. Meng, Fault-tolerant Hamiltonian laceability of Cayley graphs generated by transposition trees, Discrete Math. 312 (2012), 3087–3095.
  * [15] D. Liu and J. Li, Many-to-many $n$-disjoint path covers in $n$-dimensional hypercubes, Inform. Process. Lett. 110 (2010), 580–584.
  * [16] H. Lü and T. Wu, Unpaired many-to-many disjoint path cover of balanced hypercubest, Int. J. Found. Comput. Sci. 32 (2021), 943–956.
  * [17] R. Niu and M. Xu, The unpaired many-to-many $k$-disjoint paths in bipartite hypercube-like networks, Theoret. Comput. Sci. 911 (2022), 26–40.
  * [18] J.-H. Park, Paired many-to-many disjoint path covers in restricted hypercube-like graphs, Theoret. Comput. Sci. 634 (2016), 24–34.
  * [19] J.-H. Park, Paired many-to-many 3-disjoint path covers in bipartite toroidal grids, J. Comput. Sci. Engrg. 12 (2018), 115–126.
  * [20] J.-H. Park, Torus-like graphs and their paired many-to-many disjoint path covers, Discrete Appl. Math. 289 (2021), 64–77.
  * [21] J.-H. Park, Unpaired many-to-many disjoint path covers in nonbipartite torus-like graphs with faulty elements, IEEE Access 10 (2022), 127589–127600.
  * [22] J.-H. Park, Paired 3-disjoint path covers in bipartite torus-like graphs with edge faults, Internat. J. Found. Comput. Sci. 34 (2023), 429–441.
  * [23] J.-H. Park and I. Ihm, Many-to-many two-disjoint path covers in cylindrical and toroidal grids, Discrete Appl. Math. 185 (2015), 168–191.
  * [24] J.-H. Park and H.-C. Kim, Longest paths and cycles in faulty star graphs, J. Parallel Distrib. Comput. 64 (2004), 1286–1296.
  * [25] J.-H. Park, H.-C. Kim, and H.-S. Lim, Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements, IEEE Trans. Parallel Distrib. Syst. 17 (2006), 227–240.
  * [26] H. Qiao, E. Sabir, and J. Meng, The spanning cyclability of Cayley graphs generated by transposition trees, Discrete Appl. Math. 328 (2023), 60–69.
  * [27] E. Sabir and J. Meng, Degree sequence conditions for a graph to be disjoint path coverable, Discrete Appl. Math. 332 (2023), 62–69.
  * [28] S. Zhang and S. Wang, Many-to-many disjoint path covers in $k$-ary $n$-cubes, Theoret. Comput. Sci. 491 (2013), 103–118.