Placing Specified Vertices at Precise Locations on a Hamiltonian Cycle

Abstract

Sharp minimum degree and degree sum conditions are proven for the existence of a Hamiltonian cycle passing through specified vertices with prescribed distances between them in large graphs.

1 Introduction

In this paper, we consider only simple, finite, and undirected graphs. Unless otherwise defined, our notation follows that of [1].

Recently, there have been several results concerning the placement of specified vertices on a Hamiltonian cycle. Kaneko and Yoshimoto proved the following result.

Theorem 1

(Kaneko and Yoshimoto [10]) Let G be a graph of order n, $d \le \frac{n}{4}$ a positive integer and A a set of at most $\frac{n}{2d}$ vertices. If $\delta (G) \ge \frac{n}{2}$ then there exists a Hamiltonian cycle in G with the distance, along the cycle, between any pair of vertices of A at least d.

Sárközy and Selkow managed to ensure specified distances between almost all the consecutive pairs but did not put the specified vertices in order.

Theorem 2

(Sárközy and Selkow [15]) There are $\omega , n_{0} > 0$ such that if G is a graph on $n \ge n_{0}$ vertices with $\delta (G) \ge n/2$, d is an arbitrary integer with $3 \le d \le \omega n/2$ and S is an arbitrary set of vertices in G with $2 \le |S| = k \le \omega n / d$, then for every sequence $d_{i}$ of integers with $3 \le d_{i} \le d$, $1 \le i \le k - 1$, there is a Hamiltonian cycle C of G and an ordering of the vertices of S, $a_{1}, a_{2}, \dots , a_{k}$, such that the vertices of S are visited in this order on C and we have $|dist_{C}(a_{i}, a_{i + 1}) - d_{i}| \le 1$ for all but one i with $1 \le i \le k - 1$.

More recently, Faudree et al. placed specified vertices in order but were unable to prescribe the distances exactly.

Theorem 3

(Faudree et al. [7]) Let $t \ge 3$ be an integer and $\epsilon , \gamma _{1}, \gamma _{2}, \dots , \gamma _{t}$ positive real numbers having $\sum _{i = 1}^{t} \gamma _{i} = 1$ and $0< \epsilon < \min \{ \frac{\gamma _{i}^{2}}{2} \}$. For $n \ge \frac{7t^{12} \times 10^{10}}{\epsilon ^{6}}$, let G be a graph of order n having $\delta (G) \ge \frac{n + t - 1}{2}$ or $\delta (G) \ge \frac{n}{2}$ and $\kappa (G) \ge \frac{3t}{2}$. For every $X = \{ x_{1}, x_{2}, \dots , x_{t} \} \subseteq V(G)$, there exists a Hamiltonian cycle H containing the vertices of X in order such that $(\gamma _{i} - \epsilon ) n \le dist_{H}(x_{i}, x_{i + 1}) \le (\gamma _{i} + \epsilon ) n$ for all $1 \le i \le t$. Furthermore, the minimum degree and connectivity conditions are sharp.

In the case where there are only two vertices specified, the following conjecture has been attributed to H. Enomoto.

Conjecture 1

[5] If G is a graph of order $n \ge 3$ and $\delta (G) \ge n/2 + 1$, then for any $x, y \in V(G)$, there is a Hamiltonian cycle C of G such that $d_{C}(x, y) = \left\lfloor n/2 \right\rfloor$.

This conjecture was generalized by Faudree and Li.

Conjecture 2

(Faudree and Li [9]) If G is a graph of order n with $\delta (G) \ge n/2 + 1$, then for any integer $2 \le m \le n/2$ and for any $x, y \in V(G)$, there is a Hamiltonian cycle C of G such that $dist_{C}(x, y) = m$.

The case of Conjecture 2 where $n \ge 6m$ was proven in [8]. Faudree and Gould recently provided a sharp minimum degree condition for the placement of specified vertices at precise locations relative to each other on a Hamiltonian cycle.

Theorem 4

(Faudree and Gould [6]) Let $n_{1}, \dots , n_{k - 1}$ be a set of $k - 1$ integers each at least 2 and $\{x_{1}, \dots , x_{k}\}$ be a fixed set of k ordered vertices in a graph G of order n. If $\delta (G) \ge (n + 2k - 2)/2$, then there is $N = N(k, n_{1}, \dots , n_{k - 1})$ such that if $n \ge N$, there is a Hamiltonian cycle C of G such that $dist_{C}(x_{i}, x_{i + 1}) = n_{i}$ for all $1 \le i \le k - 1$.

Our first result is very closely related to Theorem 4. Our degree assumption is lower but, since our choices of the lengths $n_{i}$ must be large, we are not bound by the following sharpness example for Theorem 4, noted in [6]. Let

$$\begin{aligned} G = \overline{K}_{(n - 2k + 3)/2} + \left( \frac{n + 2k - 3}{2(2k - 2)} K_{2k - 2} \right) . \end{aligned}$$

Then $\delta (G) = \frac{n + 2k - 3}{2}$ but if k vertices are all selected from one of the copies of $K_{2k - 2}$, then there does not exist $k - 1$ internally disjoint paths of length 3 between consecutive pairs of these vertices.

Theorem 5

Given an integer $k \ge 3$, let G be a graph of sufficiently large order n. Then there exists $n_{0} = n_{0}(k, n)$ such that if $n_{1}, n_{2}, \dots , n_{k}$ are a set of k positive integers with $n_{i} \ge n_{0}$ for all i, $\sum n_{i} = n$, and $\delta (G) \ge \frac{n + k}{2}$, then for any k distinct vertices $x_{1}, x_{2}, \dots , x_{k}$ in G, there exists a Hamiltonian cycle such that the length of the path between $x_i$ to $x_{i+1}$ on the Hamiltonian cycle is $n_i$.

Theorem 5 includes the best possible bound on $\delta (G)$ when k is even by the following example. Suppose n is large and satisfies appropriate divisibility constraints with respect to k. Consider two complete graphs A and B each of order $\frac{n - (k + 1)}{2}$. Let C be the remaining $k + 1$ vertices. If we let $+$ denote the standard graph join of inserting all edges between two disjoint sets, then let $G = (A + C) \cup (C + B)$ where the copies of vertices of C are identified. If all of the vertices $x_{1}, \dots , x_{k}$ are chosen from A and each length $n_{i}$ is chosen to be $\frac{n}{k}$, then certainly at least $\left\lceil \frac{k}{2} \right\rceil$ of the paths between consecutive vertices on the cycle must pass through C into B. These $\frac{k}{2}$ paths through B must contain at least a total of $|B| + |C| = \frac{n + k + 1}{2}$ internal vertices, which is more than the desired $\frac{k}{2} (\frac{n}{k} - 1)$, a contradiction. Thus, there is no Hamiltonian cycle with consecutive specified vertices at distance precisely $n_{i}$ apart. Furthermore, this graph has $\delta (G) = |A| + |C| - 1 = \frac{n - k - 1}{2} + k = \frac{n + k - 1}{2}$.

Our next result provides a degree sum condition for the same placement of specified vertices on a Hamiltonian cycle.

Theorem 6

Given an integer $k \ge 3$, let G be a graph of sufficiently large order n. Then there exists $n_{0} = n_{0}(k, n)$ such that if $n_{1}, n_{2}, \dots , n_{k}$ are a set of k positive integers with $n_{i} \ge n_{0}$ for all i, $\sum n_{i} = n$, and $\sigma _{2}(G) \ge n + 2k - 2$, then for any k distinct vertices $x_{1}, x_{2}, \dots , x_{k}$ in G, there exists a Hamiltonian cycle such that the length of the path between $x_i$ to $x_{i+1}$ on the Hamiltonian cycle is $n_i$.

Theorem 6 includes the best possible bound on $\sigma _{2}(G)$ by the following example. Let A be a complete graph on k vertices and B be a complete graph on $n - (3k - 1)$ vertices. Let C be the remaining $2k - 1$ independent vertices. If we again let $G = (A + C) \cup (C + B)$, choose all vertices $x_{i} \in A$, and choose lengths of paths $n_{i}$ to be at least 3 each, there is no Hamiltonian cycle with these specified vertices at distance $n_{i}$ apart since $n_{i} > 2$ for all i. Furthermore, this graph has $\sigma _{2}(G) = (|A| - 1) + 2|C| + (|B| - 1) = n + 2k - 3$.

Theorems 5 and 6 are proven in Sect. 4.

Our proof follows the same general outline as the proof in [3]. It utilizes several extremal lemmas based on the structure of the reduced graph provided by the Regularity Lemma. The lemmas deal with the cases where the minimum degree of the graph is small, where the reduced graph has a large independent set and where the connectivity of the reduced graph is small.

2 Preliminiaries

Given two sets of vertices A and B, let E(A, B) denote set of edges with one end in A and one end in B and let $e(A, B) = |E(A, B)|$. Define the density between A and B to be

$$\begin{aligned} d(A, B) = \frac{e(A, B)}{|A||B|}. \end{aligned}$$

Definition 1

Let $\epsilon > 0$. Given a graph G and two nonempty disjoint vertex sets $A, B \subseteq V$, we say that the pair (A, B) is $\epsilon$ -regular if for every $X \subseteq A$ and $Y \subseteq B$ satisfying

$$\begin{aligned} |X|> \epsilon |A| ~ ~ ~ \text {and} ~ ~ ~ |Y| > \epsilon |B| \end{aligned}$$

we have

$$\begin{aligned} |d(X, Y) - d(A, B)| < \epsilon . \end{aligned}$$

We will also use the following one-sided but stronger version of regularity.

Definition 2

Let $\epsilon , \delta > 0$. Given a graph G and two nonempty disjoint vertex sets $A, B \subseteq V$ forming an $\epsilon$-regular pair, we say that the pair (A, B) is $(\epsilon , \delta )$ -super-regular if for every $X \subseteq A$ and $Y \subseteq B$ satisfying

$$\begin{aligned} |X|> \epsilon |A| ~ ~ ~ \text {and} ~ ~ ~ |Y| > \epsilon |B|, \end{aligned}$$

we have

$$\begin{aligned} e(X, Y) > \delta |X| |Y|, \end{aligned}$$

and furthermore $deg_{B}(a) > \delta |B|$ for all $a \in A$ and $deg_{A}(b) > \delta |A|$ for all $b \in B$.

The following is the degree form of the famous Regularity Lemma of Szemerédi.

Lemma 1

(Regularity lemma—Szemerédi [16]) For every $\epsilon > 0$ and every positive integer m, there is an $M = M(\epsilon )$ such that if G is any graph and $d \in (0,1)$ is any real number, then there is a partition of V(G) into $\ell +1$ clusters $V_{0},V_{1},\dots ,V_{\ell }$, and there is a subgraph $G^\prime \subseteq G$ with the following properties:

• (1) $m \le \ell \le M$,

• (2) $|V_{0}|\le \epsilon |V(G)|$,

• (3) $|V_{1}| = \dots = |V_{\ell }|=L \le \epsilon |V(G)|$,

• (4) $\deg _{G^\prime }(v)>\deg _{G}(v)-(d+\epsilon )|V(G)|$ for all $v\in V(G)$,

• (5) $e(G^\prime [V_i]) = 0$ for all $i \ge 1$,

• (6) for all $1\le i < j\le \ell$ the graph $G^\prime [V_{i},V_{j}]$ is $\epsilon$-regular and has density either 0 or greater than d.

Based on the partition of a graph given by the Regularity Lemma, we define the reduced graph R to be the graph consisting of a vertex for each cluster of the partition and an edge between two vertices when the corresponding two clusters form an $\epsilon$-regular pair with density greater than d. This next lemma allows the creation of a super-regular pair from an $\epsilon$-regular pair by simply removing some vertices.

Lemma 2

([4, Lemma 7.5.1] ) Let (A, B) be an $\epsilon$-regular pair of density d and let $Y \subseteq B$ have size $|Y| \ge \epsilon |B|$. Then all but at most $\epsilon |A|$ of the vertices in A (each) have at least $(d - \epsilon )|Y|$ neighbors in Y.

We will use a simple corollary of this result.

Corollary 7

Let (A, B) be an $\epsilon$-regular pair of density d such that $|A| = |B|$. Then there exist subsets $A' \subseteq A$ and $B' \subseteq B$ with $|A'| = |B'| \ge (1 - \epsilon )|A|$ such that the pair $(A', B')$ is $(\epsilon , d - 2\epsilon )$-super-regular.

Our next fact follows trivially from the definition of super-regular pairs. This fact allows for the creation of short paths between pairs of vertices in super-regular pairs.

Fact 1

Given an $(\epsilon , d)$-super-regular pair (A, B) and a pair of vertices $a \in A$ and $b \in B$, there exists a path of length at most 3 from a to b in the graph induced on $A \cup B$.

A special case of the famous Blow-Up Lemma of Komlós, Sárközy, Szemerédi [11], stated in [15], is the following.

Lemma 3

(Sárközy and Selkow [15]) For every $\delta > 0$, there are $\epsilon _{0} = \epsilon _{0}(\delta ), n_{0} = n_{0}(\delta ) > 0$ such that if $\epsilon \le \epsilon _{0}$ and $n \ge n_{0}$, $G = (A, B)$ is an $(\epsilon , \delta )$-super-regular pair with $|A| = |B| = n$ and $x \in A$ and $y \in B$, then there is a Hamiltonian path of G from x to y.

The following theorem gives us a degree sum condition on the reduced graph R based on our assumed degree sum condition on G.

Theorem 8

(Kühn et al. [12]) Given a constant c, if $\sigma _{2}(G) \ge cn$, then $\sigma _{2}(R) > (c - 2d - 4\epsilon )|R|$.

We will also use the following theorem of Ore.

Theorem 9

(Ore [14]) If G is 2-connected, then G contains a cycle of length at least $\sigma _{2}(G)$.

We will also use the following result of Williamson. Recall that a graph is called panconnected if, between every pair of vertices u and v, there is a path of every possible length from dist(u, v) up to $n - 1$. Note that if the diameter of the graph is 2, then $dist(u, v) \le 2$ so this definition provides all possible lengths of paths.

Theorem 10

(Williamson [17]) Let G be a graph of order n. If $\delta (G) \ge \frac{n + 2}{2}$, then G is panconnected with diameter 2.

3 Proof Outline

Given an integer $k \ge 3$ and desired path segment lengths $n_{1}, n_{2}, \dots , n_{k}$, we choose constants $\epsilon$ and d as follows:

$$\begin{aligned} 0 < \epsilon \ll d \ll \frac{1}{k^{2}}, \end{aligned}$$

where $a \ll b$ is used to indicate that a is chosen to be sufficiently small relative to b. Let n be sufficiently large to apply the Regularity Lemma 1 with constant $\epsilon$ to get large clusters and let R be the corresponding reduced graph. Note that, when applying Lemma 1, there are at least $\frac{1}{\epsilon }$ clusters so $|R| \ge \frac{1}{\epsilon }$.

We use a sequence of lemmas to eliminate extremal cases of the proof. Without loss of generality, we assume $n_{k} \ge n_{i}$ for all i. Our first lemma establishes the case of Theorem 6 when $\delta (G)$ is small.

Lemma 4

If $\delta (G) \le \frac{n_{k}}{8}$, then Theorem 6 holds.

Lemma 4 is proven in Sect. 5. By Lemma 4, we may assume $\delta (G) \ge \frac{n_{k}}{8} \ge \frac{n}{8k}$ in the proof of Theorem 6. Our next lemmas establish the case where G contains a large independent set. Although the statements are almost identical, the different degree assumptions require slight differences in the proofs.

Lemma 5

Let $\lambda > 0$ be a sufficiently small real number. If $\alpha (G) \ge (\frac{1}{2} - \lambda )n$, then Theorem 5 holds.

Lemma 6

Let $\lambda > 0$ be a sufficiently small real number. If $\alpha (G) \ge (\frac{1}{2} - \lambda )n$, then Theorem 6 holds.

Lemmas 5 and 6 are proven in Sect. 6.

Our final lemmas establish the case for small connectivity, that is, when $\kappa (R) \le 1$. Again the statements look identical but the different assumptions of the theorems require slightly different proofs.

Lemma 7

If $\kappa (R) \le 1$, then Theorem 5 holds.

Lemma 8

If $\kappa (R) \le 1$, then Theorem 6 holds.

Lemmas 7 and 8 are proven in Sect. 7.

Once all these lemmas are in place, we use Ore’s Theorem (Theorem 9) to construct a long cycle in the reduced graph. Alternating edges of this cycle are made into super-regular pairs of the graph. This structure is then used to construct the desired paths. The complete proofs of our main results are presented in the following section. Since the non-extremal case, the case when all of the above lemmas are assumed, looks generally the same for both of our main results and the conclusions are the same, we combine both proofs into one.

4 Proof of Theorems 5 and 6

Since the conclusions of both results are identical and the proofs are the same aside from applications of different lemmas, we provide a single proof for both theorems.

Proof

By Lemma 7 or 8, we may assume R is 2-connected. By Theorem 8, we know that $\sigma _{2}(R) \ge (1 - 2d - 4\epsilon )|R|$. Thus, we may apply Theorem 9 to obtain a cycle C within $V(R) \setminus v_{0}$ of length at least $(1 - 2d - 4\epsilon )|R|$ in R. Define the “garbage set” to include $V_{0}$ and those clusters not associated to vertices in C. Without loss of generality, suppose these clusters are $V_{1}, V_{2}, \dots , V_{s}$ where $s \le (2d + 4\epsilon )|R|$. This means that so far, the garbage set contains at most $(2d + 5\epsilon )n$ vertices.

Color the edges of the cycle C (in R) with red and blue such that no two red edges are adjacent and at most one pair of blue edges is adjacent (in the case when |C| is odd). Apply Corollary 7 on the pairs of clusters in G corresponding to the red edges of C, to obtain super-regular pairs where the two sets of each super-regular pair have the same order. All vertices not in the super-regular pairs are added to the garbage set and redefine the clusters $C_{i}$ to be the clusters without these garbage vertices. Note that we have added at most $\epsilon n$ vertices to the garbage set.

If C is odd, let $c_{0}$ be the vertex incident to two blue edges, let $C_{0}$ be the corresponding cluster and let $C_{0}^{+}$ and $C_{0}^{-}$ be the neighboring clusters. Since the pairs $(C_{0}^{-}, C_{0})$ and $(C_{0}, C_{0}^{+})$ are both sufficiently large and $\epsilon$-regular, there exists a set of k vertices $T_{0} \subseteq C_{0}$, each with both an edge to $C_{0}^{-}$ and an edge to $C_{0}^{+}$. We will use these vertices as transportation and move all of $C_{0} \setminus T_{0}$ to the garbage set. Since each cluster contains at most $\epsilon n$ vertices, the garbage set still contains at most $(2d + 7\epsilon )n$ vertices.

Let $G_{C}$ denote the subgraph of G with vertex set consisting of the set of vertices remaining in clusters associated with C that have not been moved to the garbage set and let D denote the garbage set and with $E(G_{C})$ consisting of the edges between consecutive pairs of clusters corresponding to the edges of C. Note that $|D| \le (2d + 7\epsilon ) n$.

By Lemma 4, we may assume $\delta (G) \ge \frac{n_{k}}{8}$ for both proofs. In particular, the vertices in D each have at least $\frac{n_{k}}{8} - (|D| - 1) \gg \epsilon n$ edges to $G_{C}$, even in the proof of Theorem 6.

The pairs of clusters corresponding to the red edges of C, those that are now super-regular, will be called couples and if A and B are a couple, then each of A and B is called the spouse of the other. A path is said to balance the couples in $G_{C}$ if for every couple that the path visits, it uses an equal number of vertices from each spouse in the couple. Note that the removal of a balancing path preserves the fact that the two spouses in every couple have the same order.

For each chosen vertex $x_{i}$, if $x_{i} \notin G_{C}$, then by Lemma 4, there are two edges from $x_{i}$ to vertices $x_{i}'$ and $x_{i}^{^{\prime \prime }}$ in $G_{C}$. If $x_{i} \in G_{C}$, then simply define $x_{i}' = x_{i}^{^{\prime \prime }} = x_{i}$.

For each index i with $1 \le i \le k$, construct a path $P_{i}$ through $G_{C}$ from $x_{i}^{^{\prime \prime }}$ through every cluster of $G_{C}$ by going all the way around the clusters corresponding to the cycle C and then continuing around to $x_{i + 1}'$, where indices are taken modulo k. This path is constructed to be balancing except possibly at one end depending on the parity of the path through $G_{C}$. If the path is not balancing, we remove a single vertex from the unbalanced pair to make it balanced again, and place that vertex in D. This process adds at most $k \ll |D|$ vertices to D. Using Fact 1, this path can be constructed to use at most 2 vertices from each cluster for each time the path passes through. Since each path goes around the cycle at most twice, each path has length at most 4|R|. Together these paths form a cycle with the selected vertices $x_{i}$ appearing in order. The goal of the rest of the proof is to extend these paths to their desired lengths in a controlled way.

Let (A, B) be a super-regular pair of clusters on C. A balancing path starting in A and ending in B which contains a vertex $v \in D$ is called v -absorbing. The following claim was proven in [3].$\square$

Claim 1

(Coll et al. [3]) Avoiding any selected set of at most $1296 k d \ell$ clusters and any set of at most $\frac{(2d + 7\epsilon )n}{81 k d \ell }$ vertices in each of the remaining clusters, there exists a v-absorbing path of order at most 17. Otherwise the desired Hamiltonian cycle already exists.

We include the proof from [3] for completeness.

Proof

Let $L'$ be the order of the smallest cluster in C. Recall that L is the order of each non-garbage cluster of G from Lemma 1 so $L \ge \frac{(1 - \epsilon ) n}{r}$ and so $L' \ge \frac{(1 - \epsilon )^{2} n}{r} - 2k \ge \frac{(1 - 2\epsilon ) n}{r} - 2k$ to avoid the vertices used in the initial paths.

Fact 2

If we have created at most $|D| - 1$ such paths, at most $1296 k d \ell$ clusters would have order at most $L' - \frac{(2d + 7\epsilon )n}{81k d \ell }$.

Proof

Each absorbing path constructed in this claim has order at most 16 (other than the vertex v), so we lose at most 16 vertices from $G_{C}$ for each vertex of D. Since $|D| \le (2d + 7\epsilon )n$, the result follows.$\square$

Note that the remaining clusters would have remaining order at least

$$\begin{aligned} L' - \frac{16(2d + 7\epsilon )n}{1296k d \ell } = L' - \frac{(2d + 7\epsilon )n}{81 k d \ell } \ge L'\left( 1 - \frac{1}{9k} \right) \end{aligned}$$

since $d \gg \epsilon$.

Let $v \in D$ such that there is no absorbing path for v of order at most 17. Since $d(v) \ge \frac{n_{k}}{8} \ge \frac{n}{8k}$, v must have at least $\frac{n}{8k\ell } \ge \frac{L'}{9k} + 2$ edges to at least $\frac{\ell }{8k} \gg 1296k d \ell$ clusters. Let A and B be two clusters which are not already ignored to which v has at least two edges to vertices that are not already in an initial path or an absorbing path.

For convenience, we call two clusters X and Y a couple or spouses (in relation to each other) if X and Y are consecutive on C and the pair (X, Y) is a super-regular pair.

The following facts are easily proven using the structure we have provided and the lemmas proven before.

Fact 3

A and B are not a couple.

Otherwise letting $a \in A$ and $b \in B$ be available neighbors of v, the path avb is a v-absorbing path.

Let $A'$ and $B'$ denote the spouses of A and B, respectively, let $a',b'\in R$ correspond to $A'$ and $B'$, respectively. Similarly for another couple (P, Q) of clusters, let p and q be the corresponding vertices of R. Define the following sets of clusters:

• $X_A:=\{$couples (P, Q) of clusters such that $pa'$ and $qa'$ are edges in $R\}$,

• $X_B:=\{$couples (P, Q) of clusters such that $pb'$ and $qb'$ are edges in $R\}$, and

• $X_{AB}:=\{$couples (P, Q) of clusters such that one of p or q has an edge to both $a'$ and $b'$ in $R\}$. In particular, let $X_{AB}'$ denote the clusters (either P or Q) in $X_{AB}$ that are not the neighbors of $A'$ and $B'$.

Since we are considering two neighbors of v in A (and two neighbors of v in B), say $v_{1}$ and $v_{2}$, if $X_{A}$ (or similarly $X_{B}$) contains even a single couple (P, Q), then we can absorb v using a path of the form $v_{1}vv_{2} - A' - P - Q - A'$. Thus, we may actually assume $X_{A} = X_{B} = \emptyset$.

Our next fact follows from the fact that $\sigma _{2}(R) \ge (1 - 2d - 4\epsilon )|R|$.

Fact 4

There are at most $(2d - 4\epsilon )|R|$ clusters in C which are not in $X_{AB}$.

If there is an edge xy between two (not already used) vertices in clusters in $X_{AB}'$, then there is a v-absorbing path of the form $v_{1}vv_{2} - A' - (X_{AB} \setminus X_{AB}') - xy - (X_{AB} \setminus X_{AB}') - A'$. Thus, the graph induced on the vertices in clusters in $X_{AB}'$ contains no edges. By Lemma 5 or 6, we have the desired Hamiltonian cycle. This completes the proof of Claim 1. $\square$

By Claim 1, since $|D| \le (2d + 7\epsilon )n$, we can construct an absorbing path for each vertex $v \in D$ where these paths are all disjoint. Let $P^{v}$ be an absorbing path for v with ends of $P^{v}$ in clusters $C_{i}$ and $C_{i + 1}$. Suppose uw is the edge of $P_{k}$ from $C_{i}$ to $C_{i + 1}$. Then using Fact 1, we can replace the edge uw with the path $P^{v}$ with the addition of at most 4 extra vertices at either end. Note that absorbing a vertex $v \in D$ into a path $P_{i}$ using the absorbing path will always change the parity of the length of $P_{i}$.

For each path $P_{i}$ that is not already completed and not the correct parity, absorb a single vertex from D into $P_{i}$. This will change the parity of the path. At this point, every path has the correct parity and has length at most $4|R| + 17 \le 4M + 17$ where M is a function of $\epsilon$ provided by Lemma 1.

By the same process, all remaining vertices of D can be absorbed into $P_{k}$. This makes $|P_{k}|$ larger but since $|D| \le (2d + 7\epsilon )n$ and each absorbing path $P^{v}$ for $v \in D$ has order at most 17, we get $|P_{k}| \le 4|M| + 17(2d + 7\epsilon )n < n_{k}$.

The following lemma, stated in [13], is an easy exercise using the definition of $(\epsilon , \delta )$-super-regular pairs and Lemma 3.

Lemma 9

[13] Let U and V be two clusters forming a balanced $(\epsilon , \delta )$-super-regular pair with $|U| = |V| = L$. Then for every pair of vertices $u \in U$ and $v \in V$, there exist paths of all odd lengths $\ell$ between u and v satisfying either

• (a) $3 \le \ell \le \delta L$ or

• (b) $(1 - \delta )L \le \ell \le L$.

For each i with $1 \le i \le k$, let $r_{i} = n_{i} - |P_{i}|$ be the number of vertices that each path $P_{i}$ currently lacks from its desired order. Note that since each path $P_{i}$ already has the correct parity, $r_{i}$ must be even for all i. Without loss of generality, suppose the numbers $r_{i}$ are in increasing order. Recall that each path $P_{i}$ already uses at least one vertex from every cluster in $G_{C}$ so we may apply Lemma 9 to any couple of clusters to absorb all of the vertices from the clusters into the path $P_{i}$. Similarly by Lemma 9, if L is the order of a cluster in the couple, we may absorb any even number of vertices between 2 and $\delta L - 1$ from the couple of clusters into the path $P_{i}$. Note that in this last case, if at most $\frac{\delta L}{2}$ vertices are used up and removed from each cluster in the couple, then what remains of this couple of clusters is $(\epsilon , \delta /2)$-super-regular.

Let $o = \left\lfloor \frac{|C|}{2} \right\rfloor$ and for $1 \le j \le o$, let $L_{j}$ denote the number of vertices remaining unused in each spouse of the jth couple. Without loss of generality, suppose $L_{j} \le L_{j + 1}$ for all j and further suppose we recalculate, reorder and relabel these numbers each time a path construction is completed.

Now let i be the smallest index of a path $P_{i}$ such that $|P_{i}| < n_{1}$. If $r_{i} \ge 2L_{1}$, then using Lemma 9, absorb all vertices in the first couple of clusters into $P_{i}$, relabel the couples, and then repeat. If $r_{i} < 2L_{1}$, then using Lemma 9, absorb two vertices from each couple of remaining clusters until either the path $P_{i}$ is completed (order $n_{i}$) or we have used two vertices from all remaining couples, and then repeat. Note that at most a total of $k \epsilon n$ vertices will be absorbed in this way, so no remaining cluster will lose more than $\frac{\delta L_{j}}{2}$ vertices in this process. Finally $P_{k}$ will simply absorb all remaining vertices. $\square$

5 Proof of Lemma 4

Recall that Lemma 4 claims Theorem 6 holds when $\delta (G) \le \frac{n_{k}}{8}$.

Proof

Let G be a graph satisfying the assumptions of Theorem 6. Let $a \in V(G)$ with $|N(a)|=\delta (G) \le \frac{n_{k}}{8}$, and partition V(G) as follows:

$$\begin{aligned} B= & {} G \setminus (a \cup N(a))\\ A= & {} \left\{ v \in a \cup N(a): |N(v) \cap V(B)| < \frac{1}{8}(n+k-\delta (G)-1) \right\} \\ C= & {} \left\{ v \in a \cup N(a): |N(v) \cap V(B)| \ge \frac{1}{8}(n+k-\delta (G)-1) \right\} \end{aligned}$$

Note that, since $\sigma _2(G) \ge n+2k-2$, the set A induces a complete graph. Furthermore, the set B has order $n-1-\delta (G)$, and A is nonempty since $a \in A$. Since $\sigma _{2}(G) \ge n + 2k - 2$ and a has no edges to B, each vertex in B has degree at least $n + 2 k - 2 - \delta (G)$ which means $\delta (G[B]) \ge n +2k - 3 - 2\delta (G)$. Also note that since $\sigma _{2}(G) \ge n + 2k - 2$, it is easy to see that $\kappa (G) \ge 2k$. First, a claim about subsets of B.$\square$

Claim 2

Every subset of B of order at least $\frac{3n_{k}}{8}$ is panconnected with diameter 2.

Proof

With $|B| = n - \delta (G) - 1$ and $\delta (G[B]) \ge n + 2k - 2 - 2\delta (G)$, we see that $\delta (G[B]) \ge |B| - \delta (G) \ge |B| - \frac{n_{k}}{8}$. Therefore, for any subset $B' \subseteq B$ with $|B'| \ge \frac{3n_{k}}{8}$, we have $\delta (G[B']) \ge |B'| - \frac{n_{k}}{8} > \frac{|B'| + 2}{2}$. By Theorem 10, we see that $B'$ is panconnected.$\square$

Consider k selected vertices $X = \{x_1, \dots , x_k\} \subseteq V(G)$. Let $X_{A}$ denote the (possibly empty) set $X \cap A$. First assume that $|X_{A}| = t \ge 1$. Since $\kappa (G) \ge 2k \ge 2t$, we will show that there exists a set of 2t disjoint paths $\mathscr {P}_{A}$ starting at the vertices of $X_{A}$, each vertex of $X_{A}$ beginning two paths, with these paths ending in B, avoiding all other vertices of X. Such a set of paths is achieved by first choosing a system of distinct representatives, say a vertex $a_{x} \in N(x)$ for each vertex $x \in X_{A}$, letting $A_{X}$ denote the set $X \cap A$ along with all the representatives, and then applying Menger’s Theorem [1] on $G \setminus (X \setminus A)$ to find disjoint paths from $A_{X}$ to B.

If there are any vertices remaining in $A \setminus X_{A}$ that have not been used on the 2t paths, we redefine one of the paths to include these vertices, using Menger’s Theorem and the fact that A is complete. If $t = 0$, then simply use Menger’s Theorem to find two paths from A to B and use all of A to patch these two together into a single path including all of A.

As vertices of B are selected and used on various paths, we continuously call the set of vertices in B that have not already been prescribed or otherwise mentioned the remaining vertices in B. For example, so far, the set $B \setminus (X \cup V(\mathscr {P}_{A}))$ is all the remaining vertices of B. Our goal is to maintain at least $\frac{3n_{k}}{8}+1$ remaining vertices to be able to apply Claim 2 as needed within these remaining vertices.

Let $C \setminus X = \{c_{1}, c_{2}, \dots , c_{s} \}$. Since $|C| \le \delta (G) \le \frac{n_{k}}{8}$ and $deg_{B}(c_{i}) \ge \frac{1}{8} (n + k - \delta (G) - 1)$ for each $c_{i} \in C \setminus X$ (or $x_{i} \in X \cap C$), we can choose a set of two distinct neighbors in $B \setminus (X \cup V(\mathscr {P}_{A}))$, say $b_{i}$ and $b_{i}'$. For each vertex $x_{i} \in X \cap C$, select these two neighboring vertices to serve as proxies for $x_{i}$. These proxy vertices will represent $x_{i}$ when constructing paths because a path from $b_{i}'$ to $b_{i + 1}$ trivially extends to a path from $x_{i}$ to $x_{i + 1}$.

Now consider the vertices of $C \setminus X$. By Claim 2, there exists a path, through the remaining vertices of B, with at most one intermediate vertex, say $d_{i}$, from $b_{i}'$ to $b_{i + 1}$ for each i. Since $|C| \le \frac{n_{k}}{8}$, such short paths can be iteratively constructed for all i with $1 \le i \le s - 1$ to create a single path $P_{C}$ starting and ending in B, at $b_{1}$ and $b_{s'}$ to be exact, and containing all vertices of $C \setminus X$ with $|P_{C}| < 4 |C| \le \frac{n_{k}}{2}$.

We may now construct paths within B to build the desired Hamiltonian cycle. Each path $P_{i}$ for $1 \le i \le k - 1$ can be constructed in any order by starting at $x_{i}$ (or a corresponding proxy vertex) and ending at $x_{i + 1}$ (or a corresponding proxy vertex) using Claim 2 within the remaining vertices of B so that the path $P_{i}$ has precisely the desired length $n_{i}$. Finally, there are at least

$$\begin{aligned}&|B| - \left| B \cap \left( \cup _{i = 1}^{k - 1} V(P_{i})\right) \right| - |B \cap V(\mathscr {P}_{A})| - |B \cap V(P_{C})|\\&\quad \ge (n - 1 - \delta (G)) - (k + 1) - (3|C|)\\&\quad \ge \frac{3n_{k}}{8} + 2 \end{aligned}$$

remaining vertices in B. With these and Claim 2, we construct a short path with at most one internal vertex from an end of $P_{C}$ to $x_{k}$ (or a corresponding proxy vertex) and a path containing all remaining vertices of B from $x_{1}$ (or a corresponding proxy vertex) to the other end of $P_{C}$. This completes the construction of the desired Hamiltonian cycle and thereby completes the proof of Lemma 4.$\square$

6 Proof of Lemmas 5 and 6

Recall that Lemmas 5 and 6 say that for a positive integer k, a small $\lambda = \lambda (k) > 0$, and a graph G of order $n \ge n(\lambda )$, if either $\delta (G) \ge \frac{n + k}{2}$ or $\sigma _2(G) \ge n + 2k - 2$, and $\alpha (G) \ge (\frac{1}{2} - \lambda )n$, then the conclusions of Theorems 5 and 6 hold respectively.

Proof

Let A be a maximum independent set of G, and let $B = V(G) \setminus A$. By the assumptions on $\sigma _2(G)$ or $\delta (G)$, we have $|B| \ge \frac{n + k}{2}$. This implies that

$$\begin{aligned} \left( \frac{1}{2} - \lambda \right) n \le |A| \le \frac{n - k}{2} \end{aligned}$$

and

$$\begin{aligned} \frac{n + k}{2} \le |B| \le \left( \frac{1}{2} + \lambda \right) n. \end{aligned}$$

$\square$

Claim 3

Let $B'$ be the set of vertices in B each with at least $( \frac{1}{2} - \frac{1}{16k} ) n$ edges to A. Then $|B'| \ge \frac{n}{2}(1 - 16k\lambda )$.

Proof

Each vertex in A (except possibly one if we are using the degree sum condition) has at least $\frac{n + k}{2}$ neighbors in B, which means there are at least $(|A|-1)\cdot \frac{n + k}{2}$ edges between A and B. On the other hand, there are fewer than $|B'||A| + \left( |B \setminus B'| \right) ( \frac{1}{2} - \frac{1}{16k} ) n$ edges out of B. Since $|A| \ge (\frac{1}{2} - \lambda ) n$ and $|B| \le ( \frac{1}{2} + \lambda ) n$, we get

$$\begin{aligned}&|B'| \left( \frac{1}{2} - \lambda \right) n + \left( \left( \frac{1}{2} + \lambda \right) n - |B'| \right) \left( \frac{1}{2} - \frac{1}{16k}\right) n\\&\quad \ge \left( \left( \frac{1}{2} - \lambda \right) n - 1\right) \frac{1}{2}(n + k - 1), \end{aligned}$$

which gives us

$$\begin{aligned}&|B'|n \left( \frac{1}{16k} - \lambda \right) + n^{2} \left( \lambda - \frac{1}{32k} - \frac{\lambda }{16k} \right) \\&\quad \ge n \left( \frac{k}{4} + \frac{\lambda }{2} - \frac{\lambda k}{2} - \frac{3}{4} \right) - \frac{k}{2} + \frac{1}{2}. \end{aligned}$$

This implies that

$$\begin{aligned} \frac{|B'|}{16k} \ge n \left( \frac{1}{32k} + \frac{\lambda }{16k} - \lambda \right) \end{aligned}$$

which means that $|B'| \ge \frac{n}{2}(1 - 16k\lambda )$ as desired.$\square$

A bipartite graph $U\cup V$ is said to be bipanconnected if for every pair of vertices $x,y\in U\cup V$, there exist (x, y)-paths of all possible lengths at least dist(x, t) of appropriate parity in $U\cup V$. That is, for every pair of vertices $x\in U$ and $y\in V$, there exist (x, y)-paths of every possible odd length at least dist(x, y), and for every pair of vertices $x,y\in U$ (and V), there exist (x, y)-paths of every even length at least dist(x, y). Also observe that the sets U and V need not be balanced, so the longest possible length is only $2\min \{ |U|, |V| \}$.

Lemma 10

(Coll et al. [2]) If $G[U \cup V]$ is a balanced bipartite graph of order 2m with $\delta (G[U \cup V]) \ge \frac{3m}{4}$, then $G[U \cup V]$ is bipanconnected.

Our next claim shows that any reasonably large subsets of $B'$ induce bipanconnected subgraphs when paired with any corresponding subset of A.

Claim 4

For all $m \ge \frac{n}{4k}$, if $U\subseteq A$ and $V\subseteq B'$ with $|U|, |V| \ge m$, then $U \cup V$ induces a bipanconnected subgraph of G.

Proof of Claim 4 For $m \ge \frac{n}{4k}$, let U and V be subsets of A and $B'$ respectively with $|U|, |V| \ge m$. Each vertex in U has at least $|V| - 2\lambda n > \frac{3|V|}{4}$ neighbors in V. Each vertex in $B'$ misses at most $\frac{n}{16k}$ vertices in A so each vertex in V has degree at least $|U| - \frac{n}{16k} \ge \frac{3|U|}{4}$ into U. It follows from Lemma 10 (simply removing vertices from the larger set if the sets are not balanced) that $G[U \cup V]$ is bipanconnected.$\square$

Let $D = B \setminus B'$ so

$$\begin{aligned} |D|\le & {} \max \{ |B| \} - \min \{ |B'|\}\\= & {} \left( \frac{1}{2} + \lambda \right) n - \frac{n}{2} (1 - 16k\lambda )\\= & {} (16k + 1) \lambda n. \end{aligned}$$

Let M be a maximum matching between D and A and let $D'$ be the vertices of D that are not covered by edges of M. In particular, vertices in $D'$ must have many edges to B, and therefore behave as if they are in A in the sense that they have almost all possible edges to $B'$. Let $\tau$ be the minimum number of edges in $B \setminus D'$ that must necessarily be used in order to ensure all path segments of the desired Hamiltonian cycle can be constructed as desired. Without concern for the placement of or specified vertices, $\tau$ would be $|B \setminus D'| - |A \cup D'|$. In order to obtain the correct distances between specified vertices, we must also consider the parity of the desired paths. More precisely, if we let o(S) denote the number of desired path segments that must start and end at vertices in the set S, then we get

$$\begin{aligned} \tau = |B \setminus D'| - |A \cup D'| - o(B \setminus D') + o(A \cup D'). \end{aligned}$$

By definition, there are no edges from $D'$ to $A \setminus V(M)$. This means that if we pick two vertices u and v in $A \setminus V(M)$, we get $d(u) + d(v) \le 2|B \setminus D'|$ but when we assume $\sigma _{2}(G) \ge n + 2k - 2$, this means

$$\begin{aligned} |B| - |A| - 2k + 2 \ge 2|D'|, \end{aligned}$$

which implies that $\tau \ge k - 2 > 0$. When we are assuming $\delta (G) \ge \frac{n + k}{2}$, we know that $deg(u) \le |B \setminus D'|$ so

$$\begin{aligned} |B| + |A| + k \le 2|B \setminus D'|, \end{aligned}$$

which implies that $\tau \ge 0$.

Let $D^{*}$ denote those vertices in $D \setminus D'$ that can be covered by a path (or a set of at most k paths if vertices of X are involved) that starts in A and ends in $B'$ and uses an equal number of vertices from $B \setminus D'$ and $A \cup D'$. Choose such a path (or set of paths) that uses the smallest number of vertices outside D. Let $D_{0}$ be the remaining vertices in $D \setminus (D' \cup D^{*})$. If we choose a vertex $u \in A$ with no neighbors to $D_{0} \cup D'$ (note that such a vertex must exist by the definitions of these sets) and $v \in D_{0}$, we get

$$\begin{aligned} n + k \le deg(u) + deg(v) \le |B \setminus (D' \cup D_{0})| + |B \setminus D'| - 1 \end{aligned}$$

which reduces down to $|D_{0}| \le \tau$. Thus, we may assume that $\tau$ is rather large and it suffices to show that we are always able to use $\tau$ edges within B in constructing the desired path segments.

By definition, each vertex of $D \setminus D'$ can use either 1 or 2 edges within B in constructions. If $\tau$ is larger than $|D \setminus D'|$, the degree sum condition, applied to vertices in B, provides many edges within B, easily enough to find $\tau$ edges that can be used. Finally, applying Claim 4, we may construct each desired path starting at the corresponding selected vertex, with the prescribed length. We construct these paths in order from shortest to longest so that, when constructing the final path (of desired order at least $\frac{n}{k}$), there will certainly be enough vertices remaining to apply Claim 4. This completes the proofs of Lemmas 5 and 6. $\square$

7 Proof of Lemmas 7 and 8

Assume $\sigma _{2}(G) \ge n + 2k - 2$. We begin with a result ensuring that low connectivity in the reduced graph R results in at most two components after removal of a minimum cut set, which is an easy corollary of the corresponding lemma in [3].

Corollary 11

Let $\epsilon ,d > 0$ be small real numbers and k be a positive integer. If G is a graph with $\sigma _2(G) \ge n+2k-2$ and reduced graph R with connectivity at most 1, then R consists of only two components after removal of a minimum cut set.

Fact 5

Given small real numbers $\epsilon , d > 0$ and a positive integer k, let G be a graph of order $n = \sum _{i=1}^k n_i \ge n(\epsilon ,d,k)$ with $\sigma _2(G) \ge n+2k-2$ and $\delta (G) \ge \frac{n_k}{8}$. Let $G'$ be the subgraph of G from Lemma 1 and let $E'$ be the set of edges that were removed from G to obtain $G'$. We replace the smallest matching M possible (from $E'$ back into $G'$) to recover the condition that $\kappa (G') \ge 2k$. Since the reduced R graph of $G'$ is assumed to have connectivity at most 1, let $D\subset V(G')$ be the cluster corresponding to a cut vertex of R. (If R contains no cut vertices, then $D=\emptyset$.) Let $V_0$ be the garbage cluster of $G'$ resulting from Lemma 1, and let C be a minimum cut set of $G'$. By Lemma 1, each vertex of R corresponds to a cluster in $G'$ of order $L \le \epsilon n$. Since there is a cut set $C^{*}$ with $C^{*} \subseteq D\cup V_0 \cup V(M)$, we have $2k \le |C| \le |D| + |V_0| + 2k \le 3 \epsilon n$. By Corollary 11, we may define A and B to be the two components of $G'\setminus C$ and write $G'=A\cup C\cup B$. It immediately follows from $\sigma _2(G)\ge n+2k-2$ that $\sigma _{2}(G') \ge n + 2k - 2 - 2(d + 3\epsilon ) n$ and

$$\begin{aligned} \delta (G'[A])> & {} |A|-|C| - 2(d + 3\epsilon ) n \ge |A| - 2(d + 4\epsilon ) n, \nonumber \\ \delta (G'[B])> & {} |B|-|C| - 2(d + 3\epsilon ) n \ge |B| - 2(d + 4\epsilon ) n. \end{aligned}$$

(1)

From the assumption that $\delta (G) \ge \frac{n_k}{8} \ge \frac{n}{2k}$ (Lemma 4), we know $|A|,|B| \ge \frac{n_k}{8} - |C| - 2(d + 3\epsilon ) n > \frac{n}{8(k+1)}$.

While panconnected sets give paths of arbitrary length, only the endpoints are specified. Hence, to create disjoint paths of arbitrary length, we must create sets using vertices that are not part of an already existing desired path. Fortunately, even small subsets of A and B induce panconnected graphs.

Lemma 11

Let $\epsilon$, d, k, and $G'=A\cup C\cup B$ be defined as in Fact 5. Then the induced graph on any subgraph of A or B of order at least $4(d + 4\epsilon ) n$ is panconnected.

Proof

We see from (1) that $\delta (G'[A]) > |A| - 2(d + 4\epsilon ) n$. Then for all $U\subseteq A$ of order at least $4(d + 4\epsilon ) n$, we have

$$\begin{aligned} \delta (G'[U])\ge & {} |U|-2(d + 4\epsilon ) n+1 \\\ge & {} \frac{|U|+2}{2}. \end{aligned}$$

By Theorem 10, the graph $G'[U]$ is panconnected. A symmetric argument shows that if $U\subseteq B$ has order at least $4(d + 4 \epsilon ) n$, then $G'[U]$ is panconnected.$\square$

With this information, we prove the following lemma which completes the proof of Lemma 8.

Lemma 12

Given small real numbers $\epsilon , d > 0$ and a positive integer k, let G be a graph of order $n = \sum _{i=1}^k n_i \ge n(\epsilon ,d,k)$ with $\sigma _2(G) \ge n+2k-2$ and $\delta (G) \ge \frac{n_k}{8}$. If $\kappa (R) \le 1$, then the conclusion of Theorem 6 holds.

Proof

Suppose $\kappa (R) \le 1$, and let $G'=A\cup C\cup B$ as in Fact 5. As noted before (1), we know $2k \le |C| \le 3 \epsilon n$. As noted after (1), we know $|A|,|B| > \frac{n}{8(k+1)}$. Since C is a minimum cut set, for each vertex $c\in C$, we may reserve two unique neighbors $a_c\in A \setminus X$ and $b_c\in B \setminus X$. Call $A_C = \{a_c\in A\setminus X \;|\; c\in C\}$ (symmetrically $B_C = \{b_c\in B\setminus X \;|\; c\in C\}$) the set of proxy vertices in A (symmetrically B). Then we have

$$\begin{aligned} |C| = |A_C| = |B_C|. \end{aligned}$$

Given vertices x and y, let an x-y -path be a path containing x and y as endpoints. Namely, each desired path $P_i$ in $G'$ is an $x_i$-$x_{i+1}$-path.

Our strategy is as follows, first we suppose that $G'[A]$ and $G'[B]$ are complete and create “shadows” of our desired paths with some simple properties. These shadows represent where we would put our desired paths if $G'[A]$ and $G'[B]$ were really complete. Then we use Lemma 11 to create the desired paths, based on the shadows, in $G'[A]$ and $G'[B]$.

First suppose that $G'[A]$ and $G'[B]$ are complete. If |C| is even, build paths $P_1, P_2, \dots P_k$ (of the Hamiltonian cycle) such that each time a path visits a vertex in C, the path passes from $A \setminus A_C$, to $A_C$, to C, to $B_C$ and then to $B \setminus B_C$ (or the opposite direction) and furthermore, all except at most one path segment of $P_i$ in $G'[A]$ and one path segment of $P_i$ in $G'[B]$ have length 2 for all $1 \le i \le k$. If |C| is odd, we first move one vertex of $C \setminus X \ne \emptyset$ to either A or B (this vertex must have many edges to at least one of A or B) and then create the Hamiltonian cycle as above. Let $P_i^A$ and $P_i^B$ denote the segments $P_i \cap G'[A]$ and $P_i \cap G'[B]$ respectively.

Arrange the set of path segments $\{ P_1^A, \dots P_t^A \}$ of the shadows in nondecreasing order, $|P'_1| \le \dots \le |P'_t|$, and suppose $P'_i$ is a $(v_i,v'_{i})$-path where $v_i, v'_{i} \in A$. By construction we have $2 \le P'_i$ for all $1 \le i \le t$.

Back in the original graph $G'$, our goal is to construct path segments with same lengths and end vertices as $P'_i$ for all $1 \le i \le t$. Since $|A|> \frac{n}{8(k+1)} > 4(d + 4\epsilon ) n$, using Lemma 11, we can build a $v_1$-$v'_1$-path of order $|P'_1|$. We inductively construct the remaining path segments in $G'[A]$ with the following claim. Here we let $A^{*}$ denote the vertices in $A \setminus A_C$ that have not already been used on a path segment.$\square$

Claim 5

After constructing $P'_1, \dots P'_{t-1}$, there are at least $4(d + 4\epsilon ) n$ vertices remaining in $A^{*}$ to apply Lemma 11 and create $P'_t$.

Proof of Claim 5 By construction, at most k paths of $P'_i$ have length greater than 2. Thus, we get $|P'_t| \ge \frac{|A|-2(t-k)}{k}$. Also, $t \le |C| + k$ because each path segment in A connects two vertices in $X \cup A_{C}$. Therefore, $|P'_t| \ge \frac{|A|-2(|C|)}{k}$ and since $A \ge \frac{n}{8(k+1)}$, we have $\frac{|A|-2(|C|)}{k} \ge \frac{n}{8k(k+1)} - \frac{2(|C|)}{k} > 4(d + 4\epsilon ) n$ as desired.$\square$

By Claim 5, we can create all desired paths in $G'[A]$ based on their shadows. Similarly, we can create the desired paths in $G'[B]$. Using corresponding vertices of C to connect the constructed paths yields the desired Hamiltonian cycle.

By same argument as proof of Lemma 8 we can prove Lemma 7. The only additional case occurs when $\kappa (G) < 2k$. In this case, the sets A and B are almost complete and we can create the desired Hamiltonian cycle trivially using Lemma 11 and an analogue to Lemma 12 within A and B.