# Transversal Hamilton paths and cycles

Yangyang Cheng  (Y. Cheng) Mathematical Institute, University of Oxford,
Oxford, UK<EMAIL_ADDRESS>,  Wanting Sun  (W. Sun) Data
Science Institute, Shandong University, Jinan, 250100, China
<EMAIL_ADDRESS>,  Guanghui Wang  (G. Wang) School of Mathematics, Shandong
University, Jinan, 250100, China<EMAIL_ADDRESS>and  Lan Wei  (L. Wei)
School of Mathematics, Shandong University, Jinan, 250100, China
<EMAIL_ADDRESS>
###### Abstract.

Given a collection $\mathcal{G}=\\{G_{1},G_{2},\dots,G_{m}\\}$ of graphs on
the common vertex set $V$ of size $n$, an $m$-edge graph $H$ on the same
vertex set $V$ is transversal in $\mathcal{G}$ if there exists a bijection
$\varphi:E(H)\rightarrow[m]$ such that $e\in E(G_{\varphi(e)})$ for all $e\in
E(H)$. Denote
$\delta(\mathcal{G}):=\operatorname*{min}\left\\{\delta(G_{i}):i\in[m]\right\\}$.
In this paper, we first establish a minimum degree condition for the existence
of transversal Hamilton paths in $\mathcal{G}$: if $n=m+1$ and
$\delta(\mathcal{G})\geq\frac{n-1}{2}$, then $\mathcal{G}$ contains a
transversal Hamilton path. This solves a problem proposed by [Li, Li and Li,
J. Graph Theory, 2023]. As a continuation of the transversal version of
Dirac’s theorem [Joos and Kim, Bull. Lond. Math. Soc., 2020] and the stability
result for transversal Hamilton cycles [Cheng and Staden, arXiv:2403.09913v1],
our second result characterizes all graph collections with minimum degree at
least $\frac{n}{2}-1$ and without transversal Hamilton cycles. We obtain an
analogous result for transversal Hamilton paths. The proof is a combination of
the stability result for transversal Hamilton paths or cycles, transversal
blow-up lemma, along with some structural analysis.

Y. Cheng is supported by the PhD studentship of ERC Advanced Grant (883810).
W. Sun is supported by the China Postdoctoral Science Foundation
(2023M742092). G. Wang and L. Wei are supported by the Natural Science
Foundation of China (12231018) and Young Taishan Scholars Program of Shandong
Province.

##  1\. Introduction

Let $G=(V(G),E(G))$ be a graph with vertex set $V(G)$ and edge set $E(G)$. For
a vertex $v$ of $G$, denote by $N_{G}(v)$ the neighborhood of $v$ and let
$d_{G}(v)=|N_{G}(v)|$ be the degree of $v$. The subscripts are omitted when
$G$ is clear from the context. Let $\delta(G)$ be the minimum degree of $G$.
Denote by $P_{n},\,C_{n},\,K_{n}$ and $K_{t,n-t}$ the path, cycle, complete
graph and complete bipartite graph (with parts of size $t$ and $n-t$) on $n$
vertices, respectively.

Let $\mathcal{G}=\\{G_{1},G_{2},\dots,G_{m}\\}$ be a collection of not
necessarily distinct graphs with common vertex set $V$. We often think of each
$G_{i}$ having the color $i$. Let $H$ be a graph on the vertex set $V$. We say
$H$ is rainbow in $\mathcal{G}$ if there exists an injection
$\varphi:E(H)\rightarrow[m]$ such that $e\in E(G_{\varphi(e)})$ for all $e\in
E(H)$. In addition, if $|E(H)|=m$, then $\varphi$ is a bijection and we say
$H$ is transversal in $\mathcal{G}$. Let
$\delta(\mathcal{G})=\min\\{\delta(G_{i}):i\in[m]\\}$ be the minimum degree of
$\mathcal{G}$. Transversal often appears in infinitary combinatorics under
several similar definitions (see, [Aharoni1983, Erdos1968]), and it is also
extensively studied in the context of Latin squares (see [Wanless2011] for a
survey).

The following general question was proposed by Joos and Kim in [2021jooskim].

######  Question 1.1.

Let $H$ be a graph with $m$ edges, $\mathbf{G}$ be a family of graphs, and
$\mathcal{G}=\\{G_{1},G_{2},\dots,G_{m}\\}$ be a collection of graphs with
common vertex set $V$ such that $G_{i}\in\mathbf{G}$ for all $i\in[n]$. Which
properties imposed on $\mathbf{G}$ guarantee a transversal copy of $H$?

By taking $G_{1}=G_{2}=\cdots=G_{m}$, we need to study properties for
$\mathbf{G}$ such that each graph in $\mathbf{G}$ contains $H$ as a subgraph.
However, this alone is not always sufficient. For example, Aharoni, DeVos, de
la Maza, Montejano and Šámal [2019Aharoni] proved that if
$\mathcal{G}=\\{G_{1},G_{2},G_{3}\\}$ is a collection of graphs on a common
vertex set of size $n$ and $|E(G_{i})|>(\frac{26-2\sqrt{7}}{81})n^{2}$ for
$i\in[3]$, then $\mathcal{G}$ contains a rainbow triangle. Moreover, the
constant $\frac{26-2\sqrt{7}}{81}$ is optimal. However, Mantel’s theorem
states that any $n$-vertex graph with more than
$\lfloor\frac{n^{2}}{4}\rfloor$ edges must contain a triangle.

In this paper, we investigate the minimum degree condition for a graph
collection to guarantee the existence of transversal Hamilton paths or cycles.
Hamiltonicity of graphs is one of the fundamental problems in extremal graph
theory and structural graph theory. In 1952, Dirac [1952dirac] proved that an
$n$-vertex graph contains a Hamilton cycle if its minimum degree is no less
than $\frac{n}{2}$. Ore [1960Ore] relaxed this condition by considering the
sum of degrees of two non-adjacent vertices. In general, there are many other
sufficient conditions that guarantee the Hamiltonicity of a graph, such as
Pósa’s condition [1962PosaCon], Bondy’s condition [1971BondyCon] and so on.
For more problems and results about Hamiltonicity of graphs, we refer the
reader to [1980jacksonHam, 2003AdvancesHam, 2005RahmanHam, 2014GouldHam,
2017McdiarmidHam].

In 2020, Aharoni [2019Aharoni] conjectured that Dirac’s theorem can be
extended to a transversal version.

######  Conjecture 1.2 ([2019Aharoni]).

Suppose $\mathcal{G}=\\{G_{1},\ldots,G_{n}\\}$ is a collection of graphs with
the same vertex set $V$ of size $n$. If $\delta(\mathcal{G})\geq\frac{n}{2}$,
then $\mathcal{G}$ contains a transversal Hamilton cycle.

Cheng, Wang and Zhao [2021ChengWangZhao] solved this conjecture
asymptotically, and it was completely confirmed by Joos and Kim [2021jooskim].
Bradshaw, Halasz and Stacho [2022BradshawNum] extended the result of
Conjecture 1.2 by showing any such graph collection has at least
$(\frac{cn}{e})^{cn}$ transversal Hamilton cycles for some constant
$c>\frac{1}{68}$. Anastos and Chakraborti [2023Anastosrobust] improved
$(\frac{cn}{e})^{cn}$ to $(Cn)^{2n}$ for some constant $C>0$. Bradshaw
[2021Bradshaw] studied the Hamiltonicity in bipartite graph collections.
Bowtell, Morris, Pehova and Staden [2023universality] showed that
$\mathcal{G}$ contains every Hamilton cycle pattern if
$\delta(\mathcal{G})\geq(1+o(1))\frac{n}{2}$. The research of graph
collections has also been generalized to random graph collections. Ferber, Han
and Mao [2022FerberRandom] provided a transversal version of the Dirac’s
theorem in random graph collections.

In addition to Dirac’s theorem, many other classical results of extremal graph
theory have been generalized. Cheng, Han, Wang and Wang [2023chengspan]
studied the minimum degree condition for the existence of transversal
$K_{t}$-factors in (hyper)graph collections, which is an asymptotical version
of the rainbow Hajnal-Szemerédi theorem [Hajnal-Szemerédi]. Montgomery,
Müyesser and Pehova [2022Montgomery] gave asymptotically tight transversal
versions of Hajnal-Szemerédi theorem [Hajnal-Szemerédi] and Kühn-Osthus
theorem [K-Othm] on factors, and a transversal generalisation of the theorem
of Komlós, Sárkózy and Szemerédi [2001komlosTree] on spanning trees. Gupta,
Hamann, Müyesser, Parczyk and Sgueglia [2023GuptaPowerH] gave a general
approach to transversal versions of several classical Dirac-type results.
Cheng and Staden [2023chengBlowup] established the transversal blow-up lemma,
which is an effective tool for transversal embedding problems. Chakraborti,
Im, Kim and Liu [2023chakrabortiBandwidth] extended the bandwidth theorem
[2009bandwidth] to graph collections. More relevant developments on this
topic, we refer the reader to [2009Ahamatch, 2017AhaEKR, 2019Ahamatch,
2021ChengHyp, 2021KupavskiiMatch, 2022LuMatch, 2023LuMatch, 2023TangHyp].

Li, Li and Li [2022liluyi] established a sufficient condition for the
existence of a rainbow Hamilton path in
$\mathcal{G}=\\{G_{1},\ldots,G_{n}\\}$. However, the edges of a rainbow
Hamilton path only come from $n-1$ graphs in $\mathcal{G}$. Hence, they
proposed the following problem: whether a collection of $n-1$ graphs is
sufficient to guarantee the existence of transversal Hamilton paths. Our first
result solves the above problem and prove the following result.

######  Theorem 1.3.

Let $\mathcal{G}=\\{G_{1},\ldots,G_{n-1}\\}$ be a collection of graphs on a
common vertex set $V$ of size $n$. If $\delta(\mathcal{G})\geq\frac{n-1}{2}$,
then $\mathcal{G}$ has a transversal Hamilton path.

The proof of Theorem 1.3 is inspired by Joos and Kim [2021jooskim], which
proved the transversal version of Dirac’s theorem by constructing auxiliary
digraphs. The difficulty of our proof is that we can only find a rainbow cycle
of length at least $n-2$ when $\delta(\mathcal{G})\geq\frac{n-1}{2}$. If the
longest rainbow cycle inside $\mathcal{G}$ has length $n-2$, then we need to
analyze the relation between two vertices outside the cycle by using a series
of rotations and more structural analysis.

For graphs $G$ and $H$, denote by $G\cup H$ the disjoint union of $G$ and $H$.
We use $G\vee H$ to denote the graph obtained from $G\cup H$ by adding an edge
between each vertex of $G$ and each vertex of $H$. A $k$-matching in a graph
is a set consisting of $k$ edges with no shared vertices. For any vertex
subsets $X,\,Y\subseteq V(G)$, let $G[X]$ be the induced subgraph of $G$ on
$X$. Let $G[X,Y]$ be the subgraph of $G$ with vertex set $X\cup Y$ and edge
set $\\{xy:x\in X,\,y\in Y\ \text{and}\ xy\in E(G)\\}$. Denote by $G-xy$ the
graph obtained from $G$ by deleting the edge $xy$, where $xy\in E(G)$. Let
$\mathcal{G}=\\{G_{1},G_{2},\dots,G_{m}\\}$ be collection of graphs on a
common vertex set. Then define $\mathcal{G}[X]:=\\{G_{i}[X]:i\in[m]\\}$ and
$\mathcal{G}[X,Y]:=\\{G_{i}[X,Y]:i\in[m]\\}$. If $E(G)=\emptyset$, then we
simply write $G=\emptyset$. Similarly, if there is no edge in $G_{i}$ for all
$i\in[m]$, then we write $\mathcal{G}=\emptyset$.

Let $0<\kappa<1$ be a positive constant. Given two graph collections
$\mathcal{G}=\\{G_{1},\ldots,G_{m}\\}$ and
$\mathcal{H}=\\{H_{1},\ldots,H_{m}\\}$ defined on the vertex sets $V_{1}$ and
$V_{2}$ respectively, where $|V_{1}|=|V_{2}|=n$ and $(1-\kappa)n\leq
m\leq(1+\kappa)n$, we say $\mathcal{G}$ is $\kappa$-close to $\mathcal{H}$ if
by adding or deleting at most $\kappa n^{3}$ edges of $\mathcal{G}$ we can
obtain a copy of $\mathcal{H}$. A graph collection
$\mathcal{G}^{\prime}=\\{G_{1}^{\prime},\ldots,G_{m}^{\prime}\\}$ is a
spanning collection of $\mathcal{G}$ if $G_{i}^{\prime}$ is a spanning
subgraph of $G_{i}$ for each $i\in[m]$. For any vertex set $V$ of size $n$, we
say $A\cup B$ is an equitable partition of $V$ if $|A|+|B|=n$ and
$||A|-|B||\leq 1$.

######  Definition 1.4 ($\mathcal{H}_{s}^{t}$, half-split graph collection).

Given integers $s,t\geq 0$, let $\mathcal{H}_{s}^{t}$ be the graph collection
on a common vertex set of size $n$ obtained by taking $s$ copies of
$K_{\lceil\frac{n}{2}\rceil}\cup K_{\lfloor\frac{n}{2}\rfloor}$ and $t$ copies
of $K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}$, where they are
defined on the same equitable partition.

We say that a graph collection $\mathcal{G}=\\{G_{1},\ldots,G_{m}\\}$ on a
common vertex set $V$ of size $n$ is half-split if there is a subset
$A\subseteq V$ with $|A|=\lceil\frac{n}{2}\rceil$ such that
$\mathcal{G}[A]=\emptyset$ and all graphs in $\mathcal{G}[A,V\backslash A]$
are complete bipartite graphs.

Cheng and Staden [2024cheng] characterized the stability result for
transversal Hamilton paths or cycles when the minimum degree of the graph
collection is slightly lower than $\frac{n}{2}$.

######  Theorem 1.5 ([2024cheng]).

For all $\kappa>0$, there exist $\mu>0$ and $n_{0}$ such that the following
holds for all integers $n\geq n_{0}$. Let
$\mathcal{G}=\\{G_{1},\ldots,G_{m}\\}$ be a collection of graphs with the
common vertex set $V$ of size $n$ and
$\delta(\mathcal{G})\geq(\frac{1}{2}-\mu)n$.

  1. (i)

If $m=n$ and $\mathcal{G}$ contains no transversal Hamilton cycles, then
either $\mathcal{G}$ is $\kappa$-close to $\mathcal{H}_{s}^{t}$ for some
$s\in[n]$ with $t=n-s$ is odd, or $\mathcal{G}$ is $\kappa$-close to a half-
split graph collection.

  2. (ii)

If $m=n-1$ and $\mathcal{G}$ contains no transversal Hamilton paths, then
either $\mathcal{G}$ is $\kappa$-close to $\mathcal{H}_{n-1}^{0}$, or
$\mathcal{G}$ is $\kappa$-close to a half-split graph collection.

As a continuation of the transversal version of Dirac’s theorem [2021jooskim]
and the stability result for transversal Hamilton cycles (i.e., Theorem 1.5
(i)), we characterize all graph collections with minimum degree at least
$\frac{n}{2}-1$ and without transversal Hamilton cycles. Note that in a graph
collection $\mathcal{G}$, the order of colors does not affect the overall
structure of $\mathcal{G}$. Thus, when we say $G_{i}$ (for example, $G_{1}$)
is a graph in $\mathcal{G}$, it is usually arbitrary.

######  Theorem 1.6.

For sufficiently large $n$, let $\mathcal{C}$ be a set of $n$ colors, and let
$\mathcal{G}=\\{G_{i}:i\in\mathcal{C}\\}$ be a collection of graphs with
common vertex set $V$ of size $n$ and $\delta(\mathcal{G})\geq\frac{n}{2}-1$.
Assume that $\mathcal{G}$ contains no transversal Hamilton cycles.

  1. (i)

If $n$ is odd, then one of the following holds:

    1. (a)

$\mathcal{G}$ is the half-split graph collection,

    2. (b)

there exists a fixed vertex $u$ with $d_{G_{i}}(u)=n-1$ and an equitable
partition $A\cup B$ of $V\backslash\\{u\\}$ such that
$G_{i}[V\backslash\\{u\\}]=G_{i}[A]\cup G_{i}[B]=2K_{\frac{n-1}{2}}$ for all
$i\in\mathcal{C}$.

  2. (ii)

If $n$ is even, then one of the following holds:

    1. (a)

$\mathcal{G}$ is a spanning collection of $\mathcal{H}_{n-t}^{t}$ for some odd
integer $t\in[n]$,

    2. (b)

there exists a partition $A\cup B$ of $V$ with $|A|=\frac{n}{2}-1$ such that
either $G_{i}[B]=\emptyset$ for all but at most one $i\in\mathcal{C}$, or
$E(G_{i}[B])\subseteq\\{uv\\}$ for fixed $u,v\in B$ and all $i\in\mathcal{C}$,

    3. (c)

there exists an equitable partition $A\cup B$ of $V$ such that
$\mathcal{G}[A,B]$ contains no rainbow $2$-matching, that is, one of the
following holds:

       * •

$G_{i}=G_{i}[A]\cup G_{i}[B]=2K_{\frac{n}{2}}$ for all but at most one
$i\in\mathcal{C}$,

       * •

there is a vertex $u\in A$ such that $E(G_{i}[A,B])=E(G_{i}[\\{u\\},B])$ for
all $i\in\mathcal{C}$,

       * •

there are vertices $u\in A$ and $v\in B$ such that
$E(G_{1}[A,B])\subseteq\\{uw:w\in B\\}\cup\\{wv:w\in A\\}$ and
$E(G_{i}[A,B])\subseteq\\{uv\\}$ for all $i\in\mathcal{C}\backslash\\{1\\}$
(see Figure 1 (a)),

       * •

there are vertices $u,u^{\prime}\in A$ and $v,v^{\prime}\in B$ such that
$E(G_{1}[A,B])=\\{uv,u^{\prime}v^{\prime}\\}$,
$E(G_{2}[A,B])=\\{uv^{\prime},u^{\prime}v\\}$ and $G_{j}=G_{j}[A]\cup
G_{j}[B]=2K_{\frac{n}{2}}$ for all $j\in\mathcal{C}\backslash[2]$ (see Figure
1 (b)).

Figure 1. Extremal graph collections in Theorem 1.6. Here the dotted line
means that the edge may not exist, and the triangle stands for a complete
graph.

######  Remark 1.7.

In fact, in Theorem 1.6 (ii) (b)-(c), based on the local structure of
$\mathcal{G}$ and the minimum degree condition, the global structure of
$\mathcal{G}$ can be deduced immediately. For example, $|A|=\frac{n}{2}-1$ and
$G_{i}[B]=\emptyset$ imply that $G_{i}[A,B]=K_{\frac{n}{2}-1,\frac{n}{2}+1}$
and $G_{i}[A]$ can be any graph.

For an $n$-vertex graph $G$ with $\delta(G)\geq\frac{n}{2}-1$, Büyükçolak-
Gözüpek-Özkan-Sibel-Shalom [2019GraphOdd] and Fu-Gao-Wang-Yang [2024GraphEven]
characterized the structure of $G$ without Hamilton cycles if $n\,(\geq 3)$ is
odd and $n\,(\geq 22)$ is even, respectively. In fact, by applying Theorem 1.6
with $G_{1}=G_{2}=\dots=G_{n}=G$, we can deduce their results when $n$ is
sufficiently large.

######  Corollary 1.8 ([2019GraphOdd, 2024GraphEven]).

For sufficiently large $n$, let $G$ be an $n$-vertex graph with vertex set
$V$. Assume that $G$ contains no Hamilton cycles and
$\delta(G)\geq\frac{n}{2}-1$.

  1. (i)

If $n$ is odd, then either $G=K_{1}\vee(K_{\frac{n-1}{2}}\cup
K_{\frac{n-1}{2}})$ or $G$ is a spanning subgraph of ${\frac{n+1}{2}K_{1}}\vee
K_{\frac{n-1}{2}}$.

  2. (ii)

If $n$ is even, then $G$ is a spanning subgraph of
$K_{1}\vee(K_{\frac{n}{2}-1}\cup K_{\frac{n}{2}})$ or
$(K_{2}\cup(\frac{n}{2}-1)K_{1})\vee K_{\frac{n}{2}-1}$.

Recall that Theorem 1.3 gives a sufficient condition for the existence of
transversal Hamilton paths in a collection of $n-1$ graphs. In contrast to the
Hamilton cycle case, our next result characterizes all collections of $n-1$
graphs with minimum degree at least $\frac{n-3}{2}$ and containing no
transversal Hamilton paths.

######  Theorem 1.9.

For sufficiently large $n$, let $\mathcal{C}$ be a set of $n-1$ colors, and
let $\mathcal{G}=\\{G_{i}:i\in\mathcal{C}\\}$ be a collection of graphs with
the common vertex set $V$ of size $n$. Assume that
$\delta(\mathcal{G})\geq\frac{n-3}{2}$ and $\mathcal{G}$ contains no
transversal Hamilton paths.

  1. (i)

If $n$ is even, then one of the following holds:

     * •

$\mathcal{G}$ is $\mathcal{H}_{n-1}^{0}$,

     * •

there exists a partition $A\cup B$ of $V$ with $|A|=\frac{n}{2}+1$ such that
$G_{i}[A]=\emptyset$ for all $i\in\mathcal{C}$.

  2. (ii)

If $n$ is odd, then one of the following holds:

     * •

$\mathcal{G}$ is a spanning collection of $\mathcal{H}_{n-1}^{0}$,

     * •

there exists a partition $A\cup B$ of $V$ with $|A|=\frac{n+3}{2}$ such that
either $G_{i}[A]=\emptyset$ for all but at most one $i\in\mathcal{C}$, or
$E(G_{i}[A])\subseteq\\{uv\\}$ for fixed vertices $u,v\in A$ and all
$i\in\mathcal{C}$.

Notice that given a collection $\mathcal{G}$ of $n-1$ graphs on a common
vertex set of size $n$, the graph collection obtained from adding a complete
graph to $\mathcal{G}$ has a transversal Hamilton cycle if and only if
$\mathcal{G}$ has a transversal Hamilton path. Thus, Theorem 1.9 (i) is an
immediate consequence of Theorem 1.6 (ii). For Theorem 1.9 (ii), it can be
proved by using similar arguments as Theorem 1.6, so we omit its proof. Note
that we just need to find a transversal Hamilton path inside $\mathcal{G}$,
that is, we don’t need to connect its two endpoints, hence the proof of
Theorem 1.9 (ii) is much simpler.

##  2\. Notation and Organization

###  2.1. Notation

First of all, we state that all terminology and notation on graph theory not
defined in this paper are the same as those used in the textbook
[graphtheory].

For a vertex subset $U,W\subseteq V(G)$ and a vertex $v\in V(G)$, let
$N_{G}(v,U)=N_{G}(v)\cap U$ and $d_{G}(v,U)=|N_{G}(v,U)|$. Let
$N_{G}(U,W)=\cup_{u\in U}N_{G}(u,W)$. Denote by $S_{r}$ the star with $r$
vertices, where the vertex with degree $r-1$ is the center of $S_{r}$. Let
$\mathcal{G}=\\{G_{i}:i\in\mathcal{C}\\}$ be a graph collection and $H$ be a
rainbow subgraph inside $\mathcal{G}$. Denote by $col(H)$ the set of colors
appearing in $H$. Let $P_{t}=v_{1}v_{2}\ldots v_{t}$ be a rainbow path inside
$\mathcal{G}$. For $1\leq i<j\leq t$, denote by
$v_{i}Pv_{j}:=v_{i}v_{i+1}\ldots v_{j}$ a rainbow subpath of $P$, and the
color of each edge inherits its color on $P$. We say $P$ is maximal in
$\mathcal{G}$ if it is not a proper rainbow subpath of any other rainbow paths
inside $\mathcal{G}$. Two rainbow paths $P$ and $Q$ are said to be disjoint if
$V(P)\cap V(Q)=\emptyset$ and $col(P)\cap col(Q)=\emptyset$.

Let $D$ be a digraph. We denote its vertex set by $V(D)$ and its arc set by
$A(D)$. For vertices $u$ and $v$ in $D$, the arc from $u$ to $v$ is denoted by
$\overrightarrow{uv}$. Given $v\in V(D)$, let $N_{D}^{+}(v)$ and
$N_{D}^{-}(v)$ be the out-neighborhood and in-neighborhood of $v$ in $D$,
respectively. Denote by $d_{D}^{+}(v)$ and $d_{D}^{-}(v)$ the out-degree and
in-degree of $v,$ respectively.

For a positive integer $n$, we write $[n]:=\\{1,2,\dots,n\\}$ and
$[a,b]:=\\{a,a+1,\dots,b\\}$ for two positive integers $a<b$. For any two
constants $\alpha,\beta\in(0,1)$, we write $\alpha\ll\beta$ if there exists a
function $f=f(\beta)$ such that the subsequent arguments hold for all
$0<\alpha\leq f.$

###  2.2. Organization

In the remainder of this section, we give a sketch of the proof of Theorem
1.6. In Section 3, we prove Theorem 1.3, which establishes a minimum degree
condition to guarantee the existence of transversal Hamilton paths. In Section
4, we give the proof of Theorem 1.6. The proof is split into three steps:
constructing short disjoint rainbow paths to cover bad vertices and bad
colors; using the connecting tool (Claim 4.5) to connect those rainbow paths;
applying transversal blow-up lemma to construct long rainbow paths to cover
all left vertices and colors. In order to use the transversal blow-up lemma,
we introduce Theorem 4.3 to balance the number of vertices in two parts, whose
proof is presented in Section 5. Finally, some concluding remarks are given in
Section 6.

###  2.3. Sketch of the proof of Theorem 1.6

Assume $0<\frac{1}{n}\ll\delta\ll\eta\ll 1$. Let
$\mathcal{G}=\\{G_{1},G_{2},\dots,G_{n}\\}$ be a collection of graphs with
common vertex set $V$ of size $n$. Assume that
$\delta(\mathcal{G})\geq\frac{n}{2}-1$ and $\mathcal{G}$ contains no
transversal Hamilton cycles. Denote $\mathcal{C}_{1}:=\\{i\in[n]:G_{i}$ is
close to $K_{\lceil\frac{n}{2}\rceil}\cup K_{\lfloor\frac{n}{2}\rfloor}\\}$,
$\mathcal{C}_{2}:=\\{i\in[n]:G_{i}$ is close to
$K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}\\}$ and
$\mathcal{C}_{bad}:=[n]\backslash(\mathcal{C}_{1}\cup\mathcal{C}_{2})$. By
[2024cheng]*Lemma 5.3 (see also Lemma 4.2 in Section 4), we know that
$|\mathcal{C}_{1}|+|\mathcal{C}_{2}|\geq(1-3\delta)n$. In view of Definition
4.1, we can fix a characteristic partition $({A_{i}},{B_{i}},{C_{i}})$ for
each graph $G_{i}$ with $i\in\mathcal{C}_{1}\cup\mathcal{C}_{2}$. By swapping
the labels of ${A_{i}}$ and ${B_{i}}$, we have
$|{A_{1}}\Delta{A_{i}}|,|{B_{1}}\Delta{B_{i}}|<\delta n$ for every
$i\in(\mathcal{C}_{1}\cup\mathcal{C}_{2})\backslash\\{1\\}$.

Based on the sizes of $|\mathcal{C}_{1}|$ and $|\mathcal{C}_{2}|$, we
distinguish our proof into three cases: $|\mathcal{C}_{1}|<\eta n$,
$|\mathcal{C}_{2}|<\eta n$, $|\mathcal{C}_{1}|\geq\eta n$ and
$|\mathcal{C}_{2}|\geq\eta n$. We will take the first case as an example to
illustrate the general idea of our proof.

Firstly, expand $A_{1}\cup B_{1}$ to an equitable partition $A\cup B$ of $V$.
For a vertex $v\in A$, there are three bad cases: $v$ lies in almost all
$B_{i}$ for $i\in\mathcal{C}_{1}\cup\mathcal{C}_{2}$; $v$ lies in almost all
$C_{i}$ for $i\in\mathcal{C}_{1}\cup\mathcal{C}_{2}$; and $v$ lies in both
$A_{i}$ and $B_{i}$ for many $i\in\mathcal{C}_{1}\cup\mathcal{C}_{2}$. Then
move vertices in the first case from $A$ to $B$, and do the same operation for
such vertices in $B$. Denote the set of vertices in the other two bad cases by
$V_{bad}$. Now, the number of vertices in $A$ and $B$ may be unbalanced, but
their difference is still small (no more than $9\delta n$). In order to use
the transversal blow-up lemma (see [2023chengBlowup] or Claim 4.4 in Section
4) to find long rainbow paths inside $\mathcal{G}$, the following four steps
are needed.

Step 1. Balance the number of vertices in $A$ and $B$. If there exists a set
of disjoint rainbow paths in $\mathcal{G}[B]$ such that after deleting their
vertices, the number of vertices in $A$ and $B$ are balanced, then we are
done. Otherwise, we will show that $\mathcal{G}$ must be a graph collection
described in Theorem 1.6.

Step 2. Deal with vertices in $V_{bad}$. By using colors in $\mathcal{C}_{2}$,
we are to find a series of disjoint rainbow $P_{3}$ such that all centers of
them are all vertices in $V_{bad}$ and the endpoints of them are unused
vertices in $(A\cup B)\backslash V_{bad}$.

Step 3. Deal with colors in $\mathcal{C}_{bad}$. Choose a maximal rainbow
matching $M$ by using colors in $\mathcal{C}_{bad}$ and avoiding vertices used
in Steps 1-2. It is routine to check that for each
$j\in\mathcal{C}_{bad}\backslash col(M)$, the graph $G_{j}$ is close to
$K_{\lfloor\frac{n}{2}\rfloor}\cup K_{\lceil\frac{n}{2}\rceil}$.

Step 4. Deal with colors in $\mathcal{C}_{1}\cup(\mathcal{C}_{bad}\backslash
col(M))$. We greedily select two rainbow paths with colors
$\mathcal{C}_{1}\cup(\mathcal{C}_{bad}\backslash col(M))$ and avoiding the
used vertices in the above three steps. The lengths of those two rainbow paths
are determined by the parity of
$|\mathcal{C}_{1}\cup(\mathcal{C}_{bad}\backslash col(M))|$.

Based on the minimum degree condition and the characteristic partition of
extremal graphs, one may use colors in $\mathcal{C}_{2}$ to connect all
rainbow paths obtained in the above four steps into a single short rainbow
path, say $P$, such that $V_{bad}\subseteq V(P)$,
$\mathcal{C}_{1}\cup\mathcal{C}_{bad}\subseteq col(P)$, $|A\backslash V(P)|$
and $|B\backslash V(P)|$ are almost equal. By applying the transversal blow-up
lemma and some structural analysis, the exact structure of graphs in
$\mathcal{G}$ can be deduced.

##  3\. Proof of Theorem 1.3

In this section, we prove Theorem 1.3. The following lemma allows us to find a
rainbow path of length at least $n-3$ in $\mathcal{G}$.

######  Lemma 3.1 ([2022liluyi]).

Suppose $\mathcal{G}=\\{G_{1},\ldots,G_{n}\\}$ is a collection of graphs with
common vertex set $V$ of size $n$, and $\delta(\mathcal{G})\geq\frac{n-1}{2}$.
Then one of the following holds:

  * •

$\mathcal{G}$ has a rainbow cycle of length at least $n-1$,

  * •

$n$ is odd and $\mathcal{G}$ consists of $n$ copies of $K_{1}\vee
2K_{\frac{n-1}{2}}$.

###### Proof of Theorem 1.3.

We prove it by contradiction. Suppose that $\mathcal{G}$ does not contain
transversal Hamilton paths. Let $V=\\{x_{1},\ldots,x_{n}\\}$. Firstly, we give
the following claim.

######  Claim 3.2.

$\mathcal{G}$ has a rainbow cycle of length at least $n-2$.

###### Proof of Claim 3.2.

Suppose that $\mathcal{G}$ contains no rainbow cycle of length at least $n-2$.
By Lemma 3.1, we know $\\{G_{1},\ldots,G_{n-1},K_{n}\\}$ contains a rainbow
cycle of length at least $n-1$. Thus, $\mathcal{G}$ contains a rainbow path of
length at least $n-3$. Let $P=x_{1}x_{2}\ldots x_{n-2}$ be such a rainbow
path, where $x_{i}x_{i+1}\in E(G_{i})$ for $i\in[n-3]$. It is obvious that
$x_{1}x_{n-2}\notin E(G_{n-1})\cup E(G_{n-2})$.

We claim that
$|N_{G_{n-2}}(x_{1})\cap\\{x_{n-1},x_{n}\\}|+|N_{G_{n-1}}(x_{n-2})\cap\\{x_{n-1},x_{n}\\}|\leq
2$. Otherwise, there exists $x_{j}\in N_{G_{n-2}}(x_{1})\cap
N_{G_{n-1}}(x_{n-2})$ for some $j\in\\{n-1,n\\}$. It follows that
$x_{j}x_{1}\ldots x_{n-2}x_{j}$ forms a rainbow cycle of length $n-1$ in
$\mathcal{G}$, a contradiction. Let

$A=\\{j\in[n-4]:x_{1}x_{j+1}\in E(G_{n-2})\\},\quad
B=\\{j\in[2,n-3]:x_{j}x_{n-2}\in E(G_{n-1})\\}.$

If $A\cap B\neq\emptyset$, then choose $j_{1}\in A\cap B$ and
$x_{1}x_{j_{1}+1}\ldots x_{n-2}x_{j_{1}}x_{j_{1}-1}\ldots x_{1}$ is a rainbow
cycle of length $n-2$ in $\mathcal{G}$, a contradiction. Thus, $A\cap
B=\emptyset$. Notice that $A\cup B\subseteq[n-3]$. Hence $|A|+|B|\leq n-3$.
Recall that $x_{1}x_{n-2}\notin E(G_{n-1})\cup E(G_{n-2})$. Then,
$|A|\geq\frac{n-1}{2}-|N_{G_{n-2}}(x_{1})\cap\\{x_{n-1},x_{n}\\}|$ and
$|B|\geq\frac{n-1}{2}-|N_{G_{n-1}}(x_{n-2})\cap\\{x_{n-1},x_{n}\\}|$.
Therefore,
$|N_{G_{n-2}}(x_{1})\cap\\{x_{n-1},x_{n}\\}|+|N_{G_{n-1}}(x_{n-2})\cap\\{x_{n-1},x_{n}\\}|=2$
and $|A|+|B|=n-3$. By symmetry, one of the following holds:

  * (A1)

$N_{G_{n-2}}(x_{1})\cap\\{x_{n-1},x_{n}\\}=\\{x_{n-1}\\}$ and
$N_{G_{n-1}}(x_{n-2})\cap\\{x_{n-1},x_{n}\\}=\\{x_{n}\\}$,

  * (A2)

$N_{G_{n-2}}(x_{1})\cap\\{x_{n-1},x_{n}\\}=\\{x_{n-1}\\}$ and
$N_{G_{n-1}}(x_{n-2})\cap\\{x_{n-1},x_{n}\\}=\\{x_{n-1}\\}$,

  * (A3)

$N_{G_{n-2}}(x_{1})\cap\\{x_{n-1},x_{n}\\}=\\{x_{n-1},x_{n}\\}$ and
$N_{G_{n-1}}(x_{n-2})\cap\\{x_{n-1},x_{n}\\}=\emptyset$.

If (A1) holds, then $\mathcal{G}$ contains a transversal Hamilton path
$x_{n-1}x_{1}\ldots x_{n-2}x_{n}$, a contradiction. If (A2) holds, then
$\mathcal{G}$ contains a rainbow $(n-1)$-cycle $x_{n-1}x_{1}\ldots
x_{n-2}x_{n-1}$, which is also a contradiction. Hence (A3) holds.

It is easy to see that $x_{n-3}x_{n}\notin E(G_{n-3})\cup E(G_{n-1})$.
Otherwise, $x_{n}x_{1}\ldots x_{n-3}x_{n}$ is a rainbow cycle of length $n-2$
in $\mathcal{G}$, a contradiction. For convenience, denote $x^{1}:=x_{n}$,
$x^{i}:=x_{i-1}$ for $i\in[2,n-2]$, $x^{n-1}:=x_{n-1}$ and $x^{n}:=x_{n-2}$.
Then $P^{\prime}:=x^{1}x^{2}\ldots x^{n-2}$ is a rainbow path inside
$\mathcal{G}$ with $n-3,n-1\notin col(P^{\prime})$. Let

$A^{\prime}=\\{j\in[n-4]:x^{1}x^{j+1}\in E(G_{n-1})\\},\quad
B^{\prime}=\\{j\in[2,n-3]:x^{j}x^{n-2}\in E(G_{n-3})\\}.$

Notice that $x^{1}x^{n-1}\not\in E(G_{n-1})$, otherwise
$x^{n-1}x^{1}P^{\prime}x^{n-2}x^{n}$ forms a transversal Hamilton path, a
contradiction. It follows from (A3) that $x^{1}x^{n}\notin E(G_{n-1})$ and
$x^{2}x^{n-1}\in E(G_{n-2})$. Then $x^{n-1}x^{n-2}\notin E(G_{n-3})$. Together
with $x_{n-3}x_{n}\notin E(G_{n-3})\cup E(G_{n-1})$, we have
$|A^{\prime}|+|B^{\prime}|\geqslant\frac{n-1}{2}+\frac{n-1}{2}-1=n-2$. Since
$A^{\prime}\cup B^{\prime}\subseteq[n-3]$, one has $A^{\prime}\cap
B^{\prime}\neq\emptyset$ and let $j_{2}\in A^{\prime}\cap B^{\prime}$. Hence,
$x^{1}x^{j_{2}+1}P^{\prime}x^{n-2}x^{j_{2}}P^{\prime}x^{1}$ is a rainbow cycle
of length $n-2$ in $\mathcal{G}$, a contradiction.

This completes the proof of Claim 3.2. ∎

Based on Claim 3.2, we distinguish our proof into the following two cases.

Case 1. $\mathcal{G}$ has a rainbow cycle of length $n-1$.

Let $C=x_{1}x_{2}\ldots x_{n-1}x_{1}$ be a rainbow cycle inside $\mathcal{G}$
with $x_{i}x_{i+1}\in E(G_{i})$ for $i\in[n-1]$, where we identify $x_{n}$
with $x_{1}$. Let $y$ be the vertex in $V\backslash V(C)$. Since $\mathcal{G}$
has no transversal Hamilton path, one has $yx_{i},yx_{i+1}\not\in E(G_{i})$
for $i\in[n-1]$.

We construct the following auxiliary digraph $D$ with vertex set $V$ and arc
set

$A(D)=\bigcup_{i\in[n-1]}\\{\overrightarrow{x_{i}z}:x_{i}z\in E(G_{i})\
\text{and}\ z\neq x_{i+1}\\}.$

By the definition of $D$, we have $d_{D}^{+}(y)=0$. Furthermore,
$d_{D}^{-}(y)=0$. Otherwise, there exists $x_{i}\in N_{D}^{-}(y)$ for some
$i\in[n-1]$. Then, $yx_{i}\ldots x_{1}x_{n-1}\ldots x_{i+1}$ is a transversal
Hamilton path in $\mathcal{G}$, a contradiction. It follows from
$\delta(\mathcal{G})\geq\frac{n-1}{2}$ that
$d_{D}^{+}(x_{i})\geq\frac{n-1}{2}-1$ for all $i\in[n-1]$. Therefore,

$|A(D)|\geq(n-1)(\frac{n-1}{2}-1)=(n-1)\frac{n-3}{2}.$ (1)

Without loss of generality, assume that
$d_{D}^{-}(x_{1})=\max\\{d_{D}^{-}(x_{i}):i\in[n-1]\\}$. Then we claim that
$d_{D}^{-}(x_{1})\geq\frac{n-3}{2}$. Otherwise,
$d_{D}^{-}(x_{1})\leq\frac{n-5}{2}$. This implies that
$|A(D)|=\sum_{i\in[n-1]}d_{D}^{-}(x_{i})\leq(n-1)\frac{n-5}{2}<(n-1)\frac{n-3}{2}$,
which contradicts (1). Let

$I_{1}^{1}=\\{i\in[2,n-2]:x_{i}\in N_{D}^{-}(x_{1})\\},\quad
I_{2}^{1}=\\{i\in[2,n-2]:x_{i+1}y\in E(G_{1})\\}.$

Recall that $x_{1}y,x_{2}y\notin E(G_{1})$. Then
$|I_{1}^{1}|+|I_{2}^{1}|\geq\frac{n-3}{2}+\frac{n-1}{2}=n-2$. But
$I_{1}^{1}\cup I_{2}^{1}\subseteq[2,n-2]$. Hence $I_{1}^{1}\cap
I_{2}^{1}\neq\emptyset$. Choose $i_{1}\in I_{1}^{1}\cap I_{2}^{1}$. Therefore,
$x_{2}\ldots x_{i_{1}}x_{1}x_{n-1}\ldots x_{i_{1}+1}y$ is a transversal
Hamilton path in $\mathcal{G}$, a contradiction.

Case 2. $\mathcal{G}$ has no rainbow cycle of length $n-1$.

By Claim 3.2, there exists a rainbow cycle of length $n-2$ in $\mathcal{G}$,
say $C=x_{1}x_{2}\ldots x_{n-2}x_{1}$ with $x_{i}x_{i+1}\in E(G_{i})$ for
$i\in[n-2]$, where we identify $x_{n-1}$ with $x_{1}$. Let
$\\{y,y^{\prime}\\}:=V\backslash V(C)$. Now, we utilize the following
auxiliary digraph $D$ with vertex set $V$ and arc set

$A(D)=\bigcup_{i\in[n-2]}\\{\overrightarrow{x_{i}z}:x_{i}z\in E(G_{i})\
\text{and}\ z\neq x_{i+1}\\}.$

Clearly, $d_{D}^{+}(y)=d_{D}^{+}(y^{\prime})=0$ and
$d_{D}^{+}(x_{i})\geq\frac{n-1}{2}-1$ for each $i\in[n-3]$. Then,
$|A(D)|\geq(n-2)\frac{n-3}{2}$. Without loss of generality, assume that
$d_{D}^{-}(x_{1})=\max\\{d_{D}^{-}(x_{i}):i\in[n-2]\\}$. In what follows, we
are going to prove that $d_{D}^{-}(x_{1})\leq\frac{n-5}{2}$. Suppose that
$d_{D}^{-}(x_{1})\geq\frac{n-3}{2}$. We distinguish the proof into two
subcases according to $yy^{\prime}$ is an edge in $G_{n-1}$ or not.

Subcase 2.1. $yy^{\prime}\in E(G_{n-1})$.

Let

$I_{1}^{2}=\\{i\in[2,n-3]:x_{i+1}y\in E(G_{1})\\},\quad
I_{2}^{2}=\\{i\in[2,n-3]:x_{i}\in N_{D}^{-}(x_{1})\\}.$

Notice that $x_{1}y,x_{2}y\not\in E(G_{1})$, otherwise either
$y^{\prime}yx_{1}x_{n-2}\ldots x_{2}$ or $y^{\prime}yx_{2}\ldots x_{n-2}x_{1}$
is a transversal Hamilton path in $\mathcal{G}$, a contradiction. Recall that
$d_{D}^{-}(x_{1})\geq\frac{n-3}{2}$. Hence,
$|I_{1}^{2}|+|I_{2}^{2}|\geq\frac{n-3}{2}+\frac{n-3}{2}=n-3$. Together with
$I_{1}^{2}\cap I_{2}^{2}\subseteq[2,n-3]$, there exists an $i_{2}$ in
$I_{1}^{2}\cap I_{2}^{2}$. Hence, $y^{\prime}yx_{i_{2}+1}\ldots
x_{n-2}x_{1}x_{i_{2}}\ldots x_{2}$ is a transversal Hamilton path in
$\mathcal{G}$ (see Figure 2 (a)), which is a contradiction.

Figure 2.

Subcase 2.2. $yy^{\prime}\notin E(G_{n-1})$.

Let

$I_{1}^{3}=\\{i\in[n-2]:x_{i}\in N_{D}^{-}(y)\\},\quad
I_{2}^{3}=\\{i\in[n-2]:x_{i+1}y\in E(G_{n-1})\\}.$

It is routine to check that $I_{1}^{3}\cap I_{2}^{3}=\emptyset$. Otherwise,
let $i_{3}\in I_{1}^{3}\cap I_{2}^{3}$. Then $x_{1}\ldots
x_{i_{3}}yx_{i_{3}+1}\ldots x_{n-2}x_{1}$ is a rainbow cycle of length $n-1$
in $\mathcal{G}$, which contradicts the assumption of Case 2. Note that
$I_{1}^{3}\cup I_{2}^{3}\subseteq[n-2]$ and $|I_{2}^{3}|\geq\frac{n-1}{2}$.
Then $|I_{1}^{3}|\leq\frac{n-3}{2}$, i.e., $d_{D}^{-}(y)\leq\frac{n-3}{2}$.
Similarly, we have $d_{D}^{-}(y^{\prime})\leq\frac{n-3}{2}$. Now, we give the
following claim.

######  Claim 3.3.

$yy^{\prime}\notin E(G_{1})$.

###### Proof of Claim 3.3.

Suppose to the contrary that $yy^{\prime}\in E(G_{1})$. In view of Subcase
2.1, we can assume that
$\\{G_{i}[V\backslash\\{y,y^{\prime}\\}]:i\in[2,n-1]\\}$ contains no
transversal Hamilton cycles. Hence $x_{1}x_{2}\notin E(G_{n-1})$. Let

$I_{1}^{4}=\\{i\in[2,n-3]:x_{i}\in N_{D}^{-}(x_{1})\\},\quad
I_{2}^{4}=\\{i\in[2,n-3]:x_{i+1}x_{2}\in E(G_{n-1})\\}.$

Then $|I_{1}^{4}|+|I_{2}^{4}|\geq\frac{n-3}{2}+\frac{n-1}{2}=n-2$. Since
$I_{1}^{4}\cup I_{2}^{4}\subseteq[2,n-2]$, one has $I_{1}^{4}\cap
I_{2}^{4}\neq\emptyset$. Let $i_{4}\in I_{1}^{4}\cap I_{2}^{4}$. Then
$x_{1}x_{i_{4}}x_{i_{4}-1}\ldots x_{2}x_{i_{4}+1}\ldots x_{n-2}x_{1}$ is a
transversal Hamilton cycle inside
$\\{G_{i}[V\backslash\\{y,y^{\prime}\\}]:i\in[2,n-1]\\}$, a contradiction. ∎

Define

$I_{1}^{5}=\\{i\in[n-2]:x_{i}y\in E(G_{1})\\},\quad
I_{2}^{5}=\\{i\in[n-2]:x_{i+1}y\in E(G_{n-1})\\}.$

By Claim 3.3 and the fact that $yy^{\prime}\not\in E(G_{n-1})$, we have
$|I_{1}^{5}|+|I_{2}^{5}|\geq\frac{n-1}{2}+\frac{n-1}{2}=n-1$. Then
$I_{1}^{5}\cap I_{2}^{5}\neq\emptyset$ and choose $i_{5}\in I_{1}^{5}\cap
I_{2}^{5}$. Hence, $P^{\prime\prime}:=x_{2}\ldots x_{i_{5}}yx_{i_{5}+1}\ldots
x_{n-2}x_{1}$ is a rainbow path inside $\mathcal{G}$. For convenience, we
rewrite $P^{\prime\prime}=x^{1}\ldots x^{n-1}$ such that $x^{1}:=x_{2}$ and
$x^{n-1}:=x_{1}$. Let

$I_{1}^{6}=\\{i\in[n-3]\backslash\\{i_{5}-1\\}:y^{\prime}x^{i+1}\in
E(G_{i_{5}})\\},\quad I_{2}^{6}=\\{i\in[n-3]\backslash\\{i_{5}\\}:x^{i}\in
N_{D}^{-}(x^{n-1})\\}.$

Clearly, $yy^{\prime}\notin E(G_{i_{5}})$. Otherwise,
$y^{\prime}yx_{i_{5}+1}\ldots x_{n-2}x_{1}x_{2}\ldots x_{i_{5}}$ is a
transversal Hamilton path in $\mathcal{G}$, a contradiction. Furthermore,
$y^{\prime}x^{n-1},\,y^{\prime}x^{1}\notin E(G_{i_{5}})$. Notice that
$y=x^{i_{5}}$ and $d_{D}^{+}(y)=d_{D}^{+}(y^{\prime})=0$. Hence
$|I_{1}^{6}|+|I_{2}^{6}|\geq\frac{n-1}{2}+\frac{n-3}{2}=n-2$. Therefore,
$I_{1}^{6}\cap I_{2}^{6}\neq\emptyset$ and choose $i_{6}\in I_{1}^{6}\cap
I_{2}^{6}$. Then $i_{6}\notin\\{i_{5}-1,i_{5}\\}$ and so
$x^{i_{6}},x^{i_{6}+1}\neq y$. By the definition of $I_{2}^{6}$ and $D$, we
have $x^{i_{6}}x^{i_{6}+1},x^{i_{6}}x^{n-1}\in E(G_{i_{6}+1})$ if $i_{6}\leq
i_{5}-1$, and $x^{i_{6}}x^{i_{6}+1},x^{i_{6}}x^{n-1}\in E(G_{i_{6}})$ if
$i_{6}\geq i_{5}+1$. Hence,
$P^{\prime\prime}-\\{x^{i_{6}}x^{i_{6}+1}\\}+\\{y^{\prime}x^{i_{6}+1},x^{i_{6}}x^{n-1}\\}$
forms a transversal Hamilton path in $\mathcal{G}$ (see Figure 2 (b)), which
is also a contradiction.

Therefore, we obtain $d_{D}^{-}(x_{i})\leq d_{D}^{-}(x_{1})\leq\frac{n-5}{2}$
for all $i\in[n-2].$ Recall that
$d_{D}^{-}(y),\,d_{D}^{-}(y^{\prime})\leq\frac{n-3}{2}$. Thus
$|A(D)|\leq(n-2)\frac{n-5}{2}+(n-3)<(n-2)\frac{n-3}{2}$, a contradiction. This
implies that there exists a transversal Hamilton path in $\mathcal{G}$.

This completes the proof of Theorem 1.3. ∎

##  4\. Proof of Theorem 1.6

###  4.1. Preliminaries

In this subsection, we give some preliminaries. Firstly, we define the
extremality for a single graph.

######  Definition 4.1 ([2024cheng]).

Let $\epsilon>0$ and $G$ be a graph on vertex set $V$ of size $n$. We call $G$
is $\epsilon$-extremal if there exists a partition ${A}\cup{B}\cup{C}$ of $V$
such that $|{A}|=|{B}|=(\frac{1}{2}-\epsilon)n$, and one of the following
holds:

  1. (i)

$d_{G}(a,{A})\geq(\frac{1}{2}-2\epsilon)n$ for all $a\in{A}$ and
$d_{G}(b,{B})\geq(\frac{1}{2}-2\epsilon)n$ for all $b\in{B}$;

  2. (ii)

$d_{G}(a,{B})\geq(\frac{1}{2}-2\epsilon)n$ for all $a\in{A}$ and
$d_{G}(b,{A})\geq(\frac{1}{2}-2\epsilon)n$ for all $b\in{B}$.

For convenience, we say $G$ is $(\epsilon,K_{\lceil\frac{n}{2}\rceil}\cup
K_{\lfloor\frac{n}{2}\rfloor})$-extremal if (i) holds; and $G$ is
$(\epsilon,K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor})$-extremal if
(ii) holds. We always call $({A},{B},{C})$ a characteristic partition of $G$.

Let $\mathcal{G}=\\{G_{1},\ldots,G_{n}\\}$ be a graph collection on a common
vertex set $V$ of size $n$ and $\delta(\mathcal{G})\geq\frac{n}{2}-1$. Let
$0<\alpha,\beta,\delta<1$. We say $\mathcal{G}$ is $(\alpha,\beta)$-strongly
stable if $G_{i}$ is $\alpha$-extremal for at most $(1-\beta)n$ colors
$i\in[n]$. Assume that $G_{1},\ldots,G_{m}$ are all $\alpha$-extremal graphs
inside $\mathcal{G}$. By Definition 4.1, we can fix a characteristic partition
$({A_{i}},{B_{i}},{C_{i}})$ of $G_{i}$ for each $i\in[m]$. We say $G_{i}$ and
$G_{j}$ are $\delta$-crossing if $G_{i}$ and $G_{j}$ are $\alpha$-extremal and
$|{A_{i}}\Delta{A_{j}}|\geq\delta n$, $|{A_{i}}\Delta{B_{j}}|\geq\delta n$.
For $i\in[m]$, define $I_{i}$ to be the set of $j\in[m]$ such that $G_{i}$ and
$G_{j}$ are $\delta$-crossing. Under the above characteristic partitions, we
say $\mathcal{G}$ is $(\alpha,\delta)$-weakly stable if
$\sum_{i\in[m]}|I_{i}|\geq 2\delta m^{2}$.

Cheng and Staden [2024cheng]*Lemma 5.3 proved the following result.

######  Lemma 4.2 ([2024cheng]).

Assume $0<\frac{1}{n}\ll\mu\ll\alpha\ll\beta,\epsilon\ll\delta\ll 1$. Let
$\mathcal{G}=\\{G_{1},\ldots,G_{n}\\}$ be a graph collection on a common
vertex set $V$ of size $n$ and $\delta(\mathcal{G})\geq(\frac{1}{2}-\mu)n$. If
$\mathcal{G}$ is either $(\alpha,\beta)$-strongly stable or
$(\epsilon,\delta)$-weakly stable, then $\mathcal{G}$ contains a transversal
Hamilton cycle.

The following theorem characterizes the structure of almost balanced graph
collections (i.e., almost all graphs in the graph collection have an almost
balanced common vertex bipartition such that their subgraphs induced by the
bipartition are close to complete bipartite graphs) that do not contain
transversal Hamilton cycles. For the sake of readability, we postpone its
proof in Section 5.

######  Theorem 4.3.

Let $0<\frac{1}{n}\ll\delta\ll 1$ and $0\leq\gamma\leq 3{\delta}$. Assume
$\mathcal{C}$ is a set of $n$ colors and
$\mathcal{G}=\\{G_{i}:i\in\mathcal{C}\\}$ is collection of graphs on a common
vertex set $V$ of size $n$ with $\delta(\mathcal{G})\geq\frac{n}{2}-1$. Let
$\mathcal{C}^{\prime}\cup\mathcal{C}^{\prime\prime}$ be a partition of
$\mathcal{C}$ with $|\mathcal{C}^{\prime\prime}|\leq{\delta}n$, and let $A\cup
B$ be a partition of $V$ with $|A|=\lceil\frac{n}{2}-1\rceil+\gamma n$.
Suppose that $G_{i}[B]=\emptyset$ for all $i\in\mathcal{C}^{\prime}$ and
$\mathcal{G}$ does not contain a transversal Hamilton cycle. Then
$\mathcal{G}$ must be one of the graph collections described in Theorem 1.6.

###  4.2. Proof of Theorem 1.6

In this subsection, we give the proof of Theorem 1.6.

###### Proof of Theorem 1.6.

Suppose that $\mathcal{G}$ does not contain transversal Hamilton cycles. We
are to prove that $\mathcal{G}$ must be a graph collection described in
Theorem 1.6. Let $0<\frac{1}{n}\ll\alpha\ll\beta,\epsilon\ll\delta\ll\eta\ll
1$. By Lemma 4.2, we know $\mathcal{G}$ is not $(\alpha,\beta)$-strongly
stable. Thus, there are at least $(1-\beta)n$ graphs in $\mathcal{G}$ such
that each of them is $\alpha$-extremal, and hence $\epsilon$-extremal.
Therefore, there exists a constant $\beta^{\prime}\,(<\beta)$ such that the
number of $\epsilon$-extremal graphs in $\mathcal{G}$ is exactly
$(1-\beta^{\prime})n$. Without loss of generality, assume that for each
$i\in[(1-\beta^{\prime})n]$, $G_{i}$ is $\epsilon$-extremal. By Definition
4.1, we can fix a characteristic partition
$(\tilde{A_{i}},\tilde{B_{i}},\tilde{C_{i}})$ for each $G_{i}$ with
$i\in[(1-\beta^{\prime})n]$.

Under the above characteristic partition, applying Lemma 4.2 again yields that
$\mathcal{G}$ is not $(\epsilon,\delta)$-weakly stable. Therefore,
$\sum_{i\in[(1-\beta^{\prime})n]}|I_{i}|<2\delta(1-\beta^{\prime})^{2}n^{2}$.
Without loss of generality, assume that
$|I_{1}|=\min\\{|I_{i}|:i\in[(1-\beta^{\prime})n]\\}$. Then $|I_{1}|\leq
2\delta(1-\beta^{\prime})n$. For every $i\in[(1-\beta^{\prime})n]\backslash
I_{1}$, based on the definition of $I_{1}$, we have either
$|\tilde{A_{1}}\Delta\tilde{A_{i}}|<\delta n$ or
$|\tilde{A_{1}}\Delta\tilde{B_{i}}|<\delta n$. By swapping the labels of
$\tilde{A_{i}}$ and $\tilde{B_{i}}$, we have
$|\tilde{A_{1}}\Delta\tilde{A_{i}}|,|\tilde{B_{1}}\Delta\tilde{B_{i}}|<\delta
n$ for every $i\in[(1-\beta^{\prime})n]\backslash I_{1}$. Denote
$[m]:=[(1-\beta^{\prime})n]\backslash I_{1}$ and $\mathcal{C}_{bad}:=[m+1,n]$.
Then $m\geq(1-\beta^{\prime}-2\delta)n\geq(1-3\delta)n$. By adding colors to
$\mathcal{C}_{bad}$ if necessary we may assume $m=(1-3\delta)n$. Recall that
$\alpha\ll\epsilon$. Hence for each $i\in[2,m]$, there exists a new partition
$(A_{i},B_{i},C_{i})$ of $G_{i}$ such that

  * (B1)

if $G_{i}$ is $(\epsilon,K_{\lceil\frac{n}{2}\rceil}\cup
K_{\lfloor\frac{n}{2}\rfloor})$-extremal, then for $Y\in\\{A,B\\}$ we have
$\tilde{Y_{i}}\subseteq Y_{i}$ and
$d_{G_{i}}(v,Y_{i})\geq(\frac{1}{2}-3\sqrt{\delta})n$ for each vertex $v\in
Y_{i}$,

  * (B2)

if $G_{i}$ is
$(\epsilon,K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor})$-extremal,
then for $Y\in\\{A,B\\}$ we have $\tilde{Y_{i}}\subseteq Y_{i}$ and
$d_{G_{i}}(v,Z_{i})\geq(\frac{1}{2}-3\sqrt{\delta})n$ for each vertex $v\in
Y_{i}$,

  * (B3)

subject to (B1)-(B2), each vertex in $V$ lies in as many as possible
$A_{i}\cup B_{i}$ for $i\in[2,m]$.

Denote $(A_{1},B_{1},C_{1}):=(\tilde{A}_{1},\tilde{B}_{1},\tilde{C}_{1})$.
Expand $A_{1}\cup B_{1}$ to be an equitable partition $A\cup B$ of $V$. Let
$\mathcal{C}_{1}\cup\mathcal{C}_{2}$ be a partition of $[m]$ with

$\displaystyle\mathcal{C}_{1}=\\{i\in[m]:\
G_{i}~{}\textrm{is}~{}(\epsilon,K_{\lceil\frac{n}{2}\rceil}\cup
K_{\lfloor\frac{n}{2}\rfloor})\textrm{-extremal}\\},$
$\displaystyle\mathcal{C}_{2}=\\{i\in[m]:\
G_{i}~{}\textrm{is}~{}(\epsilon,K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor})\textrm{-extremal}\\}.$

Hence for $i\in[2,m]$ and $Y\in\\{A,B\\}$, we have $|Y_{1}\Delta
Y_{i}|\leq|\tilde{Y_{1}}\Delta\tilde{Y_{i}}|+|\tilde{C}_{i}|\leq\delta
n+2{\epsilon}n<2\delta n$.

In the following of our proof, we shall emphasize that if we say a set of
vertices $V^{\prime}\subseteq B$ is moved from $B$ to $A$, then the partition
of $V$ becomes to $(A\cup V^{\prime})\cup(B\backslash V^{\prime})$. In order
not to introduce too much notation, we still denote the resulted partition by
$A\cup B$. Moreover, unless otherwise specified, we assume $Y\in\\{A,B\\}$ and
$\\{Y,Z\\}=\\{A,B\\}$.

Now, we define the set of bad vertices. Let
$\hat{\mathcal{C}}:=\cup_{k\in[2]}\psi(\mathcal{C}_{k}),$ where
$\psi(\mathcal{C}_{k})=\mathcal{C}_{k}$ if $|\mathcal{C}_{k}|\geq\eta n$ and
$\psi(\mathcal{C}_{k})=\emptyset$ otherwise. Clearly,
$|\hat{\mathcal{C}}|\geq(1-3\delta-\eta)n$. Define

$X=\\{x\in V:x\not\in A_{i}\cup B_{i}~{}\textrm{for at
least}~{}3\sqrt{\delta}|\hat{\mathcal{C}}|~{}\textrm{colors}~{}i\in\hat{\mathcal{C}}\\},$
$X_{Y}=\\{x\in Y\backslash X:x\not\in Y_{i}~{}\textrm{for at
least}~{}10\sqrt{\delta}|\hat{\mathcal{C}}|~{}\textrm{colors}~{}i\in\hat{\mathcal{C}}\\}.$

Recall that for all $i\in\hat{\mathcal{C}}$, we have $|C_{i}|\leq
2{\epsilon}n$ and $|Y_{1}\Delta Y_{i}|<2\delta n$. Hence
$3\sqrt{\delta}|\hat{\mathcal{C}}||X|\leq 2{\epsilon}n|\hat{\mathcal{C}}|$ and
$10\sqrt{\delta}|\hat{\mathcal{C}}||X_{Y}|\leq\sum_{i\in\hat{\mathcal{C}}}|Y\backslash
Y_{i}|\leq(2\delta+2{\epsilon})n|\hat{\mathcal{C}}|$. It follows that
$|X|\leq\sqrt{\epsilon}n$ and $|X_{Y}|<\frac{1}{4}\sqrt{\delta}n$.

For $k\in[2]$, define

$X_{Y}^{k}=\left\\{\begin{array}[]{ll}\\{x\in X_{Y}:x\in Y_{i}~{}\textrm{for
at
least}~{}3\sqrt{\delta}n~{}\textrm{colors}~{}i\in{\mathcal{C}_{k}}\\},&\textrm{if
$|\mathcal{C}_{k}|\geq\eta n$,}\\\\[5.0pt]
\emptyset,&\textrm{otherwise.}\end{array}\right.$

Recall that $\\{Y,Z\\}=\\{A,B\\}$. For a vertex $x\in
X_{Y}\backslash(\cup_{k\in[2]}X_{Y}^{k})$, we know $x\in Y_{i}$ for at most
$6\sqrt{\delta}n$ colors $i\in\hat{\mathcal{C}}$ and $x\in A_{i}\cup B_{i}$
for at least $(1-3\sqrt{\delta})|\hat{\mathcal{C}}|$ colors
$i\in\hat{\mathcal{C}}$. Thus, $x\in Z_{i}$ for at least
$(1-3\sqrt{\delta})|\hat{\mathcal{C}}|-6\sqrt{\delta}n\geq(1-10\sqrt{\delta})|\hat{\mathcal{C}}|$
colors $i\in\hat{\mathcal{C}}$. This implies that $x\in Y\backslash Y_{i}$ for
at least $(1-10\sqrt{\delta})|\hat{\mathcal{C}}|$ colors
$i\in\hat{\mathcal{C}}$. Hence

$|X_{Y}\backslash(\cup_{k\in[2]}X_{Y}^{k})|(1-10\sqrt{\delta})|\hat{\mathcal{C}}|\leq\sum_{i\in\hat{\mathcal{C}}}|Y\backslash
Y_{i}|\leq\sum_{i\in\hat{\mathcal{C}}}(|Y\backslash Y_{1}|+|Y_{1}\Delta
Y_{i}|)\leq(2\delta+2\epsilon)n|\hat{\mathcal{C}}|.$

It follows that $|X_{Y}\backslash(\cup_{k\in[2]}X_{Y}^{k})|\leq 4\delta n$.
Then move vertices in $X_{A}\backslash(\cup_{k\in[2]}X_{A}^{k})$ to $B$ and
vertices in $X_{B}\backslash(\cup_{k\in[2]}X_{B}^{k})$ to $A$. Without loss of
generality, assume that $|B|-|A|=r$, where $0\leq r\leq 8{\delta}n+\sigma$,
where $\sigma=0$ if $n$ is even and $\sigma=1$ if $n$ is odd. Define
$V_{bad}:=\cup_{k\in[2]}(X^{k}_{A}\cup X^{k}_{B})\cup X$. Obviously,
$|V_{bad}|<(\sqrt{\epsilon}+\frac{1}{2}\sqrt{\delta})n$. Moreover, each vertex
in $Y\backslash V_{bad}$ lies in $Y_{i}$ for at least
$(1-10\sqrt{\delta})|\hat{\mathcal{C}}|$ colors $i\in\hat{\mathcal{C}}$.

Next, we give an application of the transversal blow-up lemma (see
[2023chengBlowup]) for embedding transversal Hamilton paths inside very dense
bipartite graph collections, which can be proved by minor modifications to the
proof of [2024cheng]*Lemma 6.1, and we omit the proof here.

######  Claim 4.4.

Assume $W,Z\in\\{A,B\\}$. Let $W^{*}\subseteq W\backslash V_{bad}$ and
$Z^{*}\subseteq Z\backslash V_{bad}$, where $|W^{*}|,|Z^{*}|\geq\eta n$,
$W^{*}\cap Z^{*}=\emptyset$ and $|W^{*}|-|Z^{*}|=t\in\\{0,1\\}$. Let
$T^{*}=Z^{*}$ if $t=0$ and $T^{*}=W^{*}$ if $t=1$. Let
$\mathcal{C^{*}}\subseteq\mathcal{C}$ satisfy
$|\mathcal{C^{*}}|=|W^{*}|+|Z^{*}|-1$, where
$\mathcal{C^{*}}\subseteq\mathcal{C}_{1}$ if $W=Z$ and
$\mathcal{C^{*}}\subseteq\mathcal{C}_{2}$ if $W\neq Z$. Let $W^{-}\subseteq
W^{*}$ and $T^{+}\subseteq T^{*}$ with $|W^{-}|,|T^{+}|\geq\frac{\eta n}{8}$.
Then there is a transversal Hamilton path in
$\\{G_{i}[W^{*},Z^{*}]:i\in\mathcal{C}^{*}\\}$ starting in $W^{-}$ and ending
in $T^{+}$.

The subsequent result can be used to connect two disjoint short rainbow paths
into a single short rainbow path.

######  Claim 4.5 (Connecting tool).

Assume $P=u_{1}u_{2}\ldots u_{s}$ and $Q=v_{1}v_{2}\ldots v_{t}$ are two
disjoint rainbow paths inside $\mathcal{G}$ and $s+t\leq 5\eta n$.

  1. (i)

If $u_{s}\in A\backslash V_{bad}$, $v_{1}\in B\backslash V_{bad}$ and
$|\mathcal{C}_{2}\backslash col(P\cup Q)|\geq 11\sqrt{\delta}n$, then there
are three colors $c_{1},c_{2},c_{3}\in\mathcal{C}_{2}\backslash col(P\cup Q)$
and two vertices $w_{1}\in B\backslash(V(P\cup Q)\cup V_{bad})$,
$w_{1}^{\prime}\in A\backslash(V(P\cup Q)\cup V_{bad})$ such that
$u_{1}Pu_{s}w_{1}w_{1}^{\prime}v_{1}Qv_{t}$ is a rainbow path with colors
$col(P\cup Q)\cup\\{c_{1},c_{2},c_{3}\\}$.

  2. (ii)

If $u_{s},v_{1}\in Y\backslash V_{bad}$ and $|\mathcal{C}_{2}\backslash
col(P\cup Q)|\geq 11\sqrt{\delta}n$, then there are two colors
$c_{1},c_{2}\in\mathcal{C}_{2}\backslash col(P\cup Q)$ and one vertex
$w_{1}\in Z\backslash(V(P\cup Q)\cup V_{bad})$ such that
$u_{1}Pu_{s}w_{1}v_{1}Qv_{t}$ is a rainbow path with colors $col(P\cup
Q)\cup\\{c_{1},c_{2}\\}$.

  3. (iii)

If $u_{s},v_{1}\in Y\backslash V_{bad}$ and $|\mathcal{C}_{1}\backslash
col(P\cup Q)|\geq 11\sqrt{\delta}n$, then there are two colors
$c_{1},c_{2}\in\mathcal{C}_{1}\backslash col(P\cup Q)$ and one vertex
$w_{1}\in Y\backslash(V(P\cup Q)\cup V_{bad})$ such that
$u_{1}Pu_{s}w_{1}v_{1}Qv_{t}$ is a rainbow path with colors $col(P\cup
Q)\cup\\{c_{1},c_{2}\\}$. (See Figure 3.)

Figure 3. Connecting tool.

###### Proof of Claim 4.5.

We only give the proof of (i), the other two statements can be proved by a
similar discussion, whose procedures are omitted.

Note that $u_{s},v_{1}\not\in V_{bad}$. Then $u_{s}$ (resp. $v_{1}$) lies in
$A_{i}$ (resp. $B_{i}$) for at least $(1-10\sqrt{\delta})|\hat{\mathcal{C}}|$
colors $i\in\hat{\mathcal{C}}$. Since $|\mathcal{C}_{2}\backslash col(P\cup
Q)|\geq 11\sqrt{\delta}n$, we obtain that $u_{s}$ (resp. $v_{1}$) lies in
$A_{i}$ (resp. $B_{i}$) for at least
$11\sqrt{\delta}n-10\sqrt{\delta}|\hat{\mathcal{C}}|\geq\sqrt{\delta}n$ colors
$i\in\mathcal{C}_{2}$. Hence there are two colors
$c_{1},c_{2}\in\mathcal{C}_{2}\backslash col(P\cup Q)$ such that $u_{s}\in
A_{c_{1}}$ and $v_{1}\in B_{c_{2}}$. It is routine to check that

$\displaystyle|N_{G_{c_{1}}}(u_{s})\cap(B\backslash V_{bad})|$
$\displaystyle\geq$ $\displaystyle|N_{G_{c_{1}}}(u_{s})\cap
B_{c_{1}}|-|B_{1}\Delta B_{c_{1}}|-|X\cup X_{A}\cup X_{B}|$
$\displaystyle\geq$
$\displaystyle(\frac{1}{2}-3\sqrt{\delta})n-(2\delta+\sqrt{\epsilon}+\frac{1}{2}\sqrt{\delta})n\geq(\frac{1}{2}-5\sqrt{\delta})n.$

Hence there exists a vertex $w_{1}\in N_{G_{c_{1}}}(u_{s})\cap(B\backslash
V_{bad})$ that avoids $V(P\cup Q)$. Similarly, since $w_{1}\notin V_{bad}$,
there is a color $c_{3}\in\mathcal{C}_{2}\backslash(col(P\cup
Q)\cup\\{c_{1},c_{2}\\})$ such that $w_{1}\in B_{c_{3}}$. On the other hand,

$\displaystyle|N_{G_{c_{2}}}(v_{1})\cap N_{G_{c_{3}}}(w_{1})\cap(A\backslash
V_{bad})|$ $\displaystyle\geq$
$\displaystyle|N_{G_{c_{2}}}(v_{1})\cap(A\backslash
V_{bad})|+|N_{G_{c_{3}}}(w_{1})\cap(A\backslash V_{bad})|-\frac{n}{2}$
$\displaystyle\geq$ $\displaystyle(\frac{1}{2}-10\sqrt{\delta})n.$

Hence, there is a vertex $w_{1}^{\prime}\in N_{G_{c_{2}}}(v_{1})\cap
N_{G_{c_{3}}}(w_{1})\cap(A\backslash V_{bad})$ that avoids $V(P\cup Q)$.
Therefore, $u_{1}Pu_{s}w_{1}w_{1}^{\prime}v_{1}Qv_{t}$ is a rainbow path
inside $\mathcal{G}$ with colors $col(P\cup Q)\cup\\{c_{1},c_{2},c_{3}\\}$. ∎

Based on the sizes of $|\mathcal{C}_{1}|$ and $|\mathcal{C}_{2}|$, our proof
is distinguished into the following three cases.

Case 1. $|\mathcal{C}_{1}|<\eta n$.

In this case, each vertex in $Y\backslash(X\cup X_{Y}^{2})$ belongs to $Y_{i}$
for at least $(1-10\sqrt{\delta})|\mathcal{C}_{2}|$ colors
$i\in\mathcal{C}_{2}$. Recall that $|B|-|A|=r$ with $0\leq r\leq
8{\delta}n+\sigma$, where $\sigma=0$ if $n$ is even and $\sigma=1$ if $n$ is
odd. The proof is divided into four steps, as shown in the Figure 4.

Figure 4. Step 1 - Step 3. The vertex with red (resp. green) lies in
$A\backslash V_{bad}$ (resp. $B\backslash V_{bad}$), and the symbol
“$\blacklozenge$” denotes a vertex that is used to connect rainbow paths.

Step 1. Balance the number of vertices in $A$ and $B$.

In this step, we claim that if $\mathcal{G}$ is not a graph collection
described in Theorem 1.6, then by moving vertices in $B\cap V_{bad}$ or
deleting rainbow paths inside $\mathcal{G}[B]$, we can make the number of
remaining vertices in $B$ and $A$ differ by $\sigma$. Denote $s:=|V_{bad}\cap
B|$. If $|B|-|A|-\sigma\leq 2s$, then move $\frac{|B|-|A|-\sigma}{2}$ vertices
in $V_{bad}\cap B$ to $A$, we can get our desired result. Hence, it suffices
to consider $|B|-|A|-\sigma>2s$. We first move all vertices in $V_{bad}\cap B$
to $A$. Then $B\cap V_{bad}=\emptyset$. Assume that $\\{Q_{1},\ldots,Q_{t}\\}$
is a set of disjoint maximal rainbow paths in $\mathcal{G}[B]$. If
$|E(Q_{1})|+\cdots+|E(Q_{t})|\geq|B|-|A|-\sigma$, then there must exist a set
of disjoint rainbow paths, say
$\\{Q_{1}^{\prime},\ldots,Q_{t^{\prime}}^{\prime}\\}$, such that
$|E(Q_{1}^{\prime})|+\cdots+|E(Q_{t^{\prime}}^{\prime})|=|B|-|A|-\sigma$. That
is,
$|A|-t^{\prime}=|B|-(|V(Q_{1}^{\prime})|+\cdots+|V(Q_{t^{\prime}}^{\prime})|)-\sigma$.
Using Claim 4.5 (ii) to connect
$Q_{1}^{\prime},\ldots,Q_{t^{\prime}}^{\prime}$ into a single rainbow path
$P^{1}$, whose endpoints are in different parts. (In fact, by using Claim 4.5
we only get a rainbow path with two endpoints in $B$. But we usually want to
find a rainbow path with endpoints in different parts. Hence we extend it by
using an unused color of $\mathcal{C}_{2}$ and an unused vertex in $A$).
Therefore, $|A\backslash V(P^{1})|=|B\backslash V(P^{1})|-\sigma$, as desired.

In what follows, it suffices to consider
$|E(Q_{1})|+\cdots+|E(Q_{t})|<|B|-|A|-\sigma=r-2s-\sigma$. Now, we move all
vertices of $Q_{1},\ldots,Q_{t}$ to $A$. Let
$\mathcal{C}^{\prime}=\mathcal{C}\backslash col(\cup_{i\in[t]}Q_{i})$. Hence

$\displaystyle|A|$
$\displaystyle\leq\frac{n-r}{2}+s+2(r-2s-\sigma)\leq\frac{n}{2}+16{\delta}n,$
$\displaystyle|B|$
$\displaystyle\geq\frac{n+r}{2}-s-2(r-2s-\sigma)\geq\frac{n}{2}-16{\delta}n,$
$\displaystyle|\mathcal{C}^{\prime}|$
$\displaystyle=|\mathcal{C}|-(|E(Q_{1})|+\cdots+|E(Q_{t})|)\geq(1-8\delta)n.$

By the maximality of $\\{Q_{1},\ldots,Q_{t}\\}$, we know $G_{i}[B]=\emptyset$
for all $i\in\mathcal{C}^{\prime}$. It follows from
$\delta(\mathcal{G})\geq\lceil\frac{n}{2}-1\rceil$ that
$|A|\geq\lceil\frac{n}{2}-1\rceil$. Together with Theorem 4.3, we obtain that
$\mathcal{G}$ is one of the graph collections described in Theorem 1.6, as
desired.

In this step, if we only move vertices in $V_{bad}$ from $B$ to $A$, then let
$P^{1}$ be a null graph (i.e., no vertices); otherwise, assume $P^{1}$ is a
rainbow path obtained in the above, whose length is at most $24\delta n$ and
endpoints are $u_{1}\in A\backslash V_{bad},\,v_{1}\in B\backslash V_{bad}$.
Hence $|A\backslash V(P^{1})|=|B\backslash V(P^{1})|-\sigma$.

Step 2. Construct a series of disjoint rainbow $P_{3}$ such that all centers
of them are exactly all vertices in $V_{bad}$.

Recall that $|X_{A}^{2}\cup X_{B}^{2}|\leq|X_{A}\cup
X_{B}|<\frac{1}{2}\sqrt{\delta}n$. Let $v\in X_{Y}^{2}$. If $v\in Z$, then $v$
is moved from $B$ to $A$ in Step 1. Hence $v\in X_{B}$. Therefore, $v\in
A_{i}\cup B_{i}$ for at least $(1-3\sqrt{\delta})|\mathcal{C}_{2}|$ colors
$i\in\mathcal{C}_{2}$ and $v\not\in B_{i}$ for at least
$10\sqrt{\delta}|\mathcal{C}_{2}|$ colors $i\in\mathcal{C}_{2}$. Hence, $v\in
A_{i}$ for at least $7\sqrt{\delta}|\mathcal{C}_{2}|-24\delta
n>4|X_{A}^{2}\cup X_{B}^{2}|$ colors $i\in\mathcal{C}_{2}\backslash
col(P^{1})$. If $v\in Y$ (i.e., $v$ has not been moved in Step 1), then $v$
belongs to $Y_{i}$ for at least $(3\sqrt{\delta}-24\delta)n>4|X_{A}^{2}\cup
X_{B}^{2}|$ colors $i\in\mathcal{C}_{2}\backslash col(P^{1})$. Hence, using
colors in $\mathcal{C}_{2}\backslash col(P^{1})$, we can greedily choose
$|X_{A}^{2}\cup X_{B}^{2}|$ disjoint rainbow $P_{3}$, such that all centers of
them are exactly all vertices in $X_{A}^{2}\cup X_{B}^{2}$. Moreover, if
$v\in(X_{A}^{2}\cup X_{B}^{2})\cap Y$, then the rainbow $P_{3}$ with center in
$v$ has endpoints in $Z\backslash(V_{bad}\cup V(P^{1}))$.

Connect those rainbow $P_{3}$ with centers in $Y$ (if exists) into a single
rainbow path with two endpoints in different parts by Claim 4.5 (ii). Then
connect the two resulted rainbow paths and $P^{1}$ by Claim 4.5 (i)-(ii), we
obtain a rainbow path $P^{2}=u_{1}\ldots v_{2}$ with length at most
$|E(P^{1})|+4|X_{A}^{2}\cup X_{B}^{2}|+4\leq 24\delta n+2\sqrt{\delta}n+4$ and
$v_{2}\in B\backslash V_{bad}$.

For vertices in $X$, we consider the following claim. Notice that the position
(in $A$ or $B$) of vertices in $X$ will not work in our proof, so if $v\in X$
is a vertex moved from $B$ to $A$, then we only need consider $v\in A$.

######  Claim 4.6.

Assume $X\backslash V(P^{2})=\\{x_{1},\ldots,x_{s}\\}$ with
$s\leq\sqrt{\epsilon}n$. If $x_{i}\in X\cap Y$, then there exist
$c_{i}^{1},c_{i}^{2},c_{i}^{3},c_{i}^{4}\in\mathcal{C}_{2}\backslash(col(P^{2})\cup\\{c_{\ell}^{1},c_{\ell}^{2},c_{\ell}^{3},c_{\ell}^{4}:{\ell}\in[i-1]\\})$
and $x_{i}^{1},\,x_{i}^{2},\,x_{i}^{3},x_{i}^{4}\in Z\backslash(V(P^{2})\cup
V_{bad}\cup\\{x_{\ell}^{1},\,x_{\ell}^{2},\,x_{\ell}^{3},\,x_{\ell}^{4}:{\ell}\in[i-1]\\})$
such that $x_{i}x_{i}^{k}\in E(G_{c_{i}^{k}})$ for all $k\in[4]$.

###### Proof of Claim 4.6.

Suppose there exists an $i_{0}\in[s]$ such that Claim 4.6 holds for all
$i\in[i_{0}-1]$ but does not hold for $i_{0}$. Without loss of generality,
assume that $x_{i_{0}}\in X\cap A$. Hence for all but at most three
$j\in\mathcal{C}_{2}\backslash(col(P^{2})\cup\\{c_{\ell}^{1},c_{\ell}^{2},c_{\ell}^{3},c_{\ell}^{4}:{\ell}\in[i_{0}-1]\\})$
we have $d_{G_{j}}(x_{i_{0}},B)\leq 4(i_{0}-1)+3+|V(P^{2})|$. Thus, for such a
color $j$,

$\displaystyle d_{G_{j}}(x_{i_{0}},A_{j})$ $\displaystyle\geq
d_{G_{j}}(x_{i_{0}},A)-|A\backslash A_{1}|-|A_{1}\Delta
A_{j}|-|X_{A}\backslash X_{A}^{2}|$
$\displaystyle\geq\delta(G_{j})-d_{G_{j}}(x_{i_{0}},B)-|A\backslash
A_{1}|-|A_{1}\Delta A_{j}|-|X_{A}\backslash X_{A}^{2}|$
$\displaystyle\geq\frac{n}{2}-1-(4(i_{0}-1)+3+|V(P^{2})|)-2{\epsilon}n-2\delta
n-4\delta n$ $\displaystyle\geq\frac{n}{2}-1-(4\sqrt{\epsilon}n+24\delta
n+2\sqrt{\delta}n+4)-2{\epsilon}n-6\delta n$
$\displaystyle\geq(\frac{1}{2}-3\sqrt{\delta})n.$

Hence $x_{i_{0}}\in A_{j}\cup B_{j}$. Otherwise, there exists a new
characteristic partition $(A_{j},B_{j}^{\prime},C_{j}^{\prime})$ of $G_{j}$
with $B_{j}^{\prime}=B_{j}\cup\\{x_{i_{0}}\\}$, which contradicts (B3). By the
choice of $j$, we know $x_{i_{0}}\in A_{j}\cup B_{j}$ for all but at most
three
$j\in\mathcal{C}_{2}\backslash(col(P^{2})\cup\\{c_{\ell}^{1},c_{\ell}^{2},c_{\ell}^{3},c_{\ell}^{4}:{\ell}\in[i_{0}-1]\\})$.
It is routine to check that

$\displaystyle|\mathcal{C}_{2}\backslash(col(P^{2})\cup\\{c_{\ell}^{1},c_{\ell}^{2},c_{\ell}^{3},c_{\ell}^{4}:{\ell}\in[i_{0}-1]\\})|-3$
$\displaystyle\geq$ $\displaystyle|\mathcal{C}_{2}|-24\delta
n-2\sqrt{\delta}n-4-4\sqrt{\epsilon}n-3$ $\displaystyle\geq$
$\displaystyle|\mathcal{C}_{2}|-3\sqrt{\delta}n.$

Therefore, $x_{i_{0}}\in C_{j}$ for at most $3\sqrt{\delta}n$ colors
$j\in\mathcal{C}_{2}$, which implies $x_{i_{0}}\not\in X$, a contradiction. ∎

By Claim 4.6, for each $x_{i}\in X\cap Y$, there exists a rainbow path
$Q_{x_{i}}=x_{i}^{1}x_{i}x_{i}^{2}$ with
$col(Q_{x_{i}})=\\{c_{i}^{1},c_{i}^{2}\\}\subseteq\mathcal{C}_{2}$ and
$x_{i}^{1},x_{i}^{2}\in Z\backslash V_{bad}$. Furthermore, each color or
endpoint in $Q_{x_{i}}$ can be replaced by two colors or vertices not in
$P^{2}$. Connect rainbow paths in $\\{Q_{x_{i}}:x_{i}\in X\cap Y\\}$ by Claim
4.5 (i)-(ii) into a single rainbow path with endpoints in different parts (if
$|X\cap Y|\geq 1$). Then using Claim 4.5 (i)-(ii) to connect $P^{2}$ and the
resulted two rainbow paths into a single rainbow path $P^{3}$ with endpoints
$u_{1}\in A\backslash V_{bad}$ and $v_{3}\in B\backslash V_{bad}$, whose
length is at most $|E(P^{2})|+4|X|+4\leq 24\delta
n+2\sqrt{\delta}n+4\sqrt{\epsilon}n+8$.

Step 3. Select a rainbow matching inside $\\{G_{i}[A\backslash
V(P^{3}),B\backslash V(P^{3})]:i\in\mathcal{C}_{bad}\backslash col(P^{3})\\}$.

Choose a maximum rainbow matching, say $\tilde{M}$, in $\\{G_{i}[A\backslash
V(P^{3}),B\backslash V(P^{3})]:i\in\mathcal{C}_{bad}\backslash col(P^{3})\\}$.
If $\tilde{M}$ contains an edge with color $j$ such that $G_{j}[A\backslash
V(P^{3}\cup\tilde{M}),B\backslash V(P^{3}\cup\tilde{M})]$ contains no
$2$-matching, then delete all such edges from $\tilde{M}$ and denote the
resulted rainbow matching by $M$. Connect $P^{3}$ and all rainbow edges in $M$
by Claim 4.5 (i), we obtain a rainbow path $P^{4}$ with endpoints $u_{1}\in
A\backslash V_{bad}$ and $v_{4}\in B\backslash V_{bad}$, whose length is at
most $|E(P^{3})|+12\delta n\leq 2\sqrt{\delta}n+4\sqrt{\epsilon}n+36\delta
n+8$.

Denote $\mathcal{C}_{bad}^{\prime}:=\mathcal{C}_{bad}\backslash col(P^{4})$
and let $j\in\mathcal{C}_{bad}^{\prime}$. Hence in $G_{j}$, all but at most
one vertex in $Y\backslash V(P^{3}\cup\tilde{M})$ is adjacent to at least
$\frac{n}{2}-1-|V(P^{3}\cup\tilde{M})|-1\geq(\frac{1}{2}-3\sqrt{\delta})n$
vertices in $Y$. Therefore, $G_{j}$ is
$(3\sqrt{\delta},K_{\lfloor\frac{n}{2}\rfloor}\cup
K_{\lceil\frac{n}{2}\rceil})$-extremal for all
$j\in\mathcal{C}_{bad}^{\prime}$.

Step 4. Construct two disjoint rainbow paths inside $\mathcal{G}[A\backslash
V(P^{4})]$ and $\mathcal{G}[B\backslash V(P^{4})]$ by using unused colors in
$\mathcal{C}_{1}\cup\mathcal{C}_{bad}^{\prime}$.

It is straightforward to check that

$|B\backslash V(P^{4})|-|A\backslash V(P^{4})|=|B\backslash
V(P^{1})|-|A\backslash V(P^{1})|=\sigma.$

By the construction of $P^{4}$, we know that if $w\in V(P^{4})$ is a vertex
not in $(V(P^{1})\cap B)\cup V_{bad}$, then it is possible to avoid $w$ when
construct $P^{4}$; if $i\in col(P^{4})$ is a color not in $col(P^{1}-A)\cup
col(M)$, then it is possible to avoid $i$ when construct $P^{4}$. That is, we
can assume that $w\not\in V(P^{4})$ unless $w\in(V(P^{1})\cap B)\cup V_{bad}$
and $i\not\in col(P^{4})$ unless $i\in col(P^{1}-A)\cup col(M)$.

Furthermore, in the process of choosing rainbow paths inside $\mathcal{G}[B]$
(in Step 1), one may use colors in
$\mathcal{C}_{1}\cup\mathcal{C}_{bad}^{\prime}$ before other colors and avoid
vertices in $V_{bad}\cup V(M)$. This implies that either
$\mathcal{C}_{1}\cup\mathcal{C}_{bad}^{\prime}\subseteq col(P^{1})$ or
$col(P^{1}-A)\subseteq\mathcal{C}_{1}\cup\mathcal{C}_{bad}^{\prime}$. Denote
$\tilde{\mathcal{C}}:=(\mathcal{C}_{1}\cup\mathcal{C}_{bad}^{\prime})\backslash
col(P^{1})$.

######  Claim 4.7.

Let $Q=x_{1}\ldots x_{s}$ be a rainbow path inside $\mathcal{G}$ such that
$s\leq 3\sqrt{\delta}n$, $V_{bad}\subseteq V(Q)$,
$(\mathcal{C}_{1}\cup\mathcal{C}_{bad})\backslash\tilde{\mathcal{C}}\subseteq
col(Q)$, $x_{1}\in A\backslash V_{bad}$ and $x_{s}\in B\backslash V_{bad}$. If
$|\tilde{\mathcal{C}}|-||B\backslash V(Q)|-|A\backslash V(Q)||$ is a
nonnegative even integer, then $\mathcal{G}$ has a transversal Hamilton cycle.

###### Proof of Claim 4.7.

Using colors in $\tilde{\mathcal{C}}$, we can greedily choose two disjoint
rainbow paths $P^{5}$ and $P^{6}$ in $\mathcal{G}[A\backslash V(Q)]$ and
$\mathcal{G}[B\backslash V(Q)]$ with lengths
$\frac{|\tilde{\mathcal{C}}|-(|B\backslash V(Q)|-|A\backslash V(Q)|)}{2}$ and
$\frac{|\tilde{\mathcal{C}}|+(|B\backslash V(Q)|-|A\backslash V(Q)|)}{2}$
respectively, whose endpoints are $u_{5},v_{5}\in A\backslash V_{bad}$ and
$u_{6},v_{6}\in B\backslash V_{bad}$. (Note that if a rainbow path has length
$0$, then it contains one vertex instead of the null graph.) Applying Claim
4.5 (i)-(ii) to connect $Q,P^{5}$ and $P^{6}$ in turn, we get a rainbow path
$P$ with endpoints $x_{1}\in A\backslash V_{bad}$ and $v_{6}\in B\backslash
V_{bad}$. Clearly, $|V(P)|\leq 3\sqrt{\delta}n+3\delta n+\eta n+4$ and
$|A\backslash V(P)|=|B\backslash V(P)|$.

Notice that $x_{1},v_{6}\not\in V_{bad}$. Hence there exist
$i_{1},i_{2}\in\mathcal{C}_{2}\backslash col(P)$ such that $x_{1}\in
A_{i_{1}}$ and $v_{6}\in B_{i_{2}}$. Let $W^{*}=A\backslash
V(P),\,T^{*}=B\backslash V(P)$,
$\mathcal{C}^{*}=\mathcal{C}\backslash(col(P)\cup\\{i_{1},i_{2}\\})$,
$W^{-}=N_{G_{i_{2}}}(v_{6})\cap W^{*}$ and $T^{+}=N_{G_{i_{1}}}(x_{1})\cap
Z^{*}$. It is routine to check that $|W^{*}|=|T^{*}|$,
$|\mathcal{C}^{*}|=|W^{*}|+|T^{*}|-1$,

$\displaystyle|W^{-}|$ $\displaystyle\geq d_{G_{i_{2}}}(v_{6},A)-|V(P)|\geq
d_{G_{i_{2}}}(v_{6},A_{i_{2}})-|A_{1}\Delta A_{i_{2}}|-|X_{A}\backslash
X_{A}^{2}|-|V(P)|$ $\displaystyle\geq(\frac{1}{2}-3\sqrt{\delta})n-2\delta
n-4{\delta}n-|V(P)|>(\frac{1}{2}-2\eta)n.$

Similarly, $|T^{+}|>\eta n$. Applying Claim 4.4 yields that
$\\{G_{i}[W^{*},T^{*}]:i\in\mathcal{C}^{*}\\}$ contains a transversal path
$P^{\prime}$ starting at $v^{\prime}\in W^{-}$ and ending at $u^{\prime}\in
T^{+}$. Thus, $x_{1}Pv_{6}v^{\prime}P^{\prime}u^{\prime}x_{1}$ is a
transversal Hamilton cycle inside $\mathcal{G}$ (see Figure 5). ∎

Figure 5.

If $n$ is even and $|\tilde{\mathcal{C}}|$ is even, or $n$ is odd and
$|\tilde{\mathcal{C}}|$ is odd, then in view of Claim 4.7, there exists a
transversal Hamilton cycle inside $\mathcal{G}$, a contradiction. Hence, it
suffices to consider $n$ is even and $|\tilde{\mathcal{C}}|$ is odd, or $n$ is
odd and $|\tilde{\mathcal{C}}|$ is even. Therefore, either
$|\tilde{\mathcal{C}}|-(|B\backslash V(P^{4})|-|A\backslash V(P^{4})|)$ is a
positive odd integer or $|\tilde{\mathcal{C}}|=0$ and $n$ is odd.

######  Claim 4.8.

  1. (i)

If $|\tilde{\mathcal{C}}|\geq 1$, then $E(G_{i}[A])=\emptyset$ for all
$i\in\mathcal{C}\backslash\tilde{\mathcal{C}}$,

  2. (ii)

$E(G_{i}[A,B])=\emptyset$ for all $i\in\tilde{\mathcal{C}}$.

###### Proof of Claim 4.8.

(i) Since $|\tilde{C}|\geq 1$, one has
$col(P^{1}-A)\subseteq\mathcal{C}_{1}\cup\mathcal{C}_{bad}^{\prime}$. Suppose
that there exists an $i_{0}\in\mathcal{C}\backslash\tilde{\mathcal{C}}$ such
that $E(G_{i_{0}}[A])\neq\emptyset$. Choose $w_{1}w_{2}\in E(G_{i_{0}}[A])$.
Clearly, $w_{1},w_{2}\not\in V(P^{1})\cap B$. Recall that $w\not\in V(P^{4})$
unless $w\in(V(P^{1})\cap B)\cup V_{bad}$ and $i_{0}\not\in col(P^{4})$ unless
$i_{0}\in col(P^{1}-A)\cup col(M)$. If $i_{0}\in col(P^{1}-A)\cup col(M)$,
then let $\tilde{P}^{4}$ be a rainbow path obtained by deleting the edge with
color $i_{0}$ from $P^{4}$ and connecting its two endpoints by Claim 4.5 (i)
(if $i_{0}\in col(M)$) or Claim 4.5 (ii) (if $i_{0}\in col(P^{1}-A)$). It is
routine to check that
$|(\mathcal{C}_{1}\cup\mathcal{C}_{bad}^{\prime})\backslash
col(\tilde{P}^{4})|-(|B\backslash V(\tilde{P}^{4})|-|A\backslash
V(\tilde{P}^{4})|)$ is a positive odd integer. Let $P^{4}:=\tilde{P}^{4}$ if
$i_{0}\in col(P^{1}-A)\cup col(M)$. Therefore, it suffices to consider
$i_{0}\not\in col(P^{4})$.

$\bullet$ $w_{1},w_{2}\not\in V_{bad}$. Then $w_{1},w_{2}\not\in V(P^{4})$.
Connect $w_{2}$ with the endpoint $u_{1}$ of $P^{4}$ by Claim 4.5 (ii). Denote
by $Q_{0}$ the resulted rainbow path (see Figure 6).

$\bullet$ Exactly one of $w_{1},w_{2}$ lies in $V_{bad}$. Assume, without loss
of generality, that $w_{1}\not\in V_{bad}$ and $w_{2}\in V_{bad}$. Hence
$w_{1}\not\in V(P^{4})$ and $w_{2}\in V_{bad}\cap A$. Thus, there exists a
rainbow subpath $u_{1}P^{4}w_{2}^{1}w_{2}^{2}w_{2}$ of $P^{4}$ with
$w_{2}^{1}\in A\backslash V_{bad}$, $w_{2}^{2}\in B\backslash V_{bad}$.
Replace $w_{2}^{1}w_{2}^{2}w_{2}$ with $w_{1}w_{2}$ in $P^{4}$, and connect
$w_{1}$ with the vertex in $N_{P^{4}}(w_{2}^{1})\backslash\\{w_{2}^{2}\\}$ (if
exists) by Claim 4.5 (i). Let $Q_{1}$ be the resulted rainbow path (see Figure
6).

$\bullet$ $w_{1},w_{2}\in V_{bad}$. By rearranging, one may assume $w_{1}$ and
$w_{2}$ is connected by a rainbow path $w_{1}w_{1}^{1}w_{2}^{1}w_{2}^{2}w_{2}$
in $P^{4}$, where $w_{1}^{1},w_{2}^{2}\in B\backslash V_{bad}$ and
$w_{2}^{1}\in A\backslash V_{bad}$. Replace
$w_{1}w_{1}^{1}w_{2}^{1}w_{2}^{2}w_{2}$ with $w_{1}w_{2}$ in $P^{4}$. Denote
by $Q_{2}$ the resulted rainbow path (see Figure 6).

Figure 6.

In each of the above cases, we get a rainbow path $Q_{i}$ ($i\in\\{0,1,2\\}$)
such that $|\tilde{\mathcal{C}}|-||B\backslash V(Q_{i})|-|A\backslash
V(Q_{i})||$ is a nonnegative even integer. It follows from Claim 4.7 that
$\mathcal{G}$ contains a transversal Hamilton cycle, a contradiction.

(ii) Suppose that $E(G_{i_{1}}[A,B])\neq\emptyset$ for some
$i_{1}\in\tilde{\mathcal{C}}$. Choose $z_{1}z_{2}\in E(G_{i_{1}}[A,B])$ with
$z_{1}\in A$ and $z_{2}\in B$. Notice that
$col(P^{1}-A)\subseteq\mathcal{C}_{1}\cup\mathcal{C}_{bad}^{\prime}$. If
$z_{i}\in V_{bad}\cap Y$ for $i\in[2]$, then $P^{4}$ can be written as
$u_{1}P^{4}z_{i}^{0}z_{i}^{1}z_{i}z_{i}^{2}P^{4}v_{4}$, where $z_{i}^{0}\in
Y\backslash V_{bad}$ and $z_{i}^{1},z_{i}^{2}\in Z\backslash V_{bad}$; if
$z_{2}\in V(P^{1})\cap B$, then $P^{4}$ can be written as
$u_{1}P^{4}z_{2}z_{2}^{\prime}P^{4}v_{4}$, where $z_{2}z_{2}^{\prime}\in
E(P^{1})\cap E(G_{i_{2}})$ for some $i_{2}\in\mathcal{C}$. Clearly,
$i_{2}\in\mathcal{C}_{2}$ if $z_{2}^{\prime}\in A$ and
$i_{2}\in(\mathcal{C}_{1}\cup\mathcal{C}_{bad}^{\prime})\backslash\tilde{\mathcal{C}}$
if $z_{2}^{\prime}\in B$. Notice that $V(P^{1})\cap B\cap V_{bad}=\emptyset$.
Hence $z_{2}^{\prime}\not\in V_{bad}$.

$\bullet$ $z_{1},z_{2}\not\in(V(P^{1})\cap B)\cup V_{bad}$. Then
$z_{1},z_{2}\not\in V(P^{4})$. Connect $z_{2}$ with the endpoint $u_{1}$ of
$P^{4}$ by Claim 4.5 (i). Let $Q_{3}$ be the resulted rainbow path and
$\tilde{\mathcal{C}}_{3}=\tilde{\mathcal{C}}\backslash\\{i_{1}\\}$.

$\bullet$ Exactly one of $z_{1},\,z_{2}$ lies in $(V(P^{1})\cap B)\cup
V_{bad}$. Without loss of generality, assume that $z_{1}\not\in(V(P^{1})\cap
B)\cup V_{bad}$ and $z_{2}\in(V(P^{1})\cap B)\cup V_{bad}$ (the another case
is more easier since $z_{1}\not\in V(P^{1})\cap B$). Hence $z_{1}\not\in
V(P^{4})$. If $z_{2}\in V(P^{1})\cap B$, then connect $u_{1}P^{1}z_{2}z_{1}$
with $z_{2}^{\prime}P^{4}v_{4}$ into a single rainbow path by Claim 4.5
(i)-(ii). Let $Q_{4}$ be the resulted rainbow path, let
$\tilde{\mathcal{C}}_{4}=\tilde{\mathcal{C}}\backslash\\{i_{1}\\}$ if
$z_{2}^{\prime}\in A$ and
$\tilde{\mathcal{C}}_{4}=(\tilde{\mathcal{C}}\backslash\\{i_{1}\\})\cup\\{i_{2}\\}$
if $z_{2}^{\prime}\in B$. If $z_{2}\in V_{bad}$, then connect
$u_{1}P^{4}z_{2}^{1}$ with $z_{1}z_{2}z_{2}^{2}P^{4}v_{4}$ into a single
rainbow path by Claim 4.5 (ii). Let $Q_{5}$ be the resulted rainbow path and
$\tilde{\mathcal{C}}_{5}=\tilde{\mathcal{C}}\backslash\\{i_{1}\\}$.

$\bullet$ $z_{1},z_{2}\in(V(P^{1})\cap B)\cup V_{bad}$. Then $z_{1}\in
V_{bad}$. If $z_{2}\in V_{bad}$, by rearranging, one may assume $z_{1}$ and
$z_{2}$ is connected by a rainbow path
$z_{1}z_{1}^{2}z_{1}^{3}z_{2}^{3}z_{2}^{1}z_{2}$ in $P^{4}$, where
$z_{1}^{2},z_{2}^{3}\in B\backslash V_{bad}$ and $z_{1}^{3},z_{2}^{1}\in
A\backslash V_{bad}$. Replace such a rainbow path with $z_{1}z_{2}$ in
$P^{4}$. Let $Q_{6}$ be the resulted rainbow path and
$\tilde{\mathcal{C}}_{6}=\tilde{\mathcal{C}}\backslash\\{i_{1}\\}$. If
$z_{2}\in V(P^{1})\cap B$, then delete vertices
$z_{1}^{0},z_{1}^{1},z_{1},z_{1}^{2}$ from $P^{4}$ and connect the resulted
two components by Claim 4.5 (i). Denote the resulted rainbow path by
$\tilde{P}^{4}$. Then delete the edge $z_{2}z_{2}^{\prime}$ from
$\tilde{P}^{4}$. Applying Claim 4.5 (i)-(ii) again to connect
$u_{1}\tilde{P}^{4}z_{2}z_{1}z_{1}^{1}$ with
$z_{2}^{\prime}\tilde{P}^{4}v_{4}$ into a single rainbow path $Q_{7}$. Let
$\tilde{\mathcal{C}}_{7}=\tilde{\mathcal{C}}\backslash\\{i_{1}\\}$ if
$z_{2}^{\prime}\in A$ and
$\tilde{\mathcal{C}}_{7}=(\tilde{\mathcal{C}}\backslash\\{i_{1}\\})\cup\\{i_{2}\\}$
if $z_{2}^{\prime}\in B$.

In each of the above cases, we get a rainbow path $Q_{i}$ ($i\in[3,7]$) such
that $|\tilde{\mathcal{C}_{i}}|-||B\backslash V(Q_{i})|-|A\backslash
V(Q_{i})||$ is a nonnegative even integer. Applying Claim 4.7 yields that
$\mathcal{G}$ contains a transversal Hamilton cycle, a contradiction. Hence
$E(G_{i}[A,B])=\emptyset$ for all $i\in\tilde{\mathcal{C}}$. ∎

If $|\tilde{\mathcal{C}}|=0$, then $n$ is odd. By a similar discussion as the
proof of Claim 4.8, we can show that $E(G_{i}[B])=E(G_{i}[V(P^{1})\cap B])$
for all $i\in\mathcal{C}$. Then $|A|\geq\frac{n-1}{2}$. Recall that
$|B|\geq|A|$. Hence $|A|=\frac{n-1}{2}$ and $|B|=\frac{n+1}{2}$. This implies
that $P^{1}$ is a null graph. Thus, $G_{i}[B]=\emptyset$ for all
$i\in\mathcal{C}$. Therefore, $\mathcal{G}$ is the half-split graph collection
and it does not contain transversal Hamilton cycles, as desired.

If $|\tilde{\mathcal{C}}|\geq 1$, then based on Claim 4.8 and the fact that
$\delta(\mathcal{G})\geq\frac{n}{2}-1$, we know $n$ is even, $|A|=\frac{n}{2}$
and $|B|=\frac{n}{2}$, and $G_{i}[A]=\emptyset$ for all but at most $\eta
n+3\delta n$ colors in ${\mathcal{C}}$. By Theorem 4.3, we know $\mathcal{G}$
must be one of the collections described in Theorem 1.6, as desired.

Case 2. $|\mathcal{C}_{2}|<\eta n$.

In this case, each vertex in $Y\backslash(X\cup X_{Y}^{1})$ belongs to $Y_{i}$
for at least $(1-10\sqrt{\delta})|\mathcal{C}_{1}|$ colors
$i\in\mathcal{C}_{1}$. By a similar discussion as Claim 4.6, we get the
following claim.

######  Claim 4.9.

Assume $X=\\{x_{1},\ldots,x_{s}\\}$ with $s\leq\sqrt{\epsilon}n$. If $x_{i}\in
X\cap Y$, then there exist
$c_{i}^{1},c_{i}^{2},c_{i}^{3},c_{i}^{4}\in\mathcal{C}_{1}\backslash\\{c_{\ell}^{1},c_{\ell}^{2},c_{\ell}^{3},c_{\ell}^{4}:{\ell}\in[i-1]\\}$
and $x_{i}^{1},\,x_{i}^{2},\,x_{i}^{3},\,x_{i}^{4}\in
Y\backslash(V_{bad}\cup\\{x_{\ell}^{1},\,x_{\ell}^{2},\,x_{\ell}^{3},\,x_{\ell}^{4}:{\ell}\in[i-1]\\})$
such that $x_{i}x_{i}^{k}\in E(G_{c_{i}^{k}})$ for all $k\in[4]$.

By Claim 4.9 and a similar discussion as Steps 1-3 in Case 1, the following
hold:

  1. (C1)

In $\\{G_{i}[A]\cup G_{i}[B]:i\in\mathcal{C}_{1}\\}$, there are $|V_{bad}|$
disjoint rainbow $P_{3}$ with centers in $V_{bad}$ and endpoints in $(A\cup
B)\backslash V_{bad}$. Let $\mathbf{P}$ be a set consisting of those rainbow
$P_{3}$.

  2. (C2)

For colors in $\mathcal{C}_{bad}$, there exists a maximal rainbow matching,
say $M$, inside $\\{G_{i}[A\backslash V(\mathbf{P})]\cup G_{i}[B\backslash
V(\mathbf{P})]:i\in\mathcal{C}_{bad}\\}$ such that for each edge in $M[Y]$
with color $j$ we have $G_{j}[Y\backslash V(\mathbf{P}\cup{M})]$ contains a
$2$-matching. Denote $\mathcal{C}_{bad}^{\prime}:=\mathcal{C}_{bad}\backslash
col(M)$. Then $G_{j}$ is
$(3\sqrt{\delta},K_{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil})$-extremal
for all $j\in\mathcal{C}_{bad}^{\prime}$.

  3. (C3)

Let $q=|\mathcal{C}_{2}\cup\mathcal{C}_{bad}^{\prime}|$. In the graph
collection $\\{G_{i}[A\backslash V(\mathbf{P}\cup M),B\backslash
V(\mathbf{P}\cup M)]:i\in\mathcal{C}_{2}\cup\mathcal{C}_{bad}^{\prime}\\}$,
there exists a transversal matching
$M^{\prime}=\\{u_{1}v_{1},u_{2}v_{2},\ldots,u_{q}v_{q}\\}$.

  4. (C4)

We can assume a vertex $v\notin V(\mathbf{P}\cup M\cup M^{\prime})$ unless
$v\in V_{bad}$; and a color $c\notin col(\mathbf{P})$ if
$c\in\mathcal{C}_{1}$.

Next, we give the following claim.

######  Claim 4.10.

Assume that $Q_{1}=z_{1}\ldots z_{s}$ and $Q_{2}=z_{1}^{\prime}\ldots
z_{t}^{\prime}$ are two disjoint rainbow paths inside $\mathcal{G}$ such that
$z_{1},z_{1}^{\prime}\in A\backslash V_{bad}$, $z_{s},z_{t}^{\prime}\in
B\backslash V_{bad}$ and $s+t<4\eta n$. If $V_{bad}\subseteq V(Q_{1}\cup
Q_{2})$ and $\mathcal{C}_{2}\cup\mathcal{C}_{bad}\subseteq col(Q_{1}\cup
Q_{2})$, then $\mathcal{G}$ contains a transversal Hamilton cycle.

###### Proof of Claim 4.10.

Note that $z_{1},z_{1}^{\prime}\in A\backslash V_{bad}$ and
$z_{s},z_{t}^{\prime}\in B\backslash V_{bad}$. There exist
$i_{1},i_{2},i_{3},i_{4}\in\mathcal{C}_{1}\backslash col(Q_{1}\cup Q_{2})$
such that $z_{1}\in A_{i_{1}}$, $z_{1}^{\prime}\in A_{i_{2}}$, $z_{s}\in
B_{i_{3}}$ and $z_{t}^{\prime}\in B_{i_{4}}$. Split
$\mathcal{C}_{1}\backslash(col(Q_{1}\cup
Q_{2})\cup\\{i_{1},i_{2},i_{3},i_{4}\\})$ into two parts
$\mathcal{C}_{a}\cup\mathcal{C}_{b}$, where $|\mathcal{C}_{a}|=|A\backslash
V(Q_{1}\cup Q_{2})|-1$ and $|\mathcal{C}_{b}|=|B\backslash V(Q_{1}\cup
Q_{2})|-1$. Let $I_{1}\cup I_{2}$ and $J_{1}\cup J_{2}$ be equitable
partitions of $A\backslash V(Q_{1}\cup Q_{2})$ and $B\backslash V(Q_{1}\cup
Q_{2})$ with $|I_{1}|\geq|I_{2}|$ and $|J_{1}|\geq|J_{2}|$, respectively.
Define

$\mathcal{G}_{a}=\\{G_{i}[I_{1},I_{2}]:i\in\mathcal{C}_{a}\\}\ \text{and}\
\mathcal{G}_{b}=\\{G_{i}[J_{1},J_{2}]:i\in\mathcal{C}_{b}\\}.$

Notice that

$|Y\backslash V(Q_{1}\cup Q_{2})|\geq\frac{n-r}{2}-|V(Q_{1}\cup
Q_{2})|>\frac{n}{2}-5\eta n,$

and for $j\in[2]$ we have

$\displaystyle|N_{G_{i_{1}}}(z_{1},I_{j})|$ $\displaystyle\geq
d_{G_{i_{1}}}(z_{1},A\backslash V(Q_{1}\cup Q_{2}))-|I_{3-j}|$
$\displaystyle\geq d_{G_{i_{1}}}(z_{1},A_{i_{1}})-|A_{1}\Delta
A_{i_{1}}|-|X_{A}\backslash X_{A}^{1}|-|V(Q_{1}\cup Q_{2})|-|I_{3-j}|$
$\displaystyle\geq(\frac{1}{2}-3\sqrt{\delta})n-(2\delta+4\delta+8\eta)n-\lceil\frac{n+r}{4}\rceil>\frac{n}{4}-5\eta
n.$

Similarly, we have
$|N_{G_{i_{2}}}(z_{1}^{\prime},I_{j})|,|N_{G_{i_{3}}}(z_{s},J_{j})|,|N_{G_{i_{4}}}(z_{t}^{\prime},J_{j})|>\frac{n}{4}-5\eta
n$ for each $j\in[2]$. By Claim 4.4, there exists a transversal path $Q_{a}$
inside $\mathcal{G}_{a}$ with two endpoints $x_{a}\in
N_{G_{i_{1}}}(z_{1},I_{1})$ and $y_{a}\in N_{G_{i_{2}}}(z_{1}^{\prime},I)$;
and a transversal path $Q_{b}$ inside $\mathcal{G}_{b}$ with two endpoints
$x_{b}\in N_{G_{i_{3}}}(z_{s},J_{1})$ and $y_{b}\in
N_{G_{i_{4}}}(z_{t}^{\prime},J)$ (here $y_{a}\in I_{2}$ (resp. $y_{b}\in
J_{2}$) if and only if $|I_{1}|=|I_{2}|$ (resp. $|J_{1}|=|J_{2}|$) is even).
Thus,
$z_{1}Q_{1}z_{s}x_{b}Q_{b}y_{b}z_{t}^{\prime}Q_{2}z_{1}^{\prime}y_{a}Q_{a}x_{a}z_{1}$
is a transversal Hamilton cycle inside $\mathcal{G}$ (see Figure 8). ∎

Figure 7.

Figure 8.

Now, we proceed by considering the value of $q$.

Subcase 2.1. $q$ is even and $q\geq 2$.

Using Claim 4.5 (iii) to connect all rainbow paths in $\mathbf{P},M$ and
$M^{\prime}-u_{q}v_{q}$ into a single rainbow path $P$, whose length is at
most $(4\sqrt{\epsilon}+2\sqrt{\delta}+9\delta+3\eta)n$ and endpoints are
$x\in A\backslash V_{bad}$, $y\in B\backslash V_{bad}$ (see Figure 8). Thus,
$P$ and $u_{q}v_{q}$ are two disjoint rainbow paths satisfying all conditions
in Claim 4.10. Thus, $\mathcal{G}$ contains a transversal Hamilton cycle, a
contradiction.

Subcase 2.2. $q$ is odd.

Suppose that $E(G_{i_{1}}[A,B])\neq\emptyset$ for some
$i_{1}\in\mathcal{C}_{1}\cup col(M)$. Choose $w_{1}w_{2}\in E(G_{i_{1}}[A,B])$
with $w_{1}\in A$ and $w_{2}\in B$. Based on (C1), the edge $w_{1}w_{2}$ can
be extended to a rainbow path of length at most $3$, say $Q_{1}$, which has
endpoints in $A\backslash V_{bad}$ and $B\backslash V_{bad}$ respectively.
Next, by using Claim 4.5 (iii) and avoiding vertices and colors in $Q_{1}$,
one may connect all rainbow $P_{3}$ in $\mathbf{P}$ with centers not in
$\\{w_{1},w_{2}\\}$, all rainbow edges in $M$ except the possible edge with
color $i_{1}$ and all rainbow edges in $M^{\prime}$ into a single rainbow path
$P^{1}$, whose length is at most
$(4\sqrt{\epsilon}+2\sqrt{\delta}+9\delta+3\eta)n$ and endpoints are $x_{1}\in
A\backslash V_{bad}$, $y_{1}\in B\backslash V_{bad}$. Then $P^{1}$ and $Q_{1}$
satisfy all conditions in Claim 4.10. Therefore, $\mathcal{G}$ contains a
transversal Hamilton cycle, a contradiction. Hence $E(G_{i}[A,B])=\emptyset$
for all $i\in\mathcal{C}_{1}\cup col(M)$. Recall that
$\delta(\mathcal{G})\geq\frac{n}{2}-1$. Then $n$ is even and
$G_{i}[A]=G_{i}[B]=K_{\frac{n}{2}}$ for all $i\in\mathcal{C}_{1}\cup col(M)$.

If $q=1$, then it is easy to see that $\mathcal{G}$ contains no transversal
Hamilton cycle, as desired. Next, we consider $q\geq 3$. Suppose that there
exists an $i_{2}\in\mathcal{C}_{2}\cup\mathcal{C}_{bad}^{\prime}$ such that
$E(G_{i_{2}}[A])\cup E(G_{i_{2}}[B])\neq\emptyset$. Without loss of
generality, assume that $z_{1}z_{2}\in E(G_{i_{2}}[A])$ and $u_{1}v_{1}$ is
the edge in $M^{\prime}$ with color $i_{2}$. Based on (C1), we can extend
$z_{1}z_{2}$ to a rainbow path $Q_{2}$ with two endpoints in $A\backslash
V_{bad}$ and length at most $3$. Using Claim 4.5 (iii) to connect $Q_{2}$, all
rainbow $P_{3}$ in $\mathbf{P}$ with centers not in $\\{z_{1},z_{2}\\}$, all
rainbow edges in $M$ and all rainbow edges in
$M^{\prime}-\\{u_{1}v_{1},u_{q}v_{q}\\}$ into a single rainbow path $P^{2}$,
whose length is at most $(4\sqrt{\epsilon}+2\sqrt{\delta}+9\delta+3\eta)n+6$
and endpoints are $x_{2}\in A\backslash V_{bad}$, $y_{2}\in B\backslash
V_{bad}$. Clearly, ${P}^{2}$ and $u_{q}v_{q}$ are two rainbow paths satisfying
all conditions in Claim 4.10. Therefore, $\mathcal{G}$ contains a transversal
Hamilton cycle, a contradiction. Thus, for each
$i\in\mathcal{C}_{2}\cup\mathcal{C}_{bad}^{\prime}$, $E(G_{i}[A])\cup
E(G_{i}[B])=\emptyset$ and so $G_{i}$ is a subgraph of
$K_{\frac{n}{2},\frac{n}{2}}$. It follows that $\mathcal{G}$ is a spanning
collection of $\mathcal{H}_{n-q}^{q}$ with odd $q$.

We claim that $\mathcal{H}_{n-q}^{q}$ contains no transversal Hamilton cycles
if $n$ is even and $q$ is odd. Suppose not, let $C$ be a transversal Hamilton
cycle and give it an arbitrary direction to make it a directed cycle. We say
an edge of $C$ is $1$-type if it comes from some $G_{i}$ with
$i\in\mathcal{C}_{1}\cup col(M)$ and $2$-type if it comes from some $G_{i}$
with $i\in\mathcal{C}_{2}\cup\mathcal{C}_{bad}^{\prime}$. Note that the number
of $2$-type edges directed from $A$ to $B$ is equal to the number of $2$-type
edges directed from $B$ to $A$. Hence, the total number of $2$-type edges in
$C$ is even, which implies that $q$ is even, a contradiction.

Subcase 2.3. $q=0$.

Suppose that $\\{G_{i}[A,B]:i\in\mathcal{C}\\}$ contains a rainbow
$2$-matching. Let $\\{w_{1}w_{2},z_{1}z_{2}\\}$ be such a rainbow $2$-matching
with colors $c_{1},c_{2}$. Based on (C1), we can extend $w_{1}w_{2}$ and
$z_{1}z_{2}$ to two disjoint rainbow paths $Q_{3}$ and $Q_{4}$ with length at
most $3$, each of which has one endpoint in $A\backslash V_{bad}$ and the
other in $B\backslash V_{bad}$. By applying Claim 4.5 (iii) and avoiding
vertices and colors in $Q_{4}$, one may connect $Q_{3}$, all rainbow $P_{3}$
in $\mathbf{P}$ with centers outside $\\{w_{1},w_{2},z_{1},z_{2}\\}$ and all
rainbow edges in $M$ with colors outside $\\{c_{1},c_{2}\\}$ into a single
rainbow path $P^{3}$, whose length is at most
$(4\sqrt{\epsilon}+2\sqrt{\delta}+9\delta+3\eta)n+6$ and endpoints are
$x_{3}\in A\backslash V_{bad}$, $y_{3}\in B\backslash V_{bad}$. Clearly,
$P^{3}$ and $Q_{4}$ are two rainbow paths satisfying all conditions in Claim
4.10. Therefore, $\mathcal{G}$ contains a transversal Hamilton cycle, a
contradiction. Hence $\\{G_{i}[A,B]:i\in\mathcal{C}\\}$ contains no rainbow
$2$-matching. Finally, we finish the proof of this case by proving the
following claim.

######  Claim 4.11.

If $\mathcal{G}[A,B]$ has no rainbow $2$-matching, then $\mathcal{G}$ does not
contain transversal Hamilton cycles. Furthermore, $\mathcal{G}$ must be a
graph collection described in Theorem 1.6 (i)(b) or Theorem 1.6 (ii) (c).

###### Proof of Claim 4.11.

Notice that each transversal Hamilton cycle contains at least $2$ disjoint
rainbow edges in $\mathcal{G}[A,B]$. Hence $\mathcal{G}$ contains no
transversal Hamilton cycles. Next, we characterize the structure of
$\mathcal{G}$.

Assume that each vertex of $A$ has at least one neighbor in $B$ for all
$G_{i}\in\mathcal{G}$. Since $\mathcal{G}[A,B]$ contains no rainbow
$2$-matching, there exists a fixed vertex $w\in B$ such that
$N_{G_{i}}(v,B)=\\{w\\}$ for all $i\in\mathcal{C}$ and all $v\in A$.
Therefore, $|A|\geq\lceil\frac{n}{2}-1\rceil$. If $n$ is odd, then
$d_{G_{i}}(w)=n-1$ and $G_{i}[V\backslash\\{w\\}]=G_{i}[A]\cup
G_{i}[B\backslash\\{w\\}]=2K_{\frac{n-1}{2}}$ for all $i\in\mathcal{C}$, as
desired. If $n$ is even, then there exists an equitable partition
$A^{\prime}\cup B^{\prime}$ of $V$ and a vertex $w^{\prime}\in A^{\prime}$
such that $G_{i}[A^{\prime}]=K_{\frac{n}{2}}$ and
$E(G_{i}[A^{\prime},B^{\prime}])=E(G_{i}[\\{w^{\prime}\\},B^{\prime}])$ for
all $i\in\mathcal{C}$, as desired.

In what follows, it suffices to consider that there is a vertex $v\in A$ and a
color $i\in\mathcal{C}$ such that $N_{G_{i}}(v,B)=\emptyset$. Hence
$|B|\geq|A|\geq\lceil\frac{n}{2}-1\rceil+1$. Therefore, $n$ is even and
$|A|=|B|=\frac{n}{2}$.

$\bullet$ There exists a color $j_{1}\in\mathcal{C}$ and a vertex $v_{1}\in A$
such that $|N_{G_{j_{1}}}(v_{1})\cap B|\geq 2$. Since $\mathcal{G}$ contains
no rainbow $2$-matching, we know $G_{i}[A\backslash\\{v_{1}\\},B]=\emptyset$
for all $i\in\mathcal{C}\backslash\\{j_{1}\\}$. This implies that
$E(G_{i}[A,B])=E(G_{i}[\\{v_{1}\\},B])$ for all
$i\in\mathcal{C}\backslash\\{j_{1}\\}$. If $G_{i}[\\{v_{1}\\},B]=\emptyset$
for all $i\in\mathcal{C}\backslash\\{j_{1}\\}$, then
$G_{i}[A]=G_{i}[B]=K_{\frac{n}{2}}$ for all
$i\in\mathcal{C}\backslash\\{j_{1}\\}$, as desired. If there exists some
$j_{2}\in\mathcal{C}\backslash\\{j_{1}\\}$ such that
$G_{j_{2}}[\\{v_{1}\\},B]\neq\emptyset$, then let $v_{1}w\in
E(G_{j_{2}}[\\{v_{1}\\},B])$. Therefore, $N_{G_{j_{1}}}(v,B)\subseteq\\{w\\}$
for each $v\in A\backslash\\{v_{1}\\}$.

If $N_{G_{j_{1}}}(v,B)=\emptyset$ for all $v\in A\backslash\\{v_{1}\\}$, then
$E(G_{i}[A,B])=E(G_{i}[\\{v_{1}\\},B])$ and $E(G_{i}[A])=K_{\frac{n}{2}}$ for
all $i\in\mathcal{C}$, as desired. If there exists $v_{2}\in
A\backslash\\{v_{1}\\}$ such that $N_{G_{j_{1}}}(v_{2},B)=\\{w\\}$, then
$E(G_{i}[\\{v_{1}\\},B])\subseteq\\{v_{1}w\\}$ for all
$i\in\mathcal{C}\backslash\\{j_{1}\\}$. That is,
$E(G_{j_{1}}[A,B])\subseteq\\{v_{1}v:v\in B\\}\cup\\{vw:v\in A\\}$,
$E(G_{i}[A,B])\subseteq\\{v_{1}w\\}$ and $G_{i}[A]=G_{i}[B]=K_{\frac{n}{2}}$
for all $i\in\mathcal{C}\backslash\\{j_{1}\\}$, as desired.

$\bullet$ $|N_{G_{i}}(v,B)|\leq 1$ for all $i\in\mathcal{C}$ and all $v\in A$.
By symmetry, one may assume that $|N_{G_{i}}(v,A)|\leq 1$ for all
$i\in\mathcal{C}$ and all $v\in B$. Let
$|E(G_{j_{3}}[A,B])|=\max\\{|E(G_{j}[A,B])|:j\in\mathcal{C}\\}$. If
$|E(G_{j_{3}}[A,B])|\geq 3$, then $G_{i}=G_{i}[A]\cup
G_{i}[B]=2K_{\frac{n}{2}}$ for all $i\in\mathcal{C}\backslash\\{j_{3}\\}$, as
desired.

If $|E(G_{j_{3}}[A,B])|=2$, then assume
$E(G_{j_{3}}[A,B])=\\{v_{1}w_{1},v_{2}w_{2}\\}$, where
$v_{1},w_{1},v_{2},w_{2}$ are pairwise distinct. This implies
$G_{j_{3}}[A]\in\\{K_{\frac{n}{2}}-v_{1}v_{2},K_{\frac{n}{2}}\\}$ and
$G_{j_{3}}[B]\in\\{K_{\frac{n}{2}}-w_{1}w_{2},K_{\frac{n}{2}}\\}$. Recall that
$\mathcal{G}$ contains no rainbow $2$-matching. Then either
$E(G_{j_{4}}[A,B])=\\{v_{1}w_{2},v_{2}w_{1}\\}$ for a unique
$j_{4}\in\mathcal{C}\backslash\\{j_{3}\\}$ and $G_{i}[A,B]=\emptyset$ for all
$i\in\mathcal{C}\backslash\\{j_{3},j_{4}\\}$, or
$E(G_{i}[A,B])\subseteq\\{v_{1}w_{2}\\}$ for all
$i\in\mathcal{C}\backslash\\{j_{3}\\}$. The former case implies
$E(G_{j_{4}}[A,B])=\\{v_{1}w_{2},v_{2}w_{1}\\}$,
$G_{j_{4}}[A]\in\\{K_{\frac{n}{2}}-v_{1}v_{2},K_{\frac{n}{2}}\\}$,
$G_{j_{4}}[B]\in\\{K_{\frac{n}{2}}-w_{1}w_{2},K_{\frac{n}{2}}\\}$ and
$G_{i}=G_{i}[A]\cup G_{i}[B]=2K_{\frac{n}{2}}$ for all
$i\in\mathcal{C}\backslash\\{j_{3},j_{4}\\}$ (see Figure 1 (a)), as desired.
The latter case implies $E(G_{i}[A,B])\subseteq\\{v_{1}w_{2}\\}$ and
$G_{i}[A]=G_{i}[B]=K_{\frac{n}{2}}$ for all
$i\in\mathcal{C}\backslash\\{j_{3}\\}$ (see Figure 1 (b)), as desired.

If $|E(G_{j_{3}}[A,B])|\leqslant 1$, then $G_{i}[A]=G_{i}[B]=K_{\frac{n}{2}}$
for all $i\in\mathcal{C}$ and all edges in $\\{G_{i}[A,B]:i\in\mathcal{C}\\}$
must have a common vertex, as desired.

This completes the proof of Claim 4.11. ∎

Case 3. $|\mathcal{C}_{1}|\geq\eta n$ and $|\mathcal{C}_{2}|\geq\eta n$.

In this case, each vertex in $Y\backslash V_{bad}$ lies in $Y_{i}$ for at
least $(1-10\sqrt{\delta})|{\mathcal{C}_{1}}\cup\mathcal{C}_{2}|$ colors
$i\in\mathcal{C}_{1}\cup{\mathcal{C}_{2}}$. Denote
$\cup_{k\in[2]}(X_{A}^{k}\cup X_{B}^{k})=\\{v_{1},v_{2},\ldots,v_{t}\\}$.
Notice that $t<\frac{1}{2}\sqrt{\delta}n$. By the definition of $X_{Y}^{k}$,
we obtain that for each $i\in[t]$, there exist
$c_{4i-3},c_{4i-2},c_{4i-1},c_{4i}\in(\mathcal{C}_{1}\cup\mathcal{C}_{2})\backslash\\{c_{1},c_{2},\ldots,c_{4i-5},c_{4i-4}\\}$
and $v_{i}^{1},v_{i}^{2},v_{i}^{3},v_{i}^{4}\in(A\cup
B)\backslash(V_{bad}\cup\\{v_{\ell}^{1},v_{\ell}^{2},v_{\ell}^{3},v_{\ell}^{4}:\ell\in[i-1]\\})$
such that

  * •

if $v_{i}\in X_{Y}^{1}$, then $c_{4i-4+j}\in\mathcal{C}_{1}$, $v_{i}^{j}\in
Y\cap Y_{c_{4i-4+j}}$ and $v_{i}v_{i}^{j}\in E(G_{c_{4i-4+j}})$ for all
$j\in[4]$,

  * •

if $v_{i}\in X_{Y}^{2}$, then $c_{4i-4+j}\in\mathcal{C}_{2}$, $v_{i}^{j}\in
Z\cap Z_{c_{4i-4+j}}$ and $v_{i}v_{i}^{j}\in E(G_{c_{4i-4+j}})$ for all
$j\in[4]$.

Therefore, for each $i\in[t]$, there exists a rainbow path
$v_{i}^{1}v_{i}v_{i}^{2}$ with colors $c_{4i-3}$ and $c_{4i-2}$. Connect those
rainbow paths by using colors in $\mathcal{C}_{2}$ and Claim 4.5 (i)-(ii), one
may get a rainbow path $P^{1}$ with endpoints $u_{1}\in A\backslash V_{bad}$
and $w_{1}\in B\backslash V_{bad}$, whose length is at most $4t\leq
2\sqrt{\delta}n$.

By a similar discussion as Claim 4.6, we obtain the following claim.

######  Claim 4.12.

Assume $X=\\{x_{1},\ldots,x_{s}\\}$ with $s\leq\sqrt{\epsilon}n$. Then for
each $i\in[s]$, there exist
$c_{i}^{1},c_{i}^{2},c_{i}^{3},c_{i}^{4}\in\mathcal{C}_{2}\backslash(col(P^{1})\cup\\{c_{\ell}^{1},c_{\ell}^{2},c_{\ell}^{3},c_{\ell}^{4}:{\ell}\in[i-1]\\})$
and $x_{i}^{1},\,x_{i}^{2},\,x_{i}^{3},\,x_{i}^{4}\in V\backslash(V(P^{1})\cup
V_{bad}\cup\\{x_{\ell}^{1},\,x_{\ell}^{2},\,x_{\ell}^{3},\,x_{\ell}^{4}:{\ell}\in[i-1]\\})$
such that: if $x_{i}\in Y$, then $x_{i}x_{i}^{j}\in E(G_{c_{i}^{j}})$, and
either $x_{i}^{j}\in Y$ and $c_{i}^{j}\in\mathcal{C}_{1}$ for all $j\in[4]$,
or $x_{i}^{j}\in Z$ and $c_{i}^{j}\in\mathcal{C}_{2}$ for all $j\in[4]$.

By Claim 4.12, there exists a rainbow path $x_{i}^{1}x_{i}x_{i}^{2}$ with
colors $c_{i}^{1},c_{i}^{2}$ for each $i\in[s]$. Connect all those rainbow
paths and $P^{1}$ by Claim 4.5 (i)-(ii), we obtain a rainbow path $P^{2}$ with
endpoints $u_{1}\in A\backslash V_{bad}$ and $w_{2}\in B\backslash V_{bad}$,
whose length is at most
$|E(P^{1})|+4\sqrt{\epsilon}n+2\leq(2\sqrt{\delta}+4\sqrt{\epsilon})n+2$.

Choose a maximal rainbow matching, say $M$, inside $\\{G_{i}[A\backslash
V(P^{2})]\cup G_{i}[B\backslash V(P^{2})]:i\in\mathcal{C}_{bad}\\}$ such that
for each edge in $M[Y]$ with color $j$ we have $G_{j}[Y\backslash V(P^{2})]$
contains a $2$-matching. Denote
$\mathcal{C}_{bad}^{\prime}:=\mathcal{C}_{bad}\backslash col(M)$. Note that
$G_{j}$ is
$(3\sqrt{\delta},K_{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil})$-extremal
for all $j\in\mathcal{C}_{bad}^{\prime}$. Hence,
$\\{G_{i}[A,B]:i\in\mathcal{C}_{bad}^{\prime}\\}$ contains a transversal
matching, say $M^{\prime}$. Connect $P^{2}$ and all rainbow edges in $M\cup
M^{\prime}$ by Claim 4.5 (i)-(ii), we obtain a rainbow path $P^{3}$ with
endpoints $u_{1}\in A\backslash V_{bad}$ and $w_{3}\in B\backslash V_{bad}$,
whose length is at most $|E(P^{2})|+12\delta
n\leq(2\sqrt{\delta}+4\sqrt{\epsilon}+12\delta)n+2$.

Since $u_{1},w_{3}\not\in V_{bad}$, there exist
$i_{0},i_{1}\in\mathcal{C}_{1}\backslash col(P^{3})$ such that $u_{1}\in
A_{i_{0}}$ and $w_{3}\in B_{i_{1}}$. By the construction of $P^{3}$, one may
assume that $v\not\in V(P^{3})$ unless $v\in V_{bad}$, and $c\not\in
col(P^{3})$ unless $c\in\mathcal{C}_{bad}$. In what follows, we proceed by
considering the parity of $|\mathcal{C}_{2}\backslash col(P^{3})|$.

Subcase 3.1. $|\mathcal{C}_{2}\backslash col(P^{3})|$ is odd.

Split $A\backslash V(P^{3})$ into $I_{1}$ and $I_{2}$ such that
$|I_{1}|=\frac{|\mathcal{C}_{2}\backslash col(P^{3})|+1}{2}$, and split
$B\backslash V(P^{3})$ into $J_{1}$ and $J_{2}$ such that
$|J_{1}|=\frac{|\mathcal{C}_{2}\backslash col(P^{3})|+1}{2}$. Let
$\mathcal{G}_{1}=\\{G_{i}[I_{1},J_{1}]:i\in\mathcal{C}_{2}\backslash
col(P^{3})\\}$. By Claim 4.4, there exists a transversal path $Q$ inside
$\mathcal{G}_{1}$ with endpoints $x\in I_{1}$ and $y\in J_{1}$. Since
$x,y\not\in V_{bad}$, there exist $j_{0},j_{1}\in\mathcal{C}_{1}$ such that
$x\in A_{j_{0}}$ and $y\in B_{j_{1}}$.

Suppose that $|I_{2}|=|A\backslash V(P^{3})|-|I_{1}|=k_{1}$ and
$|J_{2}|=|B\backslash V(P^{3})|-|J_{1}|=k_{2}$. We further split $I_{2}$ into
$I_{2}^{\prime}$ and $I_{2}^{\prime\prime}$ such that
$|I_{2}^{\prime}|=\lceil\frac{k_{1}}{2}\rceil$, split $J_{2}$ into
$J_{2}^{\prime}$ and $J_{2}^{\prime\prime}$ such that
$|J_{2}^{\prime}|=\lceil\frac{k_{2}}{2}\rceil$. Then split the color set
$\mathcal{C}_{1}\backslash(col(P^{3})\cup\\{j_{0},j_{1}\\})$ into two subsets
$\mathcal{C}_{a}$ and $\mathcal{C}_{b}$ such that $|\mathcal{C}_{a}|=k_{1}-1$
and $|\mathcal{C}_{b}|=k_{2}-1$. Let
$\mathcal{G}_{a}=\\{G_{i}[I_{2}^{\prime},I_{2}^{\prime\prime}]:i\in\mathcal{C}_{a}\\}$
and
$\mathcal{G}_{b}=\\{G_{i}[J_{2}^{\prime},J_{2}^{\prime\prime}]:i\in\mathcal{C}_{b}\\}$.
Applying Claim 4.4 again yields that there is a transversal path $Q_{a}$
inside $\mathcal{G}_{a}$ with endpoints $x_{a}\in
N_{G_{i_{0}}}(u_{1},I_{2}^{\prime}),\,y_{a}\in N_{G_{j_{0}}}(x,I_{2})$; and a
transversal path $Q_{b}$ inside $\mathcal{G}_{b}$ with endpoints $x_{b}\in
N_{G_{i_{1}}}(w_{3},J_{2}^{\prime}),\,y_{b}\in N_{G_{j_{1}}}(y,J_{2})$. Thus,
$u_{1}P^{3}w_{3}x_{b}Q_{b}y_{b}yQxy_{a}Q_{a}x_{a}u_{1}$ is a transversal
Hamilton cycle in $\mathcal{G}$ (see Figure 9), a contradiction.

Figure 9.

Subcase 3.2. $|\mathcal{C}_{2}\backslash col(P^{3})|$ is even.

In this subcase, we first prove the following two claims.

######  Claim 4.13.

Assume that $Q_{1}=z_{1}\ldots z_{k}$ and $Q_{2}=z_{1}^{\prime}\ldots
z_{t}^{\prime}$ are two disjoint rainbow paths inside $\mathcal{G}$ such that
$z_{1},z_{1}^{\prime}\in A\backslash V_{bad}$, $z_{k},z_{t}^{\prime}\in
B\backslash V_{bad}$ and each of them has length at most $3\sqrt{\delta}n$. If
$V_{bad}\subseteq V(Q_{1}\cup Q_{2})$, $\mathcal{C}_{bad}\subseteq
col(Q_{1}\cup Q_{2})$ and $|\mathcal{C}_{2}\backslash col(Q_{1}\cup Q_{2})|$
is even, then $\mathcal{G}$ contains a transversal Hamilton cycle.

###### Proof of Claim 4.13.

Note that $z_{1},z_{1}^{\prime}\in A\backslash V_{bad}$ and
$z_{k},z_{t}^{\prime}\in B\backslash V_{bad}$. There exist
$l_{1},l_{2},l_{3}\in\mathcal{C}_{1}\backslash col(Q_{1}\cup Q_{2})$ and
$l_{4}\in\mathcal{C}_{2}\backslash col(Q_{1}\cup Q_{2})$ such that $z_{1}\in
A_{l_{1}}$, $z_{k}\in B_{l_{2}}$, $z_{1}^{\prime}\in A_{l_{4}}$ and
$z_{t}^{\prime}\in B_{l_{3}}$.

Split $A\backslash V(Q_{1}\cup Q_{2})$ into $I_{1}$ and $I_{2}$ such that
$|I_{1}|=\frac{|\mathcal{C}_{2}\backslash col(Q_{1}\cup Q_{2})|}{2}$, and
split $B\backslash V(Q_{1}\cup Q_{2})$ into $J_{1}$ and $J_{2}$ such that
$|J_{1}|=\frac{|\mathcal{C}_{2}\backslash col(Q_{1}\cup Q_{2})|}{2}$. Let
$\mathcal{G}_{1}=\\{G_{i}[I_{1},J_{1}]:i\in\mathcal{C}_{2}\backslash(col(Q_{1}\cup
Q_{2})\cup\\{l_{4}\\})\\}$. By Claim 4.4, there exists a transversal path $Q$
inside $\mathcal{G}_{1}$ with endpoints $z_{1}^{\prime\prime}\in
N_{G_{l_{4}}}(z_{1}^{\prime})\cap J_{1}$ and $y\in I_{1}$. Since $y\not\in
V_{bad}$, there exists $l_{5}\in\mathcal{C}_{1}\backslash(col(Q_{1}\cup
Q_{2})\cup\\{l_{1},l_{2},l_{3}\\})$ such that $y\in A_{l_{5}}$.

Assume that $|I_{2}|=k_{1}$ and $|J_{2}|=k_{2}$. We further split $I_{2}$ into
$I_{2}^{\prime}$ and $I_{2}^{\prime\prime}$ such that
$|I_{2}^{\prime}|=\lceil\frac{k_{1}}{2}\rceil$, and split $J_{2}$ into
$J_{2}^{\prime}$ and $J_{2}^{\prime\prime}$ such that
$|J_{2}^{\prime}|=\lceil\frac{k_{2}}{2}\rceil$. Split the color set
$\mathcal{C}_{1}\backslash(col(Q_{1}\cup
Q_{2})\cup\\{l_{1},l_{2},l_{3},l_{5}\\})$ into two subsets $\mathcal{C}_{a}$
and $\mathcal{C}_{b}$ such that $|\mathcal{C}_{a}|=k_{1}-1$ and
$|\mathcal{C}_{b}|=k_{2}-1$. Let
$\mathcal{G}_{a}=\\{G_{i}[I_{2}^{\prime},I_{2}^{\prime\prime}]:i\in\mathcal{C}_{a}\\}$
and
$\mathcal{G}_{b}=\\{G_{i}[J_{2}^{\prime},J_{2}^{\prime\prime}]:i\in\mathcal{C}_{b}\\}$.
By Claim 4.4, there exists a transversal path $Q_{a}$ inside $\mathcal{G}_{a}$
with endpoints $x_{a}\in N_{G_{l_{1}}}(z_{1})\cap I_{2}^{\prime},y_{a}\in
N_{G_{l_{5}}}(y)\cap I_{2}$, and a transversal path $Q_{b}$ inside
$\mathcal{G}_{b}$ with endpoints $x_{b}\in N_{G_{l_{2}}}(z_{k})\cap
J_{2}^{\prime},y_{b}\in N_{G_{l_{3}}}(z_{t}^{\prime})\cap J_{2}$. Hence,
$z_{1}Q_{1}z_{k}x_{b}Q_{b}y_{b}z_{t}^{\prime}Q_{2}z_{1}^{\prime}z_{1}^{\prime\prime}Qyy_{a}Q_{a}x_{a}z_{1}$
is a transversal Hamilton cycle in $\mathcal{G}$. ∎

######  Claim 4.14.

$E(G_{i}[A,B])=\emptyset$ for all $i\in\mathcal{C}_{1}\cup col(M)$.

###### Proof of Claim 4.14.

Suppose that there exists an edge $y_{1}y_{2}\in E(G_{i_{2}}[A,B])$ for some
$i_{2}\in\mathcal{C}_{1}\cup col(M)$, where $y_{1}\in A$ and $y_{2}\in B$. If
$i_{2}\in col(M)$, then assume $uv\in E(M[A])\cap E(G_{i_{2}})$. Connect
$P^{2}$, all rainbow edges in $M-uv$ and all rainbow edges in $M^{\prime}$ in
turn by Claim 4.5 (i)-(ii), we get a rainbow path $\tilde{P}^{3}$ with
endpoints $\tilde{u}_{1}\in A\backslash V_{bad}$ and $\tilde{w}_{3}\in
B\backslash V_{bad}$. Therefore, $P^{3}$ can be written as
$uvv^{\prime}\tilde{u}_{1}\tilde{P}^{3}\tilde{w}_{3}$, where the colors of
$vv^{\prime}$ and $v^{\prime}\tilde{u}_{1}$ are in $\mathcal{C}_{2}$. Since
$|\mathcal{C}_{2}\backslash col(P^{3})|$ is even, one has
$|\mathcal{C}_{2}\backslash col(\tilde{P}^{3})|$ is even. Let
$P^{3}:=\tilde{P}^{3}$ if $i_{2}\in col(M)$. Hence we can assume $i_{2}\not\in
col(P^{3})$. Recall that $y_{i}\not\in V(P^{3})$ unless it is not in $V_{bad}$
for each $i\in[2]$. Moreover, if $y_{i}\in V_{bad}$ for some $i\in[2]$, then
$P^{3}$ can be written as $u_{1}P^{3}y_{i}^{1}y_{i}y_{i}^{2}P^{3}w_{3}$.
Assume $y_{i}^{1}y_{i}$ and $y_{i}y_{i}^{2}$ have colors $j_{2i-1}$ and
$j_{2i}$ in $P^{3}$, respectively.

If $y_{1},y_{2}\not\in V_{bad}$, then $P^{3}$ and $y_{1}y_{2}$ are two
disjoint rainbow paths satisfying all conditions in Claim 4.13. Hence,
$\mathcal{G}$ contains a transversal Hamilton cycle, a contradiction.
Therefore, at least one of $y_{1}$ and $y_{2}$ lies in $V_{bad}$. Without loss
of generality, assume that $y_{2}\in V_{bad}$. Observe that either
$j_{3},j_{4}\in\mathcal{C}_{1}$ and $y_{2}^{1},\,y_{2}^{2}\in B$, or
$j_{3},j_{4}\in\mathcal{C}_{2}$ and $y_{2}^{1},\,y_{2}^{2}\in A$ holds.

Assume $y_{1}\not\in V_{bad}$. Delete $y_{2}^{1}y_{2}$ from $P^{3}$, we get
two rainbow paths $P^{\prime}=u_{1}P^{3}y_{2}^{1}$ and
$P^{\prime\prime}=y_{1}y_{2}y_{2}^{2}P^{3}w_{3}$. Recall that $u_{1},y_{1}\in
A\backslash V_{bad}$, $w_{3}\in B\backslash V_{bad}$ and $y_{2}^{1}\notin
V_{bad}$. It is routine to checck that $P^{\prime}$ can be extended to a
rainbow path with one endpoint $u_{1}$ and the other endpoint $\hat{y}\in
B\backslash V_{bad}$, where $\hat{y}=y_{2}^{1}$ if $y_{2}^{1}\in B$.
Therefore, there are two rainbow paths satisfying all conditions in Claim
4.13. Therefore, $\mathcal{G}$ contains a transversal Hamilton cycle, a
contradiction.

Finally, we consider $y_{1},y_{2}\in V_{bad}$. Then by rearranging, one may
assume that $y_{1}^{2}P^{3}y_{2}^{1}$ is a rainbow path with length at most
$3$. Replace $y_{1}P^{3}y_{2}$ by the edge $y_{1}y_{2}$ with color $i_{2}$. It
is routine to check that $|\mathcal{C}_{2}\backslash
col(u_{1}P^{3}y_{1}y_{2}P^{3}w_{3})|$ is odd (see Figure 10 for all possible
cases). Thus, this can be attributed to the Subcase 3.1. Hence $\mathcal{G}$
contains a transversal Hamilton cycle, a contradiction. ∎

Figure 10. All possible cases for $y_{1},y_{2}\in V_{bad}$. We use “1” (resp.
“2”) to denote that the color of this edge lies in $\mathcal{C}_{1}$ (resp.
$\mathcal{C}_{2}$).

By Claim 4.14, one has $E(G_{i}[A,B])=\emptyset$ for all
$i\in\mathcal{C}_{1}\cup col(M)$. Therefore, $n$ is even and
$G_{i}[A]=G_{i}[B]=K_{\frac{n}{2}}$ for all $i\in\mathcal{C}_{1}\cup col(M)$.
By a similar argument as Claim 4.14, we can show that $E(G_{i}[A]\cup
G_{i}[B])=\emptyset$ for all
$i\in\mathcal{C}_{2}\cup\mathcal{C}_{bad}^{\prime}$. It follows that
$\mathcal{G}$ is a spanning collection of $\mathcal{H}_{n-t}^{t}$, where
$t=|\mathcal{C}_{2}\cup\mathcal{C}_{bad}^{\prime}|$.

We claim that $t$ is odd. Otherwise, $t$ is even. Recall that
$G_{i}[A]=G_{i}[B]=K_{\frac{n}{2}}$ for all $i\in\mathcal{C}_{1}\cup col(M)$.
Then there exist two rainbow paths, say $Q_{1}:=z_{1}^{1}\ldots z_{s_{1}}^{1}$
and $Q_{2}:=z_{1}^{2}\ldots z_{s_{2}}^{2}$, such that $V(Q_{1}\cup
Q_{2})=V_{bad}$ and $col(Q_{1}\cup Q_{2})\subseteq\mathcal{C}_{1}\cup col(M)$.
For $i\in[2]$, it is easy to see that $Q_{i}$ can be extended to a rainbow
path $Q_{i}^{\prime}:=x^{i}z_{1}^{i}\ldots z_{s_{i}}^{i}y^{i}z^{i}$, where
$x^{i},y^{i}\in A\backslash V_{bad}$, $z_{i}\in B\backslash V_{bad}$, and the
colors of $x^{i}z_{1}^{i},\,z_{s_{i}}^{i}y^{i},\,y^{i}z^{i}$ are unused colors
in $\mathcal{C}_{1},\,\mathcal{C}_{1},\,\mathcal{C}_{2}$, respectively. Since
$t$ is even, one has
$|(\mathcal{C}_{2}\cup\mathcal{C}_{bad}^{\prime})\backslash
col(Q_{1}^{\prime}\cup Q_{2}^{\prime})|$ is even. By a similar argument as
Claim 4.13, we know $\mathcal{G}$ contains a transversal Hamilton cycle, a
contradiction. Therefore, $\mathcal{G}$ is a spanning collection of
$\mathcal{H}_{n-t}^{t}$, where $n$ is even and $t$ is odd.

This completes the proof of Theorem 1.6. ∎

##  5\. Proof of Theorem 4.3

In this section, we prove Theorem 4.3, which characterizes the structure of
almost balanced graph collections that do not contain transversal Hamilton
cycles. Based on the parity of $n$ and the size of the vertex partition, we
split the proof of Theorem 4.3 into four lemmas (see, Lemmas 5.1, 5.2, 5.6 and
5.8).

######  Lemma 5.1.

For every $\delta$ with $0<\delta\ll 1$, there exists $n_{0}\in\mathbb{N}$
satisfying the following for every odd integer $n\geq n_{0}$. Let
$\mathcal{C}$ be a set of $n$ colors and
$\mathcal{G}=\\{G_{i}:i\in\mathcal{C}\\}$ be a collection of graphs with
common vertex set $V$ of size $n$. Let $A\cup B$ be a partition of $V$ with
$|A|=\frac{n-1}{2}$, and let
$\mathcal{C}^{\prime}\cup\mathcal{C}^{\prime\prime}$ be a partition of
$\mathcal{C}$ with $|\mathcal{C}^{\prime\prime}|\leq\delta n$. Assume that
$\delta(\mathcal{G})\geq\frac{n-1}{2}$ and $G_{i}[B]=\emptyset$ for all
$i\in\mathcal{C}^{\prime}$. If $\mathcal{G}$ does not contain transversal
Hamilton cycles, then $\mathcal{G}$ is the half-split graph collection.

###### Proof.

In order to show that $\mathcal{G}$ is the half-split graph collection, it
suffices to prove $G_{i}[B]=\emptyset$ for all
$i\in\mathcal{C}^{\prime\prime}$. By adding colors to
$\mathcal{C}^{\prime\prime}$ if necessary we may assume
$|\mathcal{C}^{\prime\prime}|=\delta n>0$ and
$\mathcal{C}^{\prime\prime}=\\{i_{1},i_{2},\ldots,i_{\delta n}\\}$. Suppose
that $G_{i_{1}}[B]\neq\emptyset$ and let $uv\in E(G_{i_{1}}[B])$. Choose a
maximal rainbow matching inside
$\\{G_{i_{j}}[A,B\backslash\\{u,v\\}]:j\in[2,\delta n]\\}$, say
$M=\\{e_{i_{j}}:2\leq j\leq s\\}$ with $s\leq\delta n$ and $e_{i_{j}}\in
E(G_{i_{j}})$, such that $G_{i_{j}}[A\backslash
V(M),B\backslash(V(M)\cup\\{u,v\\})]\neq\emptyset$ for all $j\in[2,s]$. Notice
that $G_{i_{j}}$ is $(2\delta n,K_{\lfloor\frac{n}{2}\rfloor}\cup
K_{\lceil\frac{n}{2}\rceil})$-extremal for all $j\in[s+1,\delta n]$. We
greedily select two rainbow paths $P_{A}$ and $P_{B}$ inside
$\\{G_{i_{j}}[A\backslash V(M)]\cup
G_{i_{j}}[B\backslash(V(M)\cup\\{u,v\\})]:j\in[s+1,\delta n]\\}$ with lengths
$\lfloor\frac{\delta n-s}{2}\rfloor$ and $\lceil\frac{\delta n-s}{2}\rceil$
respectively, where $V(P_{A})\subseteq A$ and $V(P_{B})\subseteq B$.

We first consider $\delta n-s$ is even. It is easy to see that
$G_{i}[A,B]=K_{\frac{n-1}{2},\frac{n+1}{2}}$ for all
$i\in\mathcal{C}^{\prime}$. Using colors in $\mathcal{C}^{\prime}$ and edges
between $A$ and $B$, one may connect $uv$, all rainbow edges in $M$, $P_{A}$
and $P_{B}$ into a single rainbow path, say $P^{1}:=u\ldots v_{1}$, where
$v_{1}\in B$. Therefore, $|A\backslash V(P^{1})|=|B\backslash V(P^{1})|+1$.
Observe that $\\{G_{i}[A\backslash V(P^{1}),B\backslash
V(P^{1}-\\{u,v_{1}\\})]:i\in\mathcal{C}\backslash col(P^{1})\\}$ is a
collection of complete bipartite graphs, therefore it contains a transversal
path that connects $u$ and $v_{1}$. Hence $\mathcal{G}$ has a transversal
Hamilton cycle, a contradiction.

Now, assume that $\delta n-s$ is odd. Recall that $|A|=\frac{n-1}{2}$ and
$\delta(\mathcal{G})\geq\frac{n-1}{2}$. Hence there exists an edge
$w_{1}w_{2}\in E(G_{i_{1}}[A\backslash V(M\cup P_{A}\cup P_{B}),B])$ with
$w_{1}\in A$ and $w_{2}\in B$. Notice that one may avoid $w_{2}$ when choosing
$M$ and $P_{B}$. Using colors in $\mathcal{C}^{\prime}$ and edges between $A$
and $B$, we can connect $w_{1}w_{2}$, all rainbow edges in $M$, $P_{A}$ and
$P_{B}$ into a single rainbow path $P^{2}$, whose endpoints are in different
parts. Therefore, $|A\backslash V(P^{1})|=|B\backslash V(P^{1})|$. Similarly,
$\mathcal{G}$ has a transversal Hamilton cycle, a contradiction. ∎

######  Lemma 5.2.

For every $\delta$ with $0<\delta\ll 1$, there exists $n_{0}\in\mathbb{N}$
satisfying the following for every even integer $n\geq n_{0}$. Let
$\mathcal{C}$ be a set of $n$ colors, and
$\mathcal{G}=\\{G_{i}:i\in\mathcal{C}\\}$ be a collection of graphs with
common vertex set $V$ of size $n$. Let $A\cup B$ be a partition of $V$ with
$|A|=\frac{n}{2}-1$, and let
$\mathcal{C}^{\prime}\cup\mathcal{C}^{\prime\prime}$ be a partition of
$\mathcal{C}$ with $|\mathcal{C}^{\prime\prime}|\leq\delta n$. Assume that
$\delta(\mathcal{G})\geq\frac{n}{2}-1$ and $G_{i}[B]=\emptyset$ for all
$i\in\mathcal{C}^{\prime}$. If $\mathcal{G}$ does not contain transversal
Hamilton cycles, then either $G_{i}[B]=\emptyset$ for all but at most one
$i\in\mathcal{C}$, or $E(G_{i}[B])\subseteq\\{uv\\}$ for two fixed vertices
$u,v\in B$ and all $i\in\mathcal{C}$.

###### Proof.

In order to prove this lemma, it suffices to show that
$\\{G_{i}[B]:i\in\mathcal{C}^{\prime\prime}\\}$ contains no rainbow $P_{3}$ or
$2P_{2}$. By adding colors to $\mathcal{C}^{\prime\prime}$ if necessary we may
assume $|\mathcal{C}^{\prime\prime}|=\delta n>0$ and
$\mathcal{C}^{\prime\prime}=\\{i_{1},i_{2},\ldots,i_{\delta n}\\}$. Suppose
that $\\{G_{i}[B]:i\in\mathcal{C}^{\prime\prime}\\}$ contains a rainbow path
$u_{1}u_{2}u_{3}$ with $u_{1}u_{2}\in E(G_{i_{1}})$ and $u_{2}u_{3}\in
E(G_{i_{2}})$. (The proof of the case that
$\\{G_{i}[B]:i\in\mathcal{C}^{\prime\prime}\\}$ contains a rainbow $2P_{2}$ is
similar).

Choose a maximal rainbow matching inside
$\\{G_{i_{j}}[A,B\backslash\\{u_{1},u_{2},u_{3}\\}]:j\in[3,\delta n]\\}$, say
$M=\\{e_{i_{j}}:3\leq j\leq s\\}$ with $s\leq\delta n$ and $e_{i_{j}}\in
E(G_{i_{j}})$, such that $G_{i_{j}}[A\backslash
V(M),B\backslash(V(M)\cup\\{u_{1},u_{2},u_{3}\\})]\neq\emptyset$ for all
$j\in[3,s]$. Notice that $G_{i_{j}}$ is $(2\delta
n,K_{\lfloor\frac{n}{2}\rfloor}\cup K_{\lceil\frac{n}{2}\rceil})$-extremal for
all $j\in[s+1,\delta n]$. We greedily select two rainbow paths $P_{A}$ and
$P_{B}$ inside $\\{G_{i_{j}}[A\backslash V(M)]\cup
G_{i_{j}}[B\backslash(V(M)\cup\\{u_{1},u_{2},u_{3}\\})]:j\in[s+1,\delta n]\\}$
with lengths $\lfloor\frac{\delta n-s}{2}\rfloor$ and $\lceil\frac{\delta
n-s}{2}\rceil$ respectively, where $V(P_{A})\subseteq A$ and
$V(P_{B})\subseteq B$.

If $\delta n-s$ is even, then by a similar discussion as Lemma 5.1, it is easy
to find a transversal Hamilton cycle inside $\mathcal{G}$, a contradiction.

Now, assume that $\delta n-s$ is odd. Recall that $|A|=\frac{n}{2}-1$ and
$\delta(\mathcal{G})\geq\frac{n}{2}-1$. Then there exists an edge
$w_{1}w_{2}\in E(G_{i_{1}}[A\backslash V(M\cup P_{A}\cup P_{B}),B])$ with
$w_{1}\in A$ and $w_{2}\in B$. Moreover,
$G_{i}[A,B]=K_{\frac{n}{2}-1,\frac{n}{2}+1}$ for all
$i\in\mathcal{C}^{\prime}$. Notice that one may avoid $w_{2}$ when choosing
$M$ and $P_{B}$. If $w_{2}\in\\{u_{2},u_{3}\\}$, then without loss of
generality, assume that $w_{2}=u_{2}$. Using colors in $\mathcal{C}^{\prime}$
and edges between $A$ and $B$, we can connect $w_{1}u_{2}u_{3}$, all rainbow
edges in $M$, $P_{A}$ and $P_{B}$ in turn to get a single rainbow path
$P^{1}$, whose endpoints are in different parts. Therefore, $|A\backslash
V(P^{1})|=|B\backslash V(P^{1})|$. If $w_{2}\not\in\\{u_{2},u_{3}\\}$, then
using colors in $\mathcal{C}^{\prime}$ and edges between $A$ and $B$, one may
connect $u_{2}u_{3}$, $w_{1}w_{2}$, all rainbow edges in $M$, $P_{A}$ and
$P_{B}$ in turn to get a single rainbow path $P^{2}$, whose endpoints are in
$B$. Therefore, $|A\backslash V(P^{2})|=|B\backslash V(P^{2})|+1$. In each of
the above two cases, it is routine to check that $\mathcal{G}$ has a
transversal Hamilton cycle, a contradiction. ∎

######  Lemma 5.3.

Let $\mathcal{C}$ be a set of colors, and
$\mathcal{G}=\\{G_{i}[Y,B]:i\in\mathcal{C}\\}$ be a collection of bipartite
graphs with common bipartition $(Y,B)$ such that
$7|Y|<|B|\leq\frac{3}{5}|\mathcal{C}|$. If
$\sum_{i\in\mathcal{C}}|E(G_{i}[Y,B])|\geq t|B||\mathcal{C}|$ for some integer
$t$ with $1\leq t\leq|Y|$, then $\mathcal{G}$ contains $t$ disjoint rainbow
star $S_{5}$, each of them has center in $Y$ and other vertices in $B$.

###### Proof.

We use induction to prove this result. If $t=1$, then
$\sum_{i\in\mathcal{C}}|E(G_{i}[Y,B])|\geq|B||\mathcal{C}|$. Suppose that
$\mathcal{G}$ does not contain any rainbow $S_{5}$ with center in $Y$ and
other vertices in $B$. Then each vertex $v\in Y$ satisfies either
$N_{G_{i}}(v,B)\neq\emptyset$ for at most three $i\in\mathcal{C}$, or there
exist three vertices $w,w^{\prime},w^{\prime\prime}\in B$ such that
$N_{G_{i}}(v)\subseteq\\{w,w^{\prime},w^{\prime\prime}\\}$ for all
$i\in\mathcal{C}$. It follows that

$\sum_{i\in\mathcal{C}}|E(G_{i}[Y,B])|=\sum_{v\in
Y}\sum_{i\in\mathcal{C}}d_{G_{i}}(v,B)\leq\sum_{v\in
Y}\max\\{3|B|,3|\mathcal{C}|\\}=3|Y||\mathcal{C}|<|B||\mathcal{C}|,$

a contradiction. That is to say, our result holds for $t=1$.

Assume the result holds for $t$, and we prove it for $t+1$. Now, we give the
following claim.

######  Claim 5.4.

There exists a vertex $w\in Y$ such that $d_{G_{i}}(w,B)\geq 4t+4$ for at
least $4t+4$ colors $i\in\mathcal{\mathcal{C}}$.

###### Proof of Claim 5.4.

Suppose not, then for each vertex $v\in Y$, we have $d_{G_{i}}(v,B)\geq 4t+4$
for at most $4t+3$ colors $i\in\mathcal{\mathcal{C}}$. It implies that

$\displaystyle\sum_{i\in\mathcal{C}}|E(G_{i}[Y,B])|$ $\displaystyle=\sum_{v\in
Y}\sum_{i\in\mathcal{C}}d_{G_{i}}(v,B)$ $\displaystyle=\sum_{v\in
Y}\Big{(}\sum_{\begin{subarray}{c}i\in\mathcal{C}\\\ d_{G_{i}}(v,B)\geq
4t+4\end{subarray}}d_{G_{i}}(v,B)+\sum_{\begin{subarray}{c}i\in\mathcal{C}\\\
d_{G_{i}}(v,B)\leq 4t+3\end{subarray}}d_{G_{i}}(v,B)\Big{)}$
$\displaystyle\leq\sum_{v\in
Y}\Big{(}\sum_{\begin{subarray}{c}i\in\mathcal{C}\\\ d_{G_{i}}(v,B)\geq
4t+4\end{subarray}}|B|+\sum_{\begin{subarray}{c}i\in\mathcal{C}\\\
d_{G_{i}}(v,B)\leq 4t+3\end{subarray}}(4t+3)\Big{)}$
$\displaystyle\leq|Y|((4t+3)|B|+|\mathcal{C}|(4t+3))$
$\displaystyle\leq(4t+3)|Y|(|B|+|\mathcal{C}|)$
$\displaystyle<7(t+1)|Y||\mathcal{C}|$ $\displaystyle<(t+1)|B||\mathcal{C}|,$

a contradiction. ∎

By Claim 5.4, there exists a vertex $w\in Y$ such that $d_{G_{i}}(w,B)\geq
4t+4$ for at least $4t+4$ colors $i\in\mathcal{\mathcal{C}}$. Let
$\mathcal{G}^{\prime}=\\{G_{i}[Y\backslash\\{w\\},B]:i\in\mathcal{C}\\}$. Then

$\sum_{i\in\mathcal{C}}|E(G_{i}[Y\backslash\\{w\\},B])|\geq(t+1)|B||\mathcal{C}|-|B||\mathcal{C}|=t|B||\mathcal{C}|.$

By induction, there are $t$ disjoint rainbow $S_{5}$ inside
$\mathcal{G}^{\prime}$, each of which has center in $Y\backslash\\{w\\}$ and
other vertices in $B$. Let $\mathbf{S}$ be a set consisting of those disjoint
rainbow $S_{5}$. Recall that $d_{G_{i}}(w,B)\geq 4t+4$ for at least $4t+4$
colors $i\in\mathcal{C}$. Hence there exist four colors
$c^{1},c^{2},c^{3},c^{4}\in\mathcal{C}\backslash col(\mathbf{S})$ such that
$d_{G_{c^{j}}}(w)\geq 4t+4$ for all $j\in[4]$. Thus, there are four vertices
$w^{1},w^{2},w^{3},w^{4}\in B\backslash V(\mathbf{S})$ such that $ww^{j}\in
E(G_{c^{j}})$ for all $j\in[4]$. Therefore,
$\\{G_{c^{j}}[\\{w,w^{1},w^{2},w^{3},w^{4}\\}]:j\in[4]\\}$ contains a rainbow
$S_{5}$ with center $w$, which is disjoint with each rainbow star in
$\mathbf{S}$, as desired. ∎

######  Lemma 5.5.

Assume $0<\frac{1}{n}\ll\delta\ll 1$ and $0\leq\gamma\leq 3{\delta}$. Let
$\mathcal{C}$ be a set of $n$ colors, and
$\mathcal{G}=\\{G_{i}:i\in\mathcal{C}\\}$ be a collection of graphs with
common vertex set $V$ of size $n$ such that
$\delta(\mathcal{G})\geq\frac{n}{2}-1$. Let $A\cup B$ be a partition of $V$
with $|A|=\lfloor\frac{n+1}{2}\rfloor+\gamma n$, and let
$\mathcal{C}^{\prime}\cup\mathcal{C}^{\prime\prime}$ be a partition of
$\mathcal{C}$ with $|\mathcal{C}^{\prime\prime}|\leq\delta n$. Define
$Y=\\{v\in A:d_{G_{i}}(v,B)\leq(1-\delta^{\frac{1}{4}})|B|\ \textrm{for at
least}\ \delta^{\frac{1}{4}}|\mathcal{C}^{\prime}|\ \textrm{colors}\
i\in\mathcal{C}^{\prime}\\}$. Assume that $|Y|>\gamma n$, $\mathcal{G}$ does
not contain transversal Hamilton cycles and $G_{i}[B]=\emptyset$ for all
$i\in\mathcal{C}^{\prime}$.

  1. (i)

If $n$ is odd, then $\mathcal{G}$ is the half-split graph collection.

  2. (ii)

If $n$ is even, then there exists a new partition $A^{\prime}\cup B^{\prime}$
of $V$ with $|A^{\prime}|=\frac{n}{2}-1$ such that either
$G_{i}[B^{\prime}]=\emptyset$ for all but at most one $i\in\mathcal{C}$, or
$E(G_{i}[B^{\prime}])\subseteq\\{v_{1}v_{2}\\}$ for fixed vertices
$v_{1},v_{2}\in B^{\prime}$ and all $i\in\mathcal{C}$.

###### Proof.

It is routine to check that

$\displaystyle\lceil\frac{n}{2}-1\rceil|B||\mathcal{C}^{\prime}|$
$\displaystyle\leq\sum_{i\in\mathcal{C}^{\prime}}|E({G_{i}}[A,B])|$
$\displaystyle\leq|Y|(1-\delta^{\frac{1}{4}})|B|\delta^{\frac{1}{4}}|\mathcal{C}^{\prime}|+|Y||B|(1-\delta^{\frac{1}{4}})|\mathcal{C}^{\prime}|+(|A|-|Y|)|B||\mathcal{C}^{\prime}|$
$\displaystyle=(|A|-\delta^{\frac{1}{2}}|Y|)|B||\mathcal{C}^{\prime}|.$ (2)

It implies that $|Y|\leq\frac{\gamma n+1}{\sqrt{\delta}}\leq 4\sqrt{\delta}n$.
Notice that Claim 4.4 and Claim 4.5 (i)-(ii) hold by setting $V_{bad}=Y$ and
$\mathcal{C}_{2}=\mathcal{C}^{\prime}$.

Since $\delta(\mathcal{G})\geq\frac{n}{2}-1$, we have
$|E(G_{i}[A,B])|\geq|B|\lceil\frac{n}{2}-1\rceil$ for each
$i\in\mathcal{C}^{\prime}$, i.e., there are at most
$|B|(\lfloor\frac{n+1}{2}\rfloor+\gamma
n)-|B|\lceil\frac{n}{2}-1\rceil=|B|(\gamma n+1)$ non-edges between $A$ and $B$
in $G_{i}$. Hence
$\sum_{i\in\mathcal{C}^{\prime}}|E(G_{i}[Y,B])|\geq(|Y|-\gamma
n-1)|B||\mathcal{C}^{\prime}|$. By Lemma 5.3, there exist $|Y|-\gamma n-1$
disjoint rainbow $P_{3}$ inside $\\{G_{i}[Y,B]:i\in\mathcal{C}^{\prime}\\}$
with centers in $Y$. Let $\mathbf{P}_{1}$ be a set consisting of those rainbow
$P_{3}$ and $Y_{1}$ be a subset of $Y$ consisting of the centers of them.
Denote $Y_{2}:=Y\backslash Y_{1}$. Then $|Y_{2}|=\gamma n+1$.

Recall that each vertex in $Y$ is adjacent to at least
$\lceil\frac{n}{2}-1\rceil-(1-\delta^{\frac{1}{4}})|B|>4|Y|$ vertices in $A$
for at least
$\delta^{\frac{1}{4}}|\mathcal{C}^{\prime}|>\delta^{\frac{1}{4}}(1-\delta)n>4|Y|$
colors $i\in\mathcal{C}^{\prime}$. Then there exist $\gamma n+1$ disjoint
rainbow $P_{3}$ inside $\\{G_{i}[Y_{2},A\backslash
Y]:i\in\mathcal{C}^{\prime}\backslash col(\mathbf{P}_{1})\\}$ with centers in
$Y_{2}$, and let $\mathbf{P}_{2}$ be a set consisting of those rainbow
$P_{3}$. For each $y\in Y$, denote the rainbow $P_{3}$ in
$\mathbf{P}_{1}\cup\mathbf{P}_{2}$ with center $y$ by $P_{y}:=y^{1}yy^{2}$
with colors $c_{y}^{1}$ and $c_{y}^{2}$. Let
$\mathbf{P}=\mathbf{P}_{1}\cup\mathbf{P}_{2}=\\{P_{y}:y\in Y\\}$.

It is routine to check that there exists a rainbow matching inside
$\\{G_{i}[A\backslash V(\mathbf{P}),B\backslash
V(\mathbf{P})]:i\in\mathcal{C}^{\prime\prime}\\}$, say $M$, such that
$G_{j}[A\backslash V(\mathbf{P}\cup M),B\backslash V(\mathbf{P}\cup M)]$
contains a $3$-matching for each $j\in col(M)$. Furthermore, $G_{j}$ is
$(13\sqrt{\delta},K_{\lfloor\frac{n}{2}\rfloor}\cup
K_{\lceil\frac{n}{2}\rceil})$-extremal for all
$j\in\mathcal{C}^{\prime\prime}\backslash col(M)$. We proceed by considering
the following three cases.

Case 1. $n$ is odd and $|\mathcal{C}^{\prime\prime}\backslash col(M)|$ is odd,
or $n$ is even and $|\mathcal{C}^{\prime\prime}\backslash col(M)|\geq 2$ is
even.

Greedily choose two disjoint rainbow paths $P_{A}$ and $P_{B}$ inside
$\\{G_{i}[A\backslash V(\mathbf{P}\cup M)]\cup G_{i}[B\backslash
V(\mathbf{P}\cup M)]:i\in\mathcal{C}^{\prime\prime}\backslash col(M)\\}$ with
lengths $\lfloor\frac{|\mathcal{C}^{\prime\prime}\backslash
col(M)|-1}{2}\rfloor$ and $\lceil\frac{|\mathcal{C}^{\prime\prime}\backslash
col(M)|+1}{2}\rceil$ respectively, such that $V(P_{A})\subseteq A$ and
$V(P_{B})\subseteq B$. In view of Claim 4.5 (i)-(ii), by using colors in
$\mathcal{C}^{\prime}$, one may connect all rainbow paths in $\mathbf{P}_{2}$
and $\mathbf{P}_{1}$ in turn to get a single rainbow path $P^{1}$ with
$2|Y_{1}|+3|Y_{2}|$ vertices in $A$ and $2|Y_{1}|+|Y_{2}|$ vertices in $B$,
whose endpoints are in different parts. Therefore, $|B\backslash
V(P^{1})|-|A\backslash V(P^{1})|=2-\sigma$. Applying Claim 4.5 (i) again to
connect $P^{1}$, all rainbow edges in $M$, $P_{A}$ and $P_{B}$ in turn, we get
a single rainbow path $P^{2}$ with endpoints are in different parts. Clearly,
$|A\backslash V(P^{2})|=|B\backslash V(P^{2})|$. Together with Claim 4.4, we
know $\mathcal{G}$ contains a transversal Hamilton cycle, a contradiction.

Case 2. $n$ is odd and $|\mathcal{C}^{\prime\prime}\backslash col(M)|$ is
even, or $n$ is even and $|\mathcal{C}^{\prime\prime}\backslash col(M)|$ is
odd.

Greedily choose two disjoint rainbow paths $P_{A}$ and $P_{B}$ inside
$\\{G_{i}[A\backslash V(\mathbf{P}\cup M)]\cup G_{i}[B\backslash
V(\mathbf{P}\cup M)]:i\in\mathcal{C}^{\prime\prime}\backslash col(M)\\}$ with
lengths $\lfloor\frac{|\mathcal{C}^{\prime\prime}\backslash
col(M)|}{2}\rfloor$ and $\lceil\frac{|\mathcal{C}^{\prime\prime}\backslash
col(M)|}{2}\rceil$ respectively, such that $V(P_{A})\subseteq A$ and
$V(P_{B})\subseteq B$. Suppose that there exists an
$i_{1}\in\mathcal{C}^{\prime}\cup col(M)$ such that $G_{i_{1}}[Y_{2}\cup
B]\neq\emptyset$. Choose $y_{1}y_{2}\in E(G_{i_{1}}[Y_{2}\cup B])$. By Claim
4.5 (i)-(ii), we connect all rainbow $P_{3}$ in
$\mathbf{P}_{2}\backslash\\{P_{y_{1}},P_{y_{2}}\\}$, $\mathbf{P}_{1}$, all
rainbow edges in $M$ except the possible edge with color $i_{1}$ and
$P_{A},P_{B}$ in turn to get a single rainbow path $P^{3}$, whose endpoints
are in different parts. Similar to Case 1, we have $|A\backslash
V(P^{3})|-|B\backslash V(P^{3})|=2|\\{y_{1},y_{2}\\}\cap Y_{2}|-1$.

If $y_{1},y_{2}\in Y_{2}$, then let $Q:=y_{1}^{1}y_{1}y_{2}y_{2}^{2}$ with
$col(Q)=\\{c_{y_{1}}^{1},i_{1},c_{y_{2}}^{2}\\}$. If $y_{1}\in Y_{2}$ and
$y_{2}\in B$, then one may assume $y_{2}\notin V(P^{3})$ and let
$Q:=y_{1}^{1}y_{1}y_{2}$ with $col(Q)=\\{c_{y_{1}}^{1},i_{1}\\}$. If
$y_{1},y_{2}\in B$, then we may assume $y_{1},y_{2}\not\in V(P^{3})$ and let
$Q:=y_{1}y_{2}$ with color $i_{1}$. Next, connect $P^{3}$ with the rainbow
path $Q$ by Claim 4.5 (i)-(ii), we get a rainbow path $P^{4}$ with endpoints
$y_{1}^{1},v_{3}$ (if $y_{1},y_{2}\in Y_{2}$) or $u_{3},y_{3}$ (otherwise). It
is routine to check that $|A\backslash V(P^{4})|=|B\backslash V(P^{4})|$.
Together with Claim 4.4, one obtains that $\mathcal{G}$ contains a transversal
Hamilton cycle, a contradiction. Hence, $G_{i}[Y_{2}\cup B]=\emptyset$ for all
$i\in\mathcal{C}^{\prime}\cup col(M)$. Recall that
$\delta(G_{i})\geq\lceil\frac{n}{2}-1\rceil$. This implies that
$N_{G_{i}}(w)=A\backslash Y_{2}$ for all $i\in\mathcal{C}^{\prime}\cup col(M)$
and all $w\in Y_{2}\cup B$. Move vertices in $Y_{2}$ from $A$ to $B$, we get
$|A|=\lceil\frac{n}{2}-1\rceil$, $|B|=\lfloor\frac{n}{2}+1\rfloor$ and
$G_{i}[B]=\emptyset$ for each $i\in\mathcal{C}^{\prime}\cup col(M)$. By Lemmas
5.1 and 5.2, our desired result holds.

Case 3. $n$ is even and $|\mathcal{C}^{\prime\prime}\backslash col(M)|=0$.

By a similar discussion as Case 2 and the proof of Lemma 5.2, we obtain that
$\mathcal{G}[Y_{2}\cup B]$ contains no rainbow $P_{3}$ or $2P_{2}$. Hence
either $G_{i}[Y_{2}\cup B]=\emptyset$ for all but at most one unique
$i\in\mathcal{C}$ or $E(G_{i}[Y_{2}\cup B])\subseteq\\{uv\\}$ for fixed $u,v$
and all $i\in\mathcal{C}$. Move vertices in $Y_{2}$ to $B$, we get
$|A|=\frac{n}{2}-1$, $|B|=\frac{n}{2}+1$. Therefore, either
$G_{i}[B]=\emptyset$ for all but at most one $i\in\mathcal{C}$, or
$E(G_{i}[B])\subseteq\\{uv\\}$ for all $i\in\mathcal{C}$. Recall that
$\delta(\mathcal{G})\geq\frac{n}{2}-1$. In both cases, $\mathcal{G}$ does not
contain transversal Hamilton cycles, as desired. ∎

######  Lemma 5.6.

Assume $0<\frac{1}{n}\ll\delta\ll 1$. Let $\mathcal{C}$ be a set of $n$ colors
and $\mathcal{G}=\\{G_{i}:i\in\mathcal{C}\\}$ be a collection of graphs with
common vertex set $V$ of size $n$. Let $A\cup B$ be a partition of $V$ with
$|A|=\frac{n}{2}$, and let
$\mathcal{C}^{\prime}\cup\mathcal{C}^{\prime\prime}$ be a partition of
$\mathcal{C}$ with $|\mathcal{C}^{\prime\prime}|\leq\delta n$. Assume that
$\delta(\mathcal{G})\geq\frac{n}{2}-1$ and $G_{i}[B]=\emptyset$ for all
$i\in\mathcal{C}^{\prime}$. If $\mathcal{G}$ does not contain transversal
Hamilton cycles, then one of the following holds:

  * •

$\mathcal{G}$ is a spanning collection of $\mathcal{H}_{n-t}^{t}$ for some odd
integer $t$,

  * •

there exists a partition $A^{\prime}\cup B^{\prime}$ of $V$ with
$|A^{\prime}|=\frac{n}{2}-1$, such that either $G_{i}[B^{\prime}]=\emptyset$
for all but at most one $i\in\mathcal{C}$, or
$E(G_{i}[B^{\prime}])\subseteq\\{uv\\}$ for fixed vertices $u,v\in B^{\prime}$
and all $i\in\mathcal{C}$.

###### Proof.

Let $Y=\\{v\in A:d_{G_{i}}(v,B)\leq(1-\delta^{\frac{1}{4}})|B|\ \textrm{for at
least}\ \delta^{\frac{1}{4}}|\mathcal{C}^{\prime}|\ \textrm{colors}\
i\in\mathcal{C}^{\prime}\\}$. Then

$\displaystyle(\frac{n}{2}-1)|B||\mathcal{C}^{\prime}|\leq$
$\displaystyle\sum_{i\in\mathcal{C}^{\prime}}|E(G_{i}[A,B])|$ $\displaystyle=$
$\displaystyle\sum_{v\in
Y}\sum_{i\in\mathcal{C}^{\prime}}d_{G_{i}}(v,B)+\sum_{v\in A\backslash
Y}\sum_{i\in\mathcal{C}^{\prime}}d_{G_{i}}(v,B)$ $\displaystyle\leq$
$\displaystyle|Y|(1-\delta^{\frac{1}{4}})|B|\delta^{\frac{1}{4}}|\mathcal{C}^{\prime}|+|Y||B|(1-\delta^{\frac{1}{4}})|\mathcal{C}^{\prime}|+(\frac{n}{2}-|Y|)|B||\mathcal{C}^{\prime}|$
$\displaystyle=$
$\displaystyle(\frac{n}{2}-\beta|Y|)|B||\mathcal{C}^{\prime}|.$

It follows that $|Y|\leq\frac{1}{\sqrt{\delta}}<\sqrt{\delta}n$. If $|Y|\geq
1$, then our result holds by Lemma 5.5. In what follows, we only consider
$|Y|=0$. It is straightforward to check that Claim 4.4 and Claim 4.5 (i)-(ii)
hold by setting $V_{bad}=Y$ and $\mathcal{C}_{2}=\mathcal{C}^{\prime}$.

Choose a maximal rainbow matching inside
$\\{G_{i}[A,B]:i\in\mathcal{C}^{\prime\prime}\\}$, say $M$, such that
$G_{j}[A,B]$ contains a $2$-matching for each $j\in col(M)$. Furthermore,
$G_{j}$ is $(2\sqrt{\delta},K_{\lfloor\frac{n}{2}\rfloor}\cup
K_{\lceil\frac{n}{2}\rceil})$-extremal for all
$j\in\mathcal{C}^{\prime\prime}\backslash col(M)$. Greedily choose two
disjoint rainbow paths $P_{A}$ and $P_{B}$ inside $\\{G_{i}[A\backslash
V(M)]\cup G_{i}[B\backslash V(M)]:i\in\mathcal{C}^{\prime\prime}\backslash
col(M)\\}$ with lengths $x_{A}$ and $x_{B}$ respectively, such that
$V(P_{A})\subseteq A$ and $V(P_{B})\subseteq B$. In view of Claim 4.5
(i)-(ii), by using colors in $\mathcal{C}^{\prime}$, one may connect all
rainbow edges in $M$, $P_{A}$ and $P_{B}$ into a single rainbow path $P$,
whose endpoints are denoted by $u_{1}\in A$ and $v_{1}\in B$.

If $|\mathcal{C}^{\prime\prime}\backslash col(M)|$ is even, then let
$x_{A}=x_{B}=\frac{|\mathcal{C}^{\prime\prime}\backslash col(M)|}{2}$. Thus,
$|B\backslash V(P)|=|A\backslash V(P)|$. Together with Claim 4.4, we know
$\mathcal{G}$ contains a transversal Hamilton cycle, a contradiction. Hence
$|\mathcal{C}^{\prime\prime}\backslash col(M)|$ is odd. Now, we give the
following claim.

######  Claim 5.7.

  1. (i)

$G_{i}[A]\cup G_{i}[B]=\emptyset$ for all $i\in\mathcal{C}^{\prime}\cup
col(M)$,

  2. (ii)

$G_{i}[A,B]=\emptyset$ for all $i\in\mathcal{C}^{\prime\prime}\backslash
col(M)$.

###### Proof of Claim 5.7.

We only give the proof of $G_{i}[A]=\emptyset$ for all
$i\in\mathcal{C}^{\prime}\cup col(M)$, the other two statements can be proved
by similar arguments.

Suppose that $G_{i_{1}}[A]\neq\emptyset$ for some
$i_{1}\in\mathcal{C}^{\prime}\cup col(M)$. Choose $w_{1}w_{2}\in
E(G_{i_{1}}[A])$. If $i_{1}\in col(M)$, then delete the edge with color
$i_{1}$ from $M$. Hence we can assume that $i_{1}\notin col(P)$ and
$w_{1},w_{2}\notin V(P)$. Using Claim 4.5 (ii) to connect $w_{1}w_{2}$ and the
rainbow path $P$, we get a rainbow path $P^{\prime}$ with endpoints $w_{1}$
and $v_{1}$. Let $x_{A}=\frac{|\mathcal{C}^{\prime\prime}\backslash
col(M)|-1}{2}$ and $x_{B}=\frac{|\mathcal{C}^{\prime\prime}\backslash
col(M)|+1}{2}$. Hence $|B\backslash V(P^{\prime})|=|A\backslash
V(P^{\prime})|$. It follows from Claim 4.4 that $\mathcal{G}$ contains a
transversal Hamilton cycle, a contradiction. ∎

Based on Claim 5.7, we know $\mathcal{G}$ is a spanning collection of
$\mathcal{H}_{n-t}^{t}$ for some odd $t$, as desired. ∎

######  Lemma 5.8.

Assume $0<\frac{1}{n}\ll\delta\ll 1$ and $0\leq\gamma\leq 3{\delta}$. Let
$\mathcal{C}$ be a set of $n$ colors, and
$\mathcal{G}=\\{G_{i}:i\in\mathcal{C}\\}$ be a collection of graphs with
common vertex set $V$ of size $n$ such that
$\delta(\mathcal{G})\geq\frac{n}{2}-1$. Let $A\cup B$ be a partition of $V$
with $|A|=\lfloor\frac{n+1}{2}\rfloor+\gamma n$, and let
$\mathcal{C}^{\prime}\cup\mathcal{C}^{\prime\prime}$ be a partition of
$\mathcal{C}$ with $|\mathcal{C}^{\prime\prime}|\leq\delta n$. Assume that
$\mathcal{G}$ does not contain transversal Hamilton cycles and
$G_{i}[B]=\emptyset$ for all $i\in\mathcal{C}^{\prime}$.

  1. (i)

If $n$ is odd, then $\mathcal{G}$ is the half-split graph collection.

  2. (ii)

If $n$ is even, then one of the following holds:

     * •

$\mathcal{G}$ is a spanning collection of $\mathcal{H}_{n-t}^{t}$ for some odd
integer $t$,

     * •

there exists a new partition $A^{\prime}\cup B^{\prime}$ of $V$ with
$|A^{\prime}|=\frac{n}{2}-1$ such that either $G_{i}[B^{\prime}]=\emptyset$
for all but at most one $i\in\mathcal{C}$, or
$E(G_{i}[B^{\prime}])\subseteq\\{v_{1}v_{2}\\}$ for two fixed vertices
$v_{1},v_{2}\in B^{\prime}$ and all $i\in\mathcal{C}$.

###### Proof.

Define $Y=\\{v\in A:d_{G_{i}}(v,B)\leq(1-\delta^{\frac{1}{4}})|B|\ \textrm{for
at least}\ \delta^{\frac{1}{4}}|\mathcal{C}^{\prime}|\ \textrm{colors}\
i\in\mathcal{C}^{\prime}\\}$. In view of (2), we have $|Y|\leq
4\sqrt{\delta}n$. If $|Y|>\gamma n$, then our result holds by Lemma 5.5. In
what follows, we only consider $|Y|\leq\gamma n$. Therefore,
$|B|\leq|A|-2|Y|-\sigma$ where $\sigma=0$ if $n$ is even and $\sigma=1$
otherwise. Notice that Claim 4.4 and Claim 4.5 (i)-(ii) hold by setting
$V_{bad}=Y$ and $\mathcal{C}_{2}=\mathcal{C}^{\prime}$.

Recall that each vertex in $Y$ is adjacent to at least
$\lceil\frac{n}{2}-1\rceil-(1-\delta^{\frac{1}{4}})|B|>5|Y|$ vertices in $A$
for at least
$\delta^{\frac{1}{4}}|\mathcal{C}^{\prime}|>\delta^{\frac{1}{4}}(1-\delta)n>5|Y|$
colors $i\in\mathcal{C}^{\prime}$. Then there exist $|Y|$ disjoint rainbow
paths $P_{3}$ with centers in $Y$ and endpoints in $A\backslash Y$ using
colors in $\mathcal{C}^{\prime}$. In the graph collection
$\mathcal{G}[A\backslash Y]$, we extend those rainbow paths or choose other