Hamiltonian paths passing through matchings in hypercubes with faulty edges

1.   Introduction

Define $[n]$ as the set $\{1, 2, \ldots, n\}$. An $n$-$dimensional$ $hypercube$ $Q_n$ is a graph with vertex set $V(Q_n) = \{v: v = v^1\cdots v^n$ and $v^i\in\{0, 1\}$ for every $i\in[n]\}$ and edge set $E(Q_n) = \{uv\mid|D(u, v)| = 1\}$, where $D(u, v) = \{i\in[n]\mid u^i\neq v^i\}$.

One of the most popular and efficient interconnection networks is the hypercube $Q_n$. It is widely recognized for being Hamiltonian for every $n\geq2$ ^[12]. Havel ^[13] proved that a Hamiltonian path exists in $Q_n$ that connects any two vertices belonging to distinct partite sets. Since then, considerable attention has been given to the research exploring Hamiltonian cycles and paths within hypercubes that exhibit certain additional properties ^{[2,6,7,9,10,11,14,16,19,21,22]}.

The $parity$ $p(u)$ of a vertex $u = u^1\cdots u^n$ in $Q_n$ is defined by $p(u) = \sum_{i = 1}^n u^i$(mod 2). Then, there are $2^{n-1}$ vertices with parity 0 and $2^{n-1}$ vertices with parity 1 in $Q_n$. Observe that $Q_n$ is bipartite and the parity form bipartite sets of $Q_n$. Consequently, $p(u)\neq p(v)$ if, and only if, $d(u, v)$ is odd. First, let us revisit the following well-established result, initially derived by Havel in ^[13].

Theorem 1.1. ^[13] Let $x, y\in V(Q_n)$ be such that $p(x)\neq p(y)$. Then, there exists a Hamiltonian path joining $x$ and $y$ in $Q_n$.

A forest is deemed linear whenever each of its components is a path. Dvořák ^[7,8] investigated the problem of Hamiltonian cycles or Hamiltonian paths in hypercubes with given edges and obtained the following results.

Theorem 1.2. ^[7] For $n\geq2$, let $P\subseteq E(Q_n)$ be such that $|P|\leq2n-3$. Then, there exists a Hamiltonian cycle of $Q_n$ containing $P$ if, and only if, the induced subgraph of $P$ is a linear forest.

Theorem 1.3. ^[8] For $n\geq2$, let $P\subseteq E(Q_n)$ be such that $|P|\leq2n-4$. Let $x, y\in V(Q_n)$ be such that $p(x)\neq p(y)$. If (1) the induced subgraph of $P$ is a linear forest, and (2) the induced subgraph of $P$ does not contain any path joining $x$ and $y$, and neither $x$ nor $y$ is incident with more than one edge of $P$, then there exists a Hamiltonian path joining $x$ and $y$ passing through $P$ in $Q_n$, except the case when $n\in\{3, 4\}$, $d(x, y) = 3$, and $P$ consists of $2n$$-$$4$ edges, all of which are of the same dimension and have a pair-wise distance of $2$, and each of $x$, $y$ is incident with one edge of $P$.

Let $P\subseteq E(Q_n)$ and $x, y\in V(Q_n)$ satisfying $p(x)\neq p(y)$. We say that $\{x, y, P\}$ is compatible if $\{x, y, P\}$ satisfies the conditions $(1)$ and $(2)$ in Theorem 1.3.

A faulty edge implies a forbidden edge, which refers to an edge that cannot be traversed when searching for a Hamiltonian cycle or path structure. In ^[17], Tsai considered the existence of Hamiltonian paths in hypercubes with faulty edges.

Theorem 1.4. ^[17] For $n\geq3$, let $x, y\in V(Q_n)$ and $F\subseteq E(Q_n)$ be such that $p(x)\neq p(y)$ and $|F|\leq2n-5$. If all vertices in $Q_n-F$ have a degree of at least $2$, then there exists a Hamiltonian path joining $x$ and $y$ in $Q_n-F$.

It is natural to draw the following conclusion from Theorem 1.4.

Corollary 1.5. ^[17] For $n\geq3$, let $F\subseteq E(Q_n)$ with $|F|\leq2n-5$. If all vertices in $Q_n-F$ have a degree of at least $2$, then there exists a Hamiltonian cycle in $Q_n-F$.

Chen ^[5] explored the problem of Hamiltonian cycles containing matchings and avoiding some edges in an $n$-cube $Q_n$ and obtained the following result.

Theorem 1.6. ^[5] Let $n\geq3$, $M\subseteq E(Q_n)$, and $F\subseteq E(Q_n)\setminus M$ with $1\leq|M|\leq2n-4-|F|$. If $M$ is a matching and all vertices in $Q_n-F$ have a degree of at least $2$, then there exists a Hamiltonian cycle containing $M$ in $Q_n-F$.

In ^[5], Chen pointed out that if $|M| = 1$ or $|M| = 2$, then the upper bound of the number of faulty edges tolerated is sharp.

In this paper, we investigate the existence of a Hamiltonian path in $Q_n$ passing through a matching and avoiding faulty edges.

Let $M$ be a matching of $Q_n$ $($$n\geq4$$)$, and let $F$ be a set of edges in $Q_n-M$ such that $|M\cup F|\leq2n-6$ and all vertices in $Q_n-F$ have a degree of at least $2$. Let $x, y\in V(Q_n)$ be such that $p(x)\neq p(y)$ and $xy\notin M$. We show that the following results hold:

(1) If there exist two neighbors $v$ and $t$ of $x$ $($or $y$$)$ satisfying $d_{Q_n-F}(v) = 2$ and $xt\in M$ $($or $yt\in M$$)$, then there exists no Hamiltonian path joining $x$ and $y$ passing through $M$ in $Q_n-F$. We denote this deadlock structure by $x/y$$-$$DS$; see Figure 1(1).

(2) If there exists a path $xvuy$ of length 3 satisfying $d_{Q_n-F}(v) = 2$ and $uy\in M$ or $d_{Q_n-F}(u) = 2$ and $xv\in M$, then there exists no Hamiltonian path joining $x$ and $y$ passing through $M$ in $Q_n-F$. We denote this deadlock structure by $(x, y)$$-$$DS$; see Figure 1(2).

(3) If there is neither $x/y$$-$$DS$ nor $(x, y)$$-$$DS$ in $Q_n-F$, then there exists a Hamiltonian path joining $x$ and $y$ passing through $M$ in $Q_n-F$.

2.   Preliminaries and lemmas

The terminology and notation employed in this paper, yet undefined within its scope, are referred in ^[1]. The vertex set and edge set of a graph $G$ are denoted by $V(G)$ and $E(G)$, respectively. In a simple graph $G$, the number of edges incident with a vertex $v$ is referred to as its degree, denoted as $d_{G}(v)$ or simply $d(v)$. The minimum degree of a graph $G$, denoted by $\delta(G)$, is the minimum value of the degrees of all vertices.

Let $H$ and $H'$ denote two subgraphs of a graph $G$, and let $F$ be a subset of $E(G)$. We use $H+H'$ to represent a graph with the vertex set $V(H)\cup V(H')$ and edge set $E(H)\cup E(H')$. We define $H+F$ as the subgraph of $G$ induced by the edge set $E(H)\cup F$. Also, we define $G-F$ as the subgraph of $G$ obtained by removing all edges in $F$ from $G$. Let $S\subseteq V(G)$, and we denote by $G-S$ the subgraph of $G$ obtained by removing all vertices in $S$ and all edges incident with vertices in $S$. When $S = \{s\}$ and $F = \{f\}$, we simply write $G-S$, $G-F$, and $H+F$ as $G-s$, $G-f$, and $H+f$.

The distance of vertices $u$ and $v$ in a graph $G$, denoted by $d_G(u, v)$, is the number of edges in a shortest path joining $u$ and $v$. The distance $d_G(u, xy)$ of a vertex $u$ and an edge $xy$ in a graph $G$ is defined by $d_G(u, xy): = \min\{d_G(u, x), d_G(u, y)\}$, and the distance $d_G(uv, xy)$ of edges $uv$ and $xy$ in a graph $G$ is defined by $d_G(uv, xy): = \min\{d_G(u, xy), d_G(v, xy)\}$.

The dimension $dim(uv)$ of an edge $uv\in E(Q_n)$ is the integer $j$ such that $D(u, v) = \{j\}$. We denote the set of all $j$-dimensional edges in $Q_n$ by $E_j$. For every $j\in[n]$ and $\alpha\in\{0, 1\}$, let $Q_{n-1, j}^{\alpha}$, with the subscripts $j$ being omitted when the context is clear and the $(n-1)$-dimensional sub-cube of $Q_n$ induced by the vertex sets $\{u\in V(Q_n): u^j = \alpha\}$. Thus, $Q_n-E_j = Q_{n-1}^0+Q_{n-1}^1$. We say that $Q_n$ is split into two $(n-1)$-cubes $Q_{n-1}^0$ and $Q_{n-1}^1$ at position $j$. Note that both $Q_{n-1}^0$ and $Q_{n-1}^1$ are isomorphic to $Q_{n-1}$. Given $M\subseteq E(Q_n)$, let $M_{\alpha} = M\cap E(Q_{n-1}^{\alpha})$ and $M_c = M\cap E_j$. Every vertex $u_\alpha\in V(Q_{n-1}^{\alpha})$ has in $Q_{n-1}^{1-\alpha}$ a unique neighbor, denoted by $u_{1-\alpha}$, and for every edge $e_\alpha = u_\alpha v_\alpha\in E(Q_{n-1}^{\alpha})$, $e_{1-\alpha}$ denotes the edge $u_{1-\alpha}v_{1-\alpha}\in E(Q_{n-1}^{1-\alpha})$.

A set of vertex-disjoint paths of a graph $G$ is a spanning $k$-path if it covers all vertices of $G$. For a path $P$ in $G$, we say that $P$ passes through $E$ if $E\subseteq E(P)$. Similarly, if $E\subseteq\bigcup_{i = 1}^{k}E(P_i)$, then $P_1+\cdots+P_k$ passes through $E$. We use $P_{xy}$ to denote a path joining vertices $x$ and $y$. Let $P_{xy} = x\cdots u\cdots v\cdots y$, and the sub-path $u\cdots v$ of $P_{xy}$ is denoted by $P_{xy}[u, v]$.

Next, we present some lemmas.

Lemma 2.1. ^[18] For $n\geq2$, let $e$ and $f$ be two disjoint edges in $Q_n$. Then, $Q_n$ can be split into two $(n-1)$-cubes such that one contains $e$ and the other contains $f$.

Lemma 2.2. ^[7] For $n\geq2$, let $x, y\in V(Q_n)$ and $e\in E(Q_n)$ be such that $p(x)\neq p(y)$ and $e\neq xy$. Then, there exists a Hamiltonian path joining $x$ and $y$ passing through $e$ in $Q_n$.

Theorem 2.3. ^[23] For $n\geq2$, let $F\subseteq E(Q_n)$ and $L\subseteq E(Q_n)\setminus F$ be such that $|L|+|F|\leq n-2$. Let $x, y\in V(Q_n)$ be such that $p(x)\neq p(y)$. If $\{x, y, L\}$ is compatible, then there exists a Hamiltonian path joining $x$ and $y$ passing through $L$ in $Q_n-F$.

A matching is a special type of a linear forest. Thus, we can easily draw the following corollary.

Corollary 2.4. ^[23] For $n\geq2$, let $M$ be a matching of $Q_n$, and let $F$ be a set of edges in $Q_n-M$ with $|M\cup F|\leq n-2$. Let $x, y\in V(Q_n)$ be such that $p(x)\neq p(y)$ and $xy\notin M$. Then, there exists a Hamiltonian path joining $x$ and $y$ passing through $M$ in $Q_n-F$.

3.   Spanning 2-paths

In this section, we present some conclusions about spanning 2-paths. When the path $P_{vy}$ is an edge $vy$, we abbreviate $P_{ux}+P_{vy}$ to $P_{ux}+vy$ for simplicity.

Theorem 3.1. ^[7] For $n\geq2$, let $x, y, u, v\in V(Q_n)$ be pair-wise distinct vertices such that $p(x)\neq p(y)$ and $p(u)\neq p(v)$. Then, $(i)$ there exists a spanning 2-path $P_{xy}+P_{uv}$ in $Q_n$; $(ii)$ moreover, in the case when $d(u, v) = 1$, path $P_{uv}$ can be chosen such that $P_{uv} = uv$, unless $n = 3$, $d(x, y) = 1$, and $d(xy, uv) = 2$.

Theorem 3.2. ^[3] For $n\geq4$, let $x, y, u, v\in V(Q_n)$ be pair-wise distinct vertices such that $p(x) = p(y)\neq p(u) = p(v)$. Then, there exists a spanning 2-path $P_{xy}+P_{uv}$ in $Q_n$.

Theorem 3.3. ^[15] For $n\geq2$, let $x, y, u\in V(Q_n)$ be pair-wise distinct vertices such that $p(x) = p(y)\neq p(u)$. Then, there exists a Hamiltonian path joining $x$ and $y$ in $Q_n-u$.

When $u = v$, the notation $P_{uv}$ denotes the path of a single vertex $u$. Thus, in Theorem 3.2, when $u = v$, the conclusion still holds.

Corollary 3.4. ^[3,15] For $n\geq4$, let $x, y, u, v\in V(Q_n)$ be such that $x\neq y$ and $p(x) = p(y)\neq p(u) = p(v)$. Then, there exists a spanning 2-path $P_{xy}+P_{uv}$ in $Q_n$.

A set $\{u_1, u_2, \ldots, u_{2k-1}, u_{2k}\}$ of distinct vertices of $Q_n$ is balanced if the number of odd vertices equals to the number of even vertices.

Lemma 3.5. ^[4] For $n\geq4$, let $\{x, y, u, v\}$ be a balanced vertex set in $Q_n$ and $F\subseteq E(Q_n)$ with $|F|\leq1$. Then, there exists a spanning 2-path $P_{xy}+P_{uv}$ in $Q_n-F$.

Theorem 3.6. ^[4] For $n\geq4$, let $F\subseteq E(Q_n)$ be such that $|F|\leq2n-7$ and the degree of every vertex in $Q_n-F$ is at least 3. Assume that $\{u, x, v, y\}$ is a balanced vertex set in $Q_n$. Then, there exists a spanning 2-path $P_{ux}+P_{vy}$ in $Q_n-F$.

Lemma 3.7. ^[20] Let $ux$ and $vy$ be two disjoint edges in $Q_4$ and $e\in E(Q_4)$. If $\{u, v\}\cap V(e) = \emptyset$ and $xy\neq e$, then there exists a spanning 2-path $P_{ux}+P_{vy}$ passing through $e$ in $Q_4$.

Lemma 3.8. For $n\geq4$, let $M$ be a matching of $Q_n$, and let $F$ be a set of edges in $Q_n-M$ with $|M\cup F|\leq n-3$. Let $ux, vy$ be two disjoint edges in $Q_n$ such that $\{u, v\}\cap V(M) = \emptyset$ and $xy\notin M$. Then, there exists a spanning 2-path $P_{ux}+P_{vy}$ passing through $M$ in $Q_n-F$.

Proof. We prove the conclusion by induction on $n$. When $n = 4$, we have $|M\cup F|\leq1$. By Lemma 3.5 when $|M| = 0$ and Lemma 3.7 when $|M| = 1$, there exists a spanning 2-path $P_{ux}+P_{vy}$ passing through $M$ in $Q_4-F$. Assume that the conclusion holds for $n\geq4$, and we are to show that it holds for $n+1$. Now, $|M\cup F|\leq (n+1)-3 = n-2$.

Select $j\in[n+1]\setminus(D(u, x)\cup D(v, y))$ such that $|(M\cup F)\cap E_j| = 0$. Split $Q_{n+1}$ into $Q_n^0$ and $Q_n^1$ at position $j$. Without loss of generality, assume that $ux\in E(Q_n^0)$. Let $M_{\alpha} = M\cap E(Q_n^{\alpha})$ and $F_{\alpha} = F\cap E(Q_n^{\alpha})$ for $\alpha\in\{0, 1\}$.

When $vy\in E(Q_n^1)$, we have $|M_0\cup F_0|\leq n-2$ and $|M_1\cup F_1|\leq n-2$. By Corollary 2.4, there exist Hamiltonian paths $P_{ux}$ and $P_{vy}$ passing through $M_0$ and $M_1$ in $Q_n^0-F_0$ and $Q_n^1-F_1$, respectively. Hence, $P_{ux}+P_{vy}$ is the desired spanning 2-path. So, we only need to consider the case that $vy\in E(Q_n^0)$.

Case 1. $|M_0\cup F_0|\leq n-3$.

By induction hypothesis, there exists a spanning 2-path $P_{ux}^0+P_{vy}^0$ passing through $M_0$ in $Q_n^0-F_0$. Choose an edge $r_0w_0\in E(P_{ux}^0+P_{vy}^0)\setminus M_0$ satisfying $\{r_1, w_1\}\cap V(M_1) = \emptyset$. Since $|E(P_{ux}^0+P_{vy}^0)\setminus M_0|-4|M_1| = |E(P_{ux}^0+P_{vy}^0)|-(|M_0|+4|M_1|)\geq(2^n-2)-4(n-2) = 2^n-4n+6 > 1$ for $n\geq4$, such an edge $r_0w_0$ exists. Without loss of generality, assume that $r_0w_0\in E(P_{ux}^0)$. Since $M_1\cup\{r_1w_1\}$ is a matching and $|(M_1\cup\{r_1w_1\})\cup F_1|\leq n-1 < 2n-4$ for $n\geq4$, by Theorem 1.6 there exists a Hamiltonian cycle $C_1$ containing $M_1\cup\{r_1w_1\}$ in $Q_n^1-F_1$. Let $P_{ux} = P_{ux}^0+C_1+\{r_0r_1, w_0w_1\}-\{r_0w_0, r_1w_1\}$ and $P_{vy} = P_{vy}^0$. Hence, $P_{ux}+P_{vy}$ is a spanning 2-path passing through $M$ in $Q_{n+1}-F$.

Case 2. $|M_0\cup F_0| = n-2$. Now, $|M_1| = |F_1| = 0$.

When $|F_0|\geq1$, choose an edge $r_0w_0\in F_0$. Since $|M_0\cup (F_0\setminus\{r_0w_0\})| = n-3$, by induction hypothesis there exists a spanning 2-path $P_{ux}^0+P_{vy}^0$ passing through $M_0$ in $Q_n^0-(F_0\setminus\{r_0w_0\})$. If $r_0w_0\notin E(P_{ux}^0+P_{vy}^0)$, then choose an edge $s_0t_0\in E(P_{ux}^0+P_{vy}^0)\setminus M_0$. If $r_0w_0\in E(P_{ux}^0+P_{vy}^0)$, then let $s_0t_0 = r_0w_0$. In the above two cases, without loss of generality, assume that $s_0t_0\in E(P_{ux}^0)$. In $Q_n^1$, by Theorem 1.1, there exists a Hamiltonian path $P_{s_1t_1}^1$. Let $P_{ux} = P_{ux}^0+P_{s_1t_1}^1+\{s_0s_1, t_0t_1\}-s_0t_0$ and $P_{vy} = P_{vy}^0$. Hence, $P_{ux}+P_{vy}$ is a spanning 2-path passing through $M$ in $Q_{n+1}-F$.

When $|F_0| = 0$, now $|M_0| = n-2$. Since $M_0\cup\{ux, vy\}$ is a linear forest with $|M_0\cup\{ux, vy\}| = n < 2n-3$ for $n\geq4$, by Theorem 1.2 there exists a Hamiltonian cycle $C_0$ containing $M_0\cup\{ux, vy\}$ in $Q_n^0$. Note that $C_0-ux-vy$ consists of two paths, having endpoints $u$ and $x$, respectively. We denote them by $P_u$ and $P_x$. Since $\{u, v\}\cap V(M) = \emptyset$ and $xy\notin M$, we can choose two edges $r_0w_0\in E(P_u)\setminus M_0$ and $s_0t_0\in E(P_x)\setminus M_0$. Without loss of generality, assume that $r_0$ is closer to $u$ than $w_0$ on $P_u$ and $s_0$ is closer to $x$ than $t_0$ on $P_x$. In $Q_n^1$, by Theorems 3.1 and 3.2, there exists a spanning 2-path $P_{r_1s_1}^1+P_{w_1t_1}^1$. Hence, $P_{ux}+P_{vy} = C_0+P_{r_1s_1}^1+P_{w_1t_1}^1+\{r_0r_1, w_0w_1, s_0s_1, t_0t_1\}-\{ux, vy, r_0w_0, s_0t_0\}$ is the desired spanning 2-path. □

Lemma 3.9. For $n\geq4$, let $ux, vy$ be two disjoint edges in $Q_n$, and let $f\in E(Q_n)$ with $vy\neq f$, then there exists a spanning 2-path $P_{ux}+vy$ in $Q_n-f$.

Proof. By Lemma 2.1, we can split $Q_n$ into $Q_{n-1}^0$ and $Q_{n-1}^1$ such that $ux\in E(Q_{n-1}^0)$ and $vy\in E(Q_{n-1}^1)$. Next, we distinguish two cases to consider.

If $f\notin E(Q_{n-1}^1)$, then by Theorem 1.4 there exists a Hamiltonian path $P_{ux}^0$ in $Q_{n-1}^0-f$. Choose an edge $s_0t_0\in E(P_{ux}^0)$ such that $f\notin\{s_0s_1, t_0t_1\}$ and $d(s_1t_1, vy)\neq2$ when $n = 4$. By Theorem 3.1 there exists a spanning 2-path $P_{s_1t_1}^1+vy$ in $Q_{n-1}^1$. Let $P_{ux} = P_{ux}^0+P_{s_1t_1}^1+\{s_0s_1, t_0t_1\}-s_0t_0$. Hence, $P_{ux}+vy$ is a spanning 2-path in $Q_n-f$.

If $f\in E(Q_{n-1}^1)$, then by Theorem 1.4 there exists a Hamiltonian path $P_{vy}^1$ in $Q_{n-1}^1-f$. Choose two neighbors $r_1, w_1$ of $v, y$ on $P_{vy}^1$. If $r_0w_0\neq ux$, then by Lemma 2.2 there exists a Hamiltonian path $P_{r_0w_0}^0$ passing through $ux$ in $Q_{n-1}^0$. Let $P_{ux} = P_{r_0w_0}^0+P_{vy}^1[r_1, w_1]+\{r_0r_1, w_0w_1\}-ux$. Hence, $P_{ux}+vy$ is the desired spanning 2-path. If $r_0w_0 = ux$, then choose an edge $s_1t_1\in E(P_{vy}^1)$ such that $\{s_0, t_0\}\cap\{r_0, w_0\} = \emptyset$ and $d(s_0t_0, r_0w_0)\neq2$ when $n = 4$. Since $|E(P_{vy}^1)|-4-1 > 1$ for $n\geq4$, such an edge $s_1t_1$ exists. In $Q_{n-1}^0$, by Theorem 3.1 there exists a spanning 2-path $P_{s_0t_0}^0+ux$. Let $P_{ux} = P_{s_0t_0}^0+P_{vy}^1[r_1, w_1]+\{uu_1, xx_1, s_0s_1, t_0t_1\}-s_1t_1$. Hence, $P_{ux}+vy$ is the desired spanning 2-path. □

Lemma 3.10. ^[20] For $n\geq5$, let $uv$ and $e$ be two disjoint edges in $Q_n$, and let $x, y\in V(Q_n)\setminus\{u, v\}$ be such that $p(x)\neq p(y)$ and $xy\neq e$. Then, there exists a spanning 2-path $P_{xy}+uv$ passing through $e$ in $Q_n$.

Lemma 3.11. For $n\geq4$, let $uv$ and $e$ be two disjoint edges in $Q_n$, and let $x, y\in V(Q_n)\setminus\{u, v\}$ be such that $p(x)\neq p(y)$ and $xy\neq e$. Then, there exists a spanning 2-path $P_{xy}+uv$ passing through $e$ in $Q_n$.

Proof. When $n\geq5$, the conclusion holds by Lemma 3.10. So, we only need to consider the case that $n = 4$. By Lemma 2.1, we can split $Q_4$ into $Q_3^0$ and $Q_3^1$ such that $e\in E(Q_3^0)$ and $uv\in E(Q_3^1)$.

Case 1. $x, y\in V(Q_3^0)$.

By Lemma 2.2, there exists a Hamiltonian path $P_{xy}^0$ passing through $e$ in $Q_3^0$. Choose an edge $s_0t_0\in E(P_{xy}^0)\setminus\{e\}$ such that $\{s_1, t_1\}\cap\{u, v\} = \emptyset$ and $d(uv, s_1t_1)\neq2$. Since $|E(P_{xy}^0)\setminus\{e\}|-4-1 = 1$, such an edge $s_0t_0$ exists. In $Q_3^1$, by Theorem 3.1 there exists a spanning 2-path $P_{s_1t_1}^1+uv$. Let $P_{xy} = P_{xy}^0+P_{s_1t_1}^1+\{s_0s_1, t_0t_1\}-s_0t_0$. Hence, $P_{xy}+uv$ is a spanning 2-path passing through $e$ in $Q_4$.

Case 2. $x\in V(Q_3^0)$, $y\in V(Q_3^1)$ (or $x\in V(Q_3^1)$, $y\in V(Q_3^0)$).

Since $2^2 > 2$, we can choose a vertex $t_0\in V(Q_3^0)$ such that $p(t_0)\neq p(x)$, $t_1\notin\{u, v\}$, and $d(t_1y, uv)\neq2$. In $Q_3^0$, by Lemma 2.2 there exists a Hamiltonian path $P_{xt_0}^0$ passing through $e$. In $Q_3^1$, by Theorem 3.1 there exists a spanning 2-path $P_{t_1y}^1+uv$. Let $P_{xy} = P_{xt_0}^0+P_{t_1y}^1+t_0t_1$. Hence, $P_{xy}+uv$ is the desired spanning 2-path.

Case 3. $x, y\in V(Q_3^1)$.

By Lemma 2.2 there exists a Hamiltonian path $P_{xy}^1$ passing through $uv$ in $Q_3^1$. Without loss of generality, assume that $u$ is closer to $x$ than $v$ on $P_{xy}^0$. Choose two neighbors $r_1, w_1$ of $u, v$ on $P_{xy}^1[x, u]$ and $P_{xy}^1[y, v]$, respectively. If $r_0w_0\neq e$, then by Lemma 2.2 there exists a Hamiltonian path $P_{r_0w_0}^0$ passing through $e$ in $Q_3^0$. Let $P_{xy} = P_{xy}^1[x, r_1]+P_{xy}^1[y, w_1]+P_{r_0w_0}^0+\{r_0r_1, w_0w_1\}$. Hence, $P_{xy}+uv$ is the desired spanning 2-path. If $r_0w_0 = e$, then choose an edge $s_1t_1\in E(P_{xy}^1)\setminus\{uv\}$ such that $\{s_0, t_0\}\cap\{r_0, w_0\} = \emptyset$ and $d(s_0t_0, r_0w_0)\neq2$. Since $|E(P_{xy}^1)\setminus\{uv\}|-4-1 = 1$, such an edge $s_1t_1$ exists. In $Q_3^0$, by Theorem 3.1 there exists a spanning 2-path $P_{s_0t_0}^0+e$. Let $P_{xy} = P_{xy}^1[x, r_1]+P_{xy}^1[y, w_1]+P_{s_0t_0}^0+e+\{r_0r_1, w_0w_1, s_0s_1, t_0t_1\}-s_1t_1$. Hence, $P_{xy}+uv$ is the desired spanning 2-path. □

Lemma 3.12. For $n\geq4$, let $swrys$ be a cycle of length four in $Q_n$. Let $M$ be a matching of $Q_n$, and let $F$ be a set of edges in $Q_n-M$ such that $\{s, w, r, y\}\cap V(M) = \emptyset$, $ry\notin F$, and $|M\cup F|\leq n-3$. Then, there exists a spanning 2-path $P_{sw}+ry$ passing through $M$ in $Q_n-F$.

Proof. Since $swrys$ is a cycle of length four, then $dim(sw) = dim(ry)$ and $dim(rw) = dim(sy)$. We prove the conclusion by induction on $n$. When $n = 4$, we have $|M\cup F|\leq1$. Thus, the conclusion holds by Theorem 3.1 when $|M\cup F| = 0$, Lemma 3.9 when $|F| = 1$, and Lemma 3.11 when $|M| = 1$. Assume that the conclusion holds for $n\geq4$, and we are to show that it holds for $n+1$. Now, $|M\cup F|\leq(n+1)-3 = n-2$.

Since $n+1 > n-2+2$, we can select $j\in[n+1]\setminus(D(s, w)\cup D(r, w))$ such that $|(M\cup F)\cap E_j| = 0$. Then, $|\{sw, ry, rw, sy\}\cap E_j| = 0$. Split $Q_{n+1}$ into $Q_n^0$ and $Q_n^1$ at position $j$. Without loss of generality, assume that $sw, ry\in E(Q_n^0)$.

Case 1. $|M_0\cup F_0|\leq n-3$.

By induction hypothesis, there exists a spanning 2-path $P_{sw}^0+ry$ passing through $M_0$ in $Q_n^0-F_0$. Choose an edge $u_0v_0\in E(P_{sw}^0)\setminus M_0$ such that $\{u_1, v_1\}\cap V(M_1) = \emptyset$. Since $|E(P_{sw}^0\setminus M_0)|-4|M_1| = |E(P_{sw}^0)|-|M_0|-4|M_1|\geq(2^n-2-1)-4(n-2) = 2^n-4n+5\geq1$ for $n\geq4$, such an edge $u_0v_0$ exists. Since $|(M_1\cup\{u_1v_1\})\cup F_1|\leq n-1 < 2n-4$ for $n\geq4$ and $M_1\cup\{u_1v_1\}$ is a matching, by Theorem 1.6 there exists a Hamiltonian cycle $C_1$ containing $M_1\cup\{u_1v_1\}$ in $Q_n^1-F_1$. Let $P_{sw} = P_{sw}^0+C_1+\{u_0u_1, v_0v_1\}-\{u_0v_0, u_1v_1\}$. Hence, $P_{sw}^0+ry$ is a spanning 2-path passing through $M$ in $Q_{n+1}-F$.

Case 2. $|M_0\cup F_0| = n-2$. Now, $|M_1\cup F_1| = 0$.

When $|M_0|\geq1$, choose an edge $u_0v_0\in M_0$. Since $|(M_0\setminus\{u_0v_0\})\cup F_0| = n-3$, by induction hypothesis there exists a spanning 2-path $P_{sw}^0+ry$ passing through $M_0\setminus\{u_0v_0\}$ in $Q_n^0-F_0$. If $u_0v_0\in E(P_{sw}^0)$, then choose an edge $x_0t_0\in E(P_{sw}^0)\setminus M_0$. In $Q_n^1$, by Theorem 1.1 there exists a Hamiltonian path $P_{x_1t_1}^1$. Let $P_{sw} = P_{sw}^0+P_{x_1t_1}^1+\{x_0x_1, t_0t_1\}-x_0t_0$. Hence, $P_{sw}^0+ry$ is the desired spanning 2-path. If $u_0v_0\notin E(P_{sw}^0)$, then without loss of generality assume that $u_0$ is closer to $s$ than $v_0$ on $P_{sw}^0$. Since $\{s, w\}\cap V(M_0) = \emptyset$, we can choose clockwise neighbors $x_0, t_0$ of $u_0, v_0$ on $P_{sw}^0$. In $Q_n^1$, by Theorem 1.1 there exists a Hamiltonian path $P_{x_1t_1}^1$. Let $P_{sw} = P_{sw}^0+P_{x_1t_1}^1+\{u_0v_0, x_0x_1, t_0t_1\}-\{u_0x_0, v_0t_0\}$. Hence, $P_{sw}^0+ry$ is the desired spanning 2-path.

When $|M_0| = 0$, we have $|F_0| = n-2$. Choose an edge $u_0v_0\in F_0$. Since $|F_0\setminus\{u_0v_0\}| = n-3$, by induction hypothesis there exists a spanning 2-path $P_{sw}^0+ry$ in $Q_n^0-(F_0\setminus\{u_0v_0\})$. If $u_0v_0\notin E(P_{sw}^0)$, then choose an edge $x_0t_0\in E(P_{sw}^0)$. If $u_0v_0\in E(P_{sw}^0)$, then let $u_0v_0 = x_0t_0$. In $Q_n^1$, by Theorem 1.1 there exists a Hamiltonian path $P_{x_1t_1}^1$. Let $P_{sw} = P_{sw}^0+P_{x_1t_1}^1+\{x_0x_1, t_0t_1\}-x_0t_0$. Hence, $P_{sw}^0+ry$ is the desired spanning 2-path. □

4.   Main results

Lemma 4.1. For $n\geq4$, let $M$ be a matching of $Q_n$, and let $F$ be a set of edges in $Q_n-M$ with $|M\cup F|\leq2n-6$. Let $x, y\in V(Q_n)$ be such that $p(x)\neq p(y)$ and $xy\notin M$. If $\delta(Q_n-F) = 2$ and if there is neither $x/y$$-$$DS$ nor $(x, y)$$-$$DS$ in $Q_n-F$, then there exists a Hamiltonian path joining $x$ and $y$ passing through $M$ in $Q_n-F$.

Proof. We prove the conclusion by induction on $n$. When $n = 4$, the conclusion holds by Corollary 2.4. Assume that the conclusion holds for $n\geq4$, and we are to show that it holds for $n+1$. Now, $|M\cup F|\leq2(n+1)-6 = 2n-4$.

When $|M| = 0$, the conclusion holds by Theorem 1.4. So, we only need to consider the case that $|M|\geq1$. Now, $|F|\leq2n-5$. Thus, there is exactly one vertex, denoted by $v$, of degree 2 in $Q_{n+1}-F$, and all the other vertices of $Q_{n+1}-F$ are of degree of at least 4. If there is another vertex of degree 2 or 3 in $Q_{n+1}-F$, then $|F|\geq(n+1-2)+(n+1-3)-1 = 2n-4$. A contradiction occurs.

Let $F_v = \{e\in F$ $|$ $e$ is incident with $v$$\}$. Note that $|F|\geq|F_v| = (n+1)-2 = n-1$. Since $|M|\leq2n-4-|F|\leq n-3 < |F_v|$, there exists a position $j$ such that $F_v\cap E_j\neq\emptyset$ and $M\cap E_j = \emptyset$. Split $Q_{n+1}$ into $Q_n^0$ and $Q_n^1$ at position $j$. We may assume $v\in V(Q_n^0)$, and denote $v$ by $v_0$. Let $M_{\alpha} = M\cap E(Q_n^{\alpha})$ and $F_{\alpha} = F\cap E(Q_n^{\alpha})$ for $\alpha\in\{0, 1\}$, and let $M_c = M\cap E_j$ and $F_c = F\cap E_j$. Hence, $d_{Q_n^0-F_0}(v_0) = 2$, all the other vertices of $Q_n^0-F_0$ are of degree of at least 3, and $\delta(Q_n^1-F_1)\geq3$. Note that $|F_0|\geq n-2$, $|M_0\cup F_0|\leq 2n-5$, and $|M_1\cup F_1|\leq n-3$.

We claim that $Q_n^0$ does not contain $x/y$$-$$DS$ and $(x, y)$$-$$DS$. If not, then $Q_{n+1}$ contains $x/y$$-$$DS$ or $(x, y)$$-$$DS$. A contradiction occurs.

Case 1. $|M_0\cup F_0|\leq 2n-6$.

Sub-case 1.1 $x, y\in V(Q_n^0)$. Note that $|F_c|\leq2n-4-(n-2)-1 = n-3$.

By induction hypothesis, there exists a Hamiltonian path $P_{xy}^0$ passing through $M_0$ in $Q_n^0-F_0$. Choose an edge $s_0t_0\in E(P_{xy}^0)\setminus M_0$ such that $\{s_0s_1, t_0t_1\}\cap F_c = \emptyset$ and $s_1t_1\notin M_1$. Since $|E(P_{xy}^0)\setminus M_0|-|M_1|-2|F_c| = |E(P_{xy}^0)|-(|M_0|+|M_1|+|F_c|)-|F_c|\geq2^n-1-(n-2)-(n-3) = 2^n-2n+4 > 1$ for $n\geq4$, such an edge $s_0t_0$ exists. Since $|M_1\cup F_1|\leq n-3 < n-2$, by Corollary 2.4 there exists a Hamiltonian path $P_{s_1t_1}^1$ passing through $M_1$ in $Q_n^1-F_1$. Hence, $P_{xy} = P_{xy}^0+P_{s_1t_1}^1+\{s_0s_1, t_0t_1\}-s_0t_0$ is a Hamiltonian path joining $x$ and $y$ passing through $M$ in $Q_{n+1}-F$.

Sub-case 1.2. $x\in V(Q_n^0)$, $y\in V(Q_n^1)$ (or $x\in V(Q_n^1)$, $y\in V(Q_n^0)$).

Choose a vertex $z_0$ in $Q_n^0$ such that $p(x)\neq p(z_0)$, $z_0\notin V(M_0)$, $z_0z_1\notin F_c$, $d_{Q_n^0-F_0}(z_0, v_0)\neq1$, and $z_1y\notin M_1$. Since $2^{(n+1)-2}-(|M_0|+|F_c|)-n-1\geq2^{n-1}-(n-2)-n-1 = 2^{n-1}-2n+1\geq1$ for $n\geq4$, such a vertex $z_0$ exists. Note that $Q_n^0$ does not contain $x$$-$$DS$, and there is only one vertex $v_0$ of degree 2 in $Q_n^0-F_0$. If $Q_n^0$ contains $z_0$$-$$DS$, then $z_0\in V(M_0)$ and $d(z_0, v_0) = 1$. If $Q_n^0$ contains $(x, z_0)$$-$$DS$, then $z_0\in V(M_0)$ or $d(z_0, v_0) = 1$. The above two cases both contradict with the choice of $z_0$. Thus, $Q_n^0$ does not contain $x/z_0$$-$$DS$ and $(x, z_0)$$-$$DS$. By induction hypothesis, there exists a Hamiltonian path $P_{xz_0}^0$ passing through $M_0$ in $Q_n^0-F_0$. By Corollary 2.4, there exists a Hamiltonian path $P_{z_1y}^1$ passing through $M_1$ in $Q_n^1-F_1$. Hence, $P_{xy} = P_{xz_0}^0+P_{z_1y}^1+z_0z_1$ is a Hamiltonian path joining $x$ and $y$ passing through $M$ in $Q_{n+1}-F$.

Sub-case 1.3 $x, y\in V(Q_n^1)$.

By Corollary 2.4, there exists a Hamiltonian path $P_{xy}^1$ passing through $M_1$ in $Q_n^1-F_1$. Choose an edge $s_1t_1\in E(P_{xy}^1)\setminus M_1$ such that $\{s_0s_1, t_0t_1\}\cap F_c = \emptyset$ and $\{s_0, t_0\}\cap V(M_0) = \emptyset$. Since $|E(P_{xy}^1)\setminus M_1|-2|F_c|-4|M_0|\geq(2^n-1)-2\times2-4(n-4) = 2^n-4n+11 > 1$ for $n\geq4$, such an edge $s_1t_1$ exists. Since $\{s_0, t_0\}\cap V(M_0) = \emptyset$, we have that $Q_n^0$ does not contain $s_0/t_0$$-$$DS$ and $(s_0, t_0)$$-$$DS$. Hence, by induction hypothesis there exists a Hamiltonian path $P_{s_0t_0}^0$ passing through $M_0$ in $Q_n^0-F_0$. Hence, $P_{xy} = P_{xy}^1+P_{s_0t_0}^0+\{s_0s_1, t_0t_1\}-s_1t_1$ is the desired Hamiltonian path.

Case 2. $|M_0\cup F_0| = 2n-5$. Now, $|F_c| = 1$ and $|M_c| = |M_1| = |F_1| = 0$. Note that $|F_0|\geq n-2$, $1\leq|M_0|\leq n-3$.

Sub-case 2.1 $x, y\in V(Q_n^0)$.

If $|F_0|\geq n-1$, then let $r_0w_0\in F_0\setminus F_v$. Note that $d_{Q_n^0-(F_0\setminus\{r_0w_0\})}(v_0) = 2$ and all the other vertices of $Q_n^0-(F_0\setminus\{r_0w_0\})$ are of degree of at least 3. Since $|M_0\cup(F_0\setminus\{r_0w_0\})| = 2n-6$, by induction hypothesis there exists a Hamiltonian path $P_{xy}^0$ passing through $M_0$ in $Q_n^0-(F_0\setminus\{r_0w_0\})$. If $r_0w_0\notin E(P_{xy}^0)$, then choose an edge $s_0t_0\in E(P_{xy}^0)\setminus M_0$ satisfying $v_0\notin\{s_0, t_0\}$. If $r_0w_0\in E(P_{xy}^0)$, then let $s_0t_0 = r_0w_0$. Since $r_0w_0\notin F_v$, we also have $v_0\notin\{s_0, t_0\}$. In $Q_n^1$, by Theorem 1.1 there exists a Hamiltonian path $P_{s_1t_1}^1$. Hence, $P_{xy} = P_{xy}^0+P_{s_1t_1}^1+\{s_0s_1, t_0t_1\}-s_0t_0$ is the desired Hamiltonian path.

If $|F_0| = n-2$, then $F_0 = F_v\setminus\{v_0v_1\}$. Denote the two edges incident with $v_0$ in $Q_n^0-F_0$ by $u_0v_0$ and $v_0s_0$.

When $v_0\notin\{x, y\}$, first we claim that $\{x, y, M_0\cup\{u_0v_0, v_0s_0\}\}$ is compatible. If $v_0\in V(M_0)$, then let $v_0s_0\in M_0$. Now, $u_0v_0\notin M_0$. There are two possibilities for $u_0$ up to isomorphism; see Figure 2(1)(2). If $v_0\notin V(M_0)$, then there are three possibilities for $\{u_0, s_0\}$ up to isomorphism; see Figure 2(3)-(5). Thus, $M_0\cup\{u_0v_0, v_0s_0\}\}$ is a linear forest. Next, we will verify that $\{x, y, M_0\cup\{u_0v_0, v_0s_0\}\}$ satisfies the condition (2) in Theorem 1.3.

For the case (1) in Figure 2, if $x$ or $y$ is an internal vertex, then $x = v_0$ or $y = v_0$. A contradiction occurs. If $x, y$ are endpoints of a path, then since $p(x)\neq p(y)$, we have $xy\in M_0$. A contradiction occurs. For the case (2) in Figure 2, if $x$ or $y$ is an internal vertex, then since $v_0\notin\{x, y\}$, we have that $x$ or $y$ is the vertex $u_0$. Now, $x$ $($or $y)$ is incident with a matching edge, and $d_{Q_n^0-F_0}(v_0) = 2$. Thus, $Q_n^0$ contains $x/y$$-$$DS$. A contradiction occurs. If $x, y$ are endpoints of a path, then since $xy\notin M_0$, we have that $x, y$ are the two endpoints of the path of length 3 in Figure 2(2). Note that $d_{Q_n^0-F_0}(v_0) = 2$, thus, $Q_n^0$ contains $(x, y)$$-$$DS$. A contradiction occurs. For the case (3) in Figure 2, if $x$ or $y$ is an internal vertex, then since $v_0\notin\{x, y\}$, we have that $x$ $($or $y)$ is $s_0$ or $u_0$. Now, $Q_n^0$ contains $x/y$$-$$DS$. A contradiction occurs. If $x, y$ are endpoints of a path, then $xy\in M_0$. A contradiction occurs. For the case (4) in Figure 2, if $x$ or $y$ is an internal vertex, then since $v_0\notin\{x, y\}$, we have that $x$ $($or $y)$ is the vertex $s_0$ in Figure 2(4). Now, $Q_n^0$ contains $x/y$$-$$DS$. A contradiction occurs. If $x, y$ are endpoints of a path, then since $xy\notin M_0$, we have that $x, y$ are endpoints of the path of length 3 in Figure 2(4). Thus, $Q_n^0$ contains $(x, y)$$-$$DS$. A contradiction occurs. For the case (5) in Figure 2, since $v_0\notin\{x, y\}$, $p(x)\neq p(y)$, and $xy\notin M_0$, we have that $\{x, y, M_0\cup\{u_0v_0, v_0s_0\}\}$ also satisfies the condition (2). In conclusion, $\{x, y, M_0\cup\{u_0v_0, v_0s_0\}\}$ satisfies the condition (2). The claim is proved.

Since $|M_0\cup\{u_0v_0, v_0s_0\}|\leq n-1 < 2n-4$ for $n\geq4$, by Theorem 1.3 there exists a Hamiltonian path $P_{xy}^0$ passing through $M_0\cup\{u_0v_0, v_0s_0\}$ in $Q_n^0$. Note that all faulty edges incident with $v_0$ do not lie on the path $P_{xy}^0$. Thus, we have $E(P_{xy}^0)\cap F_0 = \emptyset$.

When $v_0\in\{x, y\}$, we may assume $v_0 = x$. If $u_0v_0\in M_0$ or $v_0s_0\in M_0$, then without loss of generality assume that $u_0v_0\in M_0$, and now $v_0s_0\notin M_0$. Thus, $M_0\cup\{u_0v_0\} = M_0$ and $\{x, y, M_0\cup\{u_0v_0\}\}$ are compatible. If $u_0v_0\notin M_0$ and $v_0s_0\notin M_0$, then $v_0\notin V(M_0)$. Since $xy\neq u_0v_0$ or $xy\neq v_0s_0$, without loss of generality, assume that $xy\neq u_0v_0$. Thus, $M_0\cup\{u_0v_0\}$ is a linear forest with $d(v_0) = 1$ in it. Since $xy\notin M_0$, $xy\neq u_0v_0$, and $p(x)\neq p(y)$, we have that $\{x, y, M_0\cup\{u_0v_0\}\}$ is compatible. Since $|M_0\cup\{u_0v_0\}|\leq n-2 < 2n-4$ for $n\geq4$, by Theorem 1.3 there exists a Hamiltonian path $P_{xy}^0$ passing through $M_0\cup\{u_0v_0\}$ in $Q_n^0$. Note that $v_0 = x$ and $u_0v_0$ lies on the path $P_{xy}^0$, and we also have $E(P_{xy}^0)\cap F_0 = \emptyset$.

In the above two cases, choose an edge $s_0t_0\in E(P_{xy}^0)\setminus M_0$ satisfying $v_0\notin\{s_0, t_0\}$. In $Q_n^1$, by Theorem 1.1 there exists a Hamiltonian path $P_{s_1t_1}^1$. Hence, $P_{xy} = P_{xy}^0+P_{s_1t_1}^1+\{s_0s_1, t_0t_1\}-s_0t_0$ is the desired Hamiltonian path.

Sub-case 2.2. $x\in V(Q_n^0)$, $y\in V(Q_n^1)$ (or $x\in V(Q_n^1)$, $y\in V(Q_n^0)$).

Since $|M_0\cup F_0| = 2n-5 < 2n-4$, $|M_0|\geq1$, and $\delta(Q_n^0-F_0)\geq2$, by Theorem 1.6 there exists a Hamiltonian cycle $C_0$ containing $M_0$ in $Q_n^0-F_0$. Choose a neighbor $s_0$ of $x$ on $C_0$ such that $xs_0\notin M_0$ and $s_0\neq v_0$. We claim that the vertex $s_0$ exists. If $s_0$ does not exist, then in one direction along the cycle $C_0$, $x$ is adjacent to $v_0$, and in the other direction, $x$ is incident with a matching edge. Thus, $Q_n^0$ contains $x$$-$$DS$. A contradiction occurs. Since $p(s_1)\neq p(y)$, by Theorem 1.1 there exists a Hamiltonian path $P_{s_1y}^1$ in $Q_n^1$. Hence, $P_{xy} = C_0+P_{s_1y}^1+s_0s_1-xs_0$ is the desired Hamiltonian path.

Sub-case 2.3. $x, y\in V(Q_n^1)$.

Since $|M_0\cup F_0| = 2n-5 < 2n-4$, $|M_0|\geq1$, and $\delta(Q_n^0-F_0)\geq2$, by Theorem 1.6 there exists a Hamiltonian cycle $C_0$ containing $M_0$ in $Q_n^0-F_0$. Choose an edge $s_0t_0\in E(C_0)\setminus M_0$ such that $v_0\notin\{s_0, t_0\}$ and $s_1t_1\neq xy$. Since $|E(C_0)\setminus M_0|-2-1\geq2^n-|M_0|-3\geq2^n-(n-3)-3 = 2^n-n > 1$ for $n\geq4$, such an edge $s_0t_0$ exists. By Lemma 2.2, there exists a Hamiltonian path $P_{xy}^1$ passing through $s_1t_1$ in $Q_n^1$. Hence, $P_{xy} = P_{xy}^1+C_0+\{s_0s_1, t_0t_1\}-\{s_0t_0, s_1t_1\}$ is the desired Hamiltonian path. □

Lemma 4.2. For $n\geq4$, let $M$ be a matching of $Q_n$, and let $F$ be a set of edges in $Q_n-M$ with $|M\cup F|\leq2n-6$. Let $x, y\in V(Q_n)$ be such that $p(x)\neq p(y)$ and $xy\notin M$. If $\delta(Q_n-F) = 3$, then there exists a Hamiltonian path joining $x$ and $y$ passing through $M$ in $Q_n-F$.

Proof. We prove the conclusion by induction on $n$. When $n = 4$, the conclusion holds by Corollary 2.4. Assume that the conclusion holds for $n\geq4$, and we are to show that it holds for $n+1$. Now, $|M\cup F|\leq2(n+1)-6 = 2n-4$.

By Theorem 1.4, we only need to consider the case that $|M|\geq1$. Now, $|F|\leq2n-5$. Thus, there are at most two vertices of degree 3 in $Q_{n+1}-F$. If there are three vertices of degree 3 in $Q_{n+1}-F$, then $|F|\geq3(n+1-3)-2 = 3n-8 > 2n-5$ for $n\geq4$. A contradiction occurs.

Case A. There are two vertices of degree 3, denoted by $v$ and $v'$, in $Q_{n+1}-F$.

If $vv'\notin F$, then $|F|\geq2(n+1-3) = 2n-4$. A contradiction occurs. Thus, $vv'\in F$. Now, $|F| = 2n-5$, $|M| = 1$, and all the other vertices (except $v$ and $v'$) of $Q_{n+1}-F$ are of degree of at least 4. Let $D(v, v') = \{j\}$. Split $Q_{n+1}$ into $Q_n^0$ and $Q_n^1$ at position $j$. We may assume $v\in V(Q_n^0)$, and denote $v$ by $v_0$. Then, $v' = v_1$, $\delta(Q_n^0-F_0) = 3$, and $\delta(Q_n^1-F_1) = 3$. Note that $|F_0| = |F_1| = n-3$ and $|M| = 1$. Let $M = \{e\}$.

Case 1. $e\notin E_j$. Without loss of generality, assume that $e\in E(Q_n^0)$.

Sub-case 1.1 $x, y\in V(Q_n^0)$.

Since $|M_0\cup F_0| = n-2$, by Corollary 2.4 there exists a Hamiltonian path $P_{xy}^0$ passing through $M_0$ in $Q_n^0-F_0$. Choose an edge $s_0t_0\in E(P_{xy}^0)\setminus M_0$ such that $v_0\notin\{s_0, t_0\}$. Since $|E(P_{xy}^0)\setminus M_0|-2 = 2^n-4 > 1$ for $n\geq4$, such an edge $s_0t_0$ exists. Since $|F_1| = n-3 < 2n-5$ for $n\geq4$, by Theorem 1.4 there exists a Hamiltonian path $P_{s_1t_1}^1$ in $Q_n^1-F_1$. Hence, $P_{xy} = P_{xy}^0+P_{s_1t_1}^1+\{s_0s_1, t_0t_1\}-s_0t_0$ is a Hamiltonian path joining $x$ and $y$ passing through $M$ in $Q_{n+1}-F$.

Sub-case 1.2. $x\in V(Q_n^0)$, $y\in V(Q_n^1)$ (or $x\in V(Q_n^1)$, $y\in V(Q_n^0)$).

Since $2^{n-1} > 2$, we can choose a vertex $z_0$ in $Q_n^0$ such that $p(x)\neq p(z_0)$, $z_0\neq v_0$, and $xz_0\neq e$. By Corollary 2.4, there exists a Hamiltonian path $P_{xz_0}^0$ passing through $M_0$ in $Q_n^0-F_0$. By Theorem 1.4, there exists a Hamiltonian path $P_{z_1y}^1$ in $Q_n^1-F_1$. Hence, $P_{xy} = P_{xz_0}^0+P_{z_1y}^1+z_0z_1$ is the desired Hamiltonian path.

Sub-case 1.3. $x, y\in V(Q_n^1)$.

By Theorem 1.4, there exists a Hamiltonian path $P_{xy}^1$ in $Q_n^1-F_1$. Choose an edge $s_1t_1\in E(P_{xy}^1)$ such that $v_0\notin\{s_0, t_0\}$ and $s_0t_0\neq e$. Since $|E(P_{xy}^1)|-3 > 1$ for $n\geq4$, such an edge $s_1t_1$ exists. By Corollary 2.4, there exists a Hamiltonian path $P_{s_0t_0}^0$ passing through $M_0$ in $Q_n^0-F_0$. Hence, $P_{xy} = P_{xy}^1+P_{s_0t_0}^0+\{s_0s_1, t_0t_1\}-s_1t_1$ is the desired Hamiltonian path.

Case 2. $e\in E_j$. Let $e = r_0r_1$. Note that $r_0\neq v_0$.

Sub-case 2.1 $x, y\in V(Q_n^0)$ (or $x, y\in V(Q_n^1)$).

Since $n > 2$, we can choose a neighbor $w_0$ of $r_0$ in $Q_n^0$ such that $w_0\neq v_0$ and $r_0w_0\neq xy$. Since $|\{r_0w_0\}\cup F_0| = n-2$, by Corollary 2.4 there exists a Hamiltonian path $P_{xy}^0$ passing through $r_0w_0$ in $Q_n^0-F_0$. By Theorem 1.4, there exists a Hamiltonian path $P_{r_1w_1}^1$ in $Q_n^1-F_1$. Hence, $P_{xy} = P_{xy}^0+P_{r_1w_1}^1+\{r_0r_1, w_0w_1\}-r_0w_0$ is the desired Hamiltonian path.

Sub-case 2.2. $x\in V(Q_n^0)$, $y\in V(Q_n^1)$ (or $x\in V(Q_n^1)$, $y\in V(Q_n^0)$).

When $p(x)\neq p(r_0)$, by Theorem 1.4 there exist Hamiltonian paths $P_{xr_0}^0$ and $P_{r_1y}^1$ in $Q_n^0-F_0$ and $Q_n^1-F_1$, respectively. Hence, $P_{xy} = P_{xr_0}^0+P_{r_1y}^1+r_0r_1$ is the desired Hamiltonian path.

When $p(x) = p(r_0)$, since $xy\neq r_0r_1$, by symmetry we may assume $y\neq r_1$. Since $n > 1$, we can choose a neighbor $w_1$ of $r_1$ in $Q_n^1$ satisfying $w_1\neq v_1$. Since $n > 2$, we can choose a neighbor $s_1$ of $y$ in $Q_n^1$ satisfying $s_1\notin\{v_1, w_1\}$. Since $|\{r_0w_0\}\cup F_0| = n-2$, by Corollary 2.4 there exists a Hamiltonian path $P_{xs_0}^0$ passing through $r_0w_0$ in $Q_n^0-F_0$. Note that $\{r_1, w_1, s_1, y\}$ is a balanced vertex set. Since $|F_1| = n-3\leq2n-7$ for $n\geq4$ and $\delta(Q_n^1-F_1)\geq3$, by Theorem 3.6 there exists a spanning 2-path $P_{r_1w_1}^1+P_{s_1y}^1$ in $Q_n^1-F_1$. Hence, $P_{xy} = P_{xs_0}^0+P_{r_1w_1}^1+P_{s_1y}^1+\{s_0s_1, r_0r_1, w_0w_1\}-r_0w_0$ is the desired Hamiltonian path.

Case B. There is exactly a vertex, denoted by $v$, of degree 3 in $Q_{n+1}-F$.

Now, all the other vertices in $Q_n-F$ are of degree of at least 4. Let $F_v = \{e\in F$ $|$ $e$ is incident with $v$$\}$. Note that $|F|\geq|F_v| = (n+1)-3 = n-2$ and $|M|\leq2n-4-|F|\leq n-2$.

Case 1. $|M| = n-2$. Now, $|F| = |F_v| = n-2$.

Denote the three edges incident with $v$ in $Q_{n+1}-F$ by $uv$, $vr$, and $vs$. If $v\in V(M)$, then let $uv\in M$.

When $v\notin\{x, y\}$, first we claim that $\{x, y, M\cup\{uv, vs\}\}$ is compatible or $\{x, y, M\cup\{uv, vr\}\}$ is compatible. Note that $M\cup\{uv, vs\}$ and $M\cup\{uv, vr\}$ are both linear forest. If $\{x, y, M\cup\{uv, vs\}\}$ is not compatible, then $\{x, y, M\cup\{uv, vs\}\}$ does not satisfy the condition (2) in Theorem 1.3. Now there are three possibilities for $\{M\cup\{uv, vs\}\}$ up to isomorphism; see Figure 3(1)-(3). Next, we will verify that $\{x, y, M\cup\{uv, vr\}\}$ satisfies the condition (2) in Theorem 1.3. Note that there are two cases for $r$, uncovered by $M$ or covered by $M$. We denote the two cases by $r'$ and $r''$. If $r\notin V(M)$, then let $r = r'$; if $r\in V(M)$, then let $r = r''$; see Figure 3.

If $x$ or $y$ is an internal vertex of the induced subgraph of $\{M\cup\{uv, vs\}\}$, then for the case (1)(2) in Figure 3, $x = s$ or $y = s$; for the case (3) in Figure 3, $x = s$ or $u$, or $y = s$ or $u$. Note that $x$ and $y$ cannot be $s$ and $u$ simultaneously because $p(x)\neq p(y)$. For the above three cases, without loss of generality, assume that $x = s$. Since $p(x)\neq p(y)$, we have $y\notin\{u, r\}$. Note that $y\neq v$ and $xy\notin M$. Thus, $\{x, y, M\cup\{uv, vr\}\}$ satisfies the condition (2) in Theorem 1.3. If $x, y$ are endpoints of a path in the induced subgraph of $\{M\cup\{uv, vs\}\}$, then since $p(x)\neq p(y)$ and $xy\notin M$, we have that $\{M\cup\{uv, vs\}\}$ must be the case (1) or (2) in Figure 3 and $x, y$ exactly are the two endpoints of the path of length 3. Note that the two internal vertices of this path are $v$ and $s$, and $r\notin\{x, y, v, s\}$. Hence, $\{x, y, M\cup\{uv, vr\}\}$ satisfies the condition (2) in Theorem 1.3. The claim is proved. Without loss of generality, assume that $\{x, y, M\cup\{uv, vs\}\}$ is compatible.

Since $|M\cup\{uv, vs\}|\leq n < 2(n+1)-4$ for $n\geq4$, by Theorem 1.3 there exists a Hamiltonian path $P_{xy}$ passing through $M\cup\{uv, vs\}$ in $Q_{n+1}$. Note that all faulty edges incident with $v$ do not lie on the path $P_{xy}$. Thus, we have $E(P_{xy})\cap F = \emptyset$.

When $v\in\{x, y\}$, we may assume $v = x$. If $v\in V(M)$, then now $uv\in M$ and $vr, vs\notin M$. Thus, $M\cup\{uv\} = M$ and $\{x, y, M\}$ is compatible. If $v\notin V(M)$, then since $xy\neq uv$ or $xy\neq vr$ or $xy\neq vs$, without loss of generality, assume that $xy\neq uv$. So, $\{x, y, M\cup\{uv\}\}$ is compatible. Since $|M\cup\{uv\}|\leq n-1 < 2(n+1)-4$ for $n\geq4$, by Theorem 1.3 there exists a Hamiltonian path $P_{xy}$ passing through $M$ in $Q_{n+1}-F$.

Case 2. $|M|\leq n-3$.

Since $|M|\leq n-3 < n-2 = |F_v|$, there exists a position $j\in[n+1]$ such that $|F_v\cap E_j| = 1$ and $|M\cap E_j| = 0$. Split $Q_{n+1}$ into $Q_n^0$ and $Q_n^1$ at position $j$. Assume $v\in V(Q_n^0)$, and denote $v$ by $v_0$. Hence, $\delta(Q_n^0-F_0) = 3$ and $\delta(Q_n^1-F_1)\geq3$. Note that $|F_0|\geq n-3$, $|M_0\cup F_0|\leq2n-5$, and $|M_1\cup F_1|\leq n-2$.

Sub-case 2.1. $|M_0\cup F_0|\leq2n-6$. Note that $|F_c|\leq2n-4-(n-3)-1 = n-2$.

Sub-case 2.1.1 $x, y\in V(Q_n^0)$ (or $x, y\in V(Q_n^1)$)

By induction hypothesis, there exists a Hamiltonian path $P_{xy}^0$ passing through $M_0$ in $Q_n^0-F_0$. Choose an edge $s_0t_0\in E(P_{xy}^0)\setminus M_0$ such that $\{s_0s_1, t_0t_1\}\cap F_c = \emptyset$ and $s_1t_1\notin M_1$. Since $|E(P_{xy}^0)\setminus M_0|-2|F_c|-|M_1| = |E(P_{xy}^0)|-(|M_0|+|F_c|+|M_1|)-|F_c|\geq2^n-1-(n-1)-(n-2) = 2^n-2n+2 > 1$ for $n\geq4$, such an edge $s_0t_0$ exists. By Corollary 2.4, there exists a Hamiltonian path $P_{s_1t_1}^1$ passing through $M_1$ in $Q_n^1-F_1$. Hence, $P_{xy} = P_{xy}^0+P_{s_1t_1}^1+\{s_0s_1, t_0t_1\}-s_0t_0$ is the desired Hamiltonian path.

Sub-case 2.1.2. $x\in V(Q_n^0)$, $y\in V(Q_n^1)$ (or $x\in V(Q_n^1)$, $y\in V(Q_n^0)$).

Choose a vertex $z_0$ in $Q_n^0$ such that $p(x)\neq p(z_0)$, $z_0z_1\notin F_c$, and $\{xz_0, z_1y\}\cap M = \emptyset$. Note that $|M|+|F_c|\leq 2n-4-(|F_v|-1) = n-1$. Since $2^{n-1}-|M|-|F_c|\geq2^{n-1}-(n-1) = 2^{n-1}-n+1 > 1$ for $n\geq4$, such a vertex $z_0$ exists. By induction hypothesis, there exists a Hamiltonian path $P_{xz_0}^0$ passing through $M_0$ in $Q_n^0-F_0$. By Corollary 2.4, there exists a Hamiltonian path $P_{z_1y}^1$ passing through $M_1$ in $Q_n^1-F_1$. Hence, $P_{xy} = P_{xz_0}^0+P_{z_1y}^1+z_0z_1$ is the desired Hamiltonian path.

Sub-case 2.2. $|M_0\cup F_0| = 2n-5$. Now, $|M_0|\geq1$, $F_c = \{v_0v_1\}$, and $|M_1\cup F_1| = 0$.

Sub-case 2.2.1. $x, y\in V(Q_n^0)$.

Since $|M_0| = |M|\leq n-3$, we have $|F_0|\geq n-2$. So we can choose an edge $r_0w_0\in F_0\setminus F_v$. Thus, $v_0\notin\{r_0, w_0\}$. Note that $d_{Q_n^0-(F_0\setminus\{r_0w_0\})}(v_0) = 3$. So, we have $\delta(Q_n^0-(F_0\setminus\{r_0w_0\})) = 3$. Since $|M_0\cup(F_0\setminus\{r_0w_0\})| = 2n-6$, by induction hypothesis there exists a Hamiltonian path $P_{xy}^0$ passing through $M_0$ in $Q_n^0-(F_0\setminus\{r_0w_0\})$. If $r_0w_0\notin E(P_{xy}^0)$, then choose an edge $s_0t_0\in E(P_{xy}^0)\setminus M_0$ satisfying $v_0\notin\{s_0, t_0\}$. If $r_0w_0\in E(P_{xy}^0)$, then let $s_0t_0 = r_0w_0$. In $Q_n^1$, by Theorem 1.1 there exists a Hamiltonian path $P_{s_1t_1}^1$. Hence, $P_{xy} = P_{xy}^0+P_{s_1t_1}^1+\{s_0s_1, t_0t_1\}-s_0t_0$ is the desired Hamiltonian path.

Sub-case 2.2.2. $x\in V(Q_n^0)$, $y\in V(Q_n^1)$ (or $x\in V(Q_n^1)$, $y\in V(Q_n^0)$).

Since $|M_0\cup F_0| = 2n-5 < 2n-4$, $|M_0|\geq1$, and $\delta(Q_n^0-F_0)\geq3$, by Theorem 1.6 there exists a Hamiltonian cycle $C_0$ containing $M_0$ in $Q_n^0-F_0$. Choose a neighbor $s_0$ of $x$ on $C_0$ satisfying $xs_0\notin M_0$. If $s_0\neq v_0$, then by Theorem 1.1 there exists a Hamiltonian path $P_{s_1y}^1$ in $Q_n^1$. Hence, $P_{xy} = C_0+P_{s_1y}^1+s_0s_1-xs_0$ is the desired Hamiltonian path. If $s_0 = v_0$, then since $d_{Q_n^0-F_0}(v_0) = 3$, let $u_0$ be the neighbor of $v_0$ in $Q_n^0$ satisfying $d_{C_0}(u_0, v_0) > 1$ and $u_0v_0\notin F_0$. Note that there are two neighbors of $u_0$ on $C_0$. One neighbor lies on the path joining $v_0$ and $u_0$ on $C_0$ which contains $x$. We denote it as $w_0$. The other neighbor is denoted as $t_0$.

If $u_0t_0\notin M_0$, then by Theorem 1.1 there exists a Hamiltonian path $P_{t_1y}^1$ in $Q_n^1$. Hence, $P_{xy} = C_0+P_{t_1y}^1+\{u_0v_0, t_0t_1\}-\{xv_0, u_0t_0\}$ is the desired Hamiltonian path. If $u_0t_0\in M_0$, then $u_0w_0\notin M_0$. Let $r_0$ be the neighbor of $t_0$ on $C_0$ which is not $u_0$. Now, $r_0t_0\notin M_0$ and $p(w_1) = p(t_1)\neq p(r_1) = p(y)$. By Corollary 3.4, there exists a spanning 2-path $P_{t_1w_1}^1+P_{r_1y}^1$ in $Q_n^1$. Hence, $P_{xy} = C_0+P_{t_1w_1}^1+P_{r_1y}^1+\{u_0v_0, t_0t_1, r_0r_1, w_0w_1\}-\{xv_0, u_0w_0, r_0t_0\}$ is the desired Hamiltonian path.

Sub-case 2.2.3. $x, y\in V(Q_n^1)$.

Since $|M_0\cup F_0| = 2n-5 < 2n-4$, $|M_0|\geq1$, and $\delta(Q_n^0-F_0)\geq3$, by Theorem 1.6 there exists a Hamiltonian cycle $C_0$ containing $M_0$ in $Q_n^0-F_0$. Choose an edge $s_0t_0\in E(C_0)\setminus M_0$ such that $v_0\notin\{s_0, t_0\}$ and $s_1t_1\neq xy$. Since $|E(C_0)\setminus M_0|-3 > 1$ for $n\geq4$, such an edge $s_0t_0$ exists. In $Q_n^1$, by Theorem 2.2 there exists a Hamiltonian path $P_{xy}^1$ passing through $s_1t_1$. Hence, $P_{xy} = P_{xy}^1+C_0+\{s_0s_1, t_0t_1\}-\{s_0t_0, s_1t_1\}$ is the desired Hamiltonian path. □

Lemma 4.3. For $n\geq4$, let $M$ be a matching of $Q_n$, and let $F$ be a set of edges in $Q_n-M$ with $|M\cup F|\leq2n-6$. Let $x, y\in V(Q_n)$ be such that $p(x)\neq p(y)$ and $xy\notin M$. If $\delta(Q_n-F)\geq4$, then there exists a Hamiltonian path joining $x$ and $y$ passing through $M$ in $Q_n-F$.

Proof. We prove the conclusion by induction on $n$. When $n = 4$, the conclusion is by Corollary 2.4. Assume that the conclusion holds for $n\geq4$, and we are to show that it holds for $n+1$. Now, $|M\cup F|\leq2(n+1)-6 = 2n-4$. By Theorems 1.3 and 1.4, we only need to consider the case that $|F|\geq1$ and $|M|\geq1$.

Select $j\in[n+1]$ such that $|(M\cup F)\cap E_j|$ is as small as possible. Since $|M\cup F|\leq2n-4$, there exists a position $j\in[n+1]$ such that $|(M\cup F)\cap E_j|\leq1$. When $|(M\cup F)\cap E_j| = 1$, let $(M\cup F)\cap E_j = \{w_0w_1\}$, and now there are at least six possibilities of such $j$. We choose the $j$ such that the edge in $(M\cup F)\cap E_j$ lies in $F$ if possible. Otherwise, the edge in $(M\cup F)\cap E_j$ is a matching edge for every $j$ of the above six possibilities. In this case, since $x$ and $y$ are incident with at most two edges in $M$, we can choose $j$ such that the matching edge in $(M\cup F)\cap E_j$ is not incident with $x$ and $y$, i.e., $\{x, y\}\cap\{w_0, w_1\} = \emptyset$. Split $Q_{n+1}$ into $Q_n^0$ and $Q_n^1$ at position $j$. Without loss of generality, assume that $|M_0\cup F_0|\geq|M_1\cup F_1|$. Now, $\delta(Q_n^0-F_0)\geq3$ and $\delta(Q_n^1-F_1)\geq3$.

Case 1. $|M\cap E_j| = 0$. Now, $|M_1\cup F_1|\leq n-2$.

Sub-case 1.1. $|M_0\cup F_0|\leq2n-6$.

Sub-case 1.1.1. $x, y\in V(Q_n^0)$ (or $x, y\in V(Q_n^1)$).

By induction hypothesis when $\delta(Q_n^0-F_0)\geq4$ and Lemma 4.2 when $\delta(Q_n^0-F_0) = 3$, there exists a Hamiltonian path $P_{xy}^0$ passing through $M_0$ in $Q_n^0-F_0$. Choose an edge $u_0v_0\in E(P_{xy}^0)\setminus M_0$ such that $u_1v_1\notin M_1$ and $\{u_0u_1, v_0v_1\}\cap F_c = \emptyset$. Since $|E(P_{xy}^0)\setminus M_0|-|M_1|-2|F_c| = |E(P_{xy}^0)|-|M|-2|F_c|\geq 2^n-1-(2n-5)-2 = 2^n-2n+2 > 1$ for $n\geq4$, such an edge $u_0v_0$ exists. By Corollary 2.4, there exists a Hamiltonian path $P_{u_1v_1}^1$ passing through $M_1$ in $Q_n^1-F_1$. Hence, $P_{xy} = P_{xy}^0+P_{u_1v_1}^1+\{u_0u_1, v_0v_1\}-u_0v_0$ is a Hamiltonian path joining $x$ and $y$ passing through $M$ in $Q_{n+1}-F$.

Sub-case 1.1.2. $x\in V(Q_n^0)$, $y\in V(Q_n^1)$ (or $x\in V(Q_n^1)$, $y\in V(Q_n^0)$).

Since $2^{n-1} > 3$ for $n\geq4$, we can choose a vertex $z_0\in V(Q_n^0)$ such that $p(x)\neq p(z_0)$, $\{xz_0, z_1y\}\cap M = \emptyset$, and $z_0z_1\notin F_c$. By induction hypothesis when $\delta(Q_n^0-F_0)\geq4$ and Lemma 4.2 when $\delta(Q_n^0-F_0) = 3$, there exists a Hamiltonian path $P_{xz_0}^0$ passing through $M_0$ in $Q_n^0-F_0$. By Corollary 2.4, there exists a Hamiltonian path $P_{z_1y}^1$ passing through $M_1$ in $Q_n^1-F_1$. Hence, $P_{xy} = P_{xz_0}^0+P_{z_1y}^1+z_0z_1$ is the desired Hamiltonian path.

Sub-case 1.2. $|M_0\cup F_0| = 2n-5$. Now, $|F_c|+|M_1\cup F_1|\leq1$.

Sub-case 1.2.1. $x, y\in V(Q_n^0)$.

Sub-case 1.2.1.1. $F_0 = \emptyset$. Now, $|F_c|+|F_1| = 1$, $|M_1| = 0$, $|M_0| = 2n-5 < 2n-4$.

By Theorem 1.3, there exists a Hamiltonian path $P_{xy}^0$ passing through $M_0$ in $Q_n^0$. Choose an edge $u_0v_0\in E(P_{xy}^0)\setminus M_0$ such that $\{u_0u_1, v_0v_1\}\cap F_c = \emptyset$. Since $|E(P_{xy}^0)\setminus M_0|-2|F_c|\geq2^n-1-(2n-5)-2 = 2^n-2n+2 > 1$ for $n\geq4$, such an edge $u_0v_0$ exists. Since $|F_1|\leq1 < 2n-5$, by Theorem 1.4 there exists a Hamiltonian path $P_{u_1v_1}^1$ in $Q_n^1-F_1$. Hence, $P_{xy} = P_{xy}^0+P_{u_1v_1}^1+\{u_0u_1, v_0v_1\}-u_0v_0$ is the desired Hamiltonian path.

Sub-case 1.2.1.2. $F_0\neq\emptyset$. Let $s_0t_0\in F_0$. Note that $\delta(Q_n^0-(F_0\setminus\{s_0t_0\}))\geq3$.

Since $|M_0\cup(F_0\setminus\{s_0t_0\})| = 2n-6$, by induction hypothesis and Lemma 4.2, there exists a Hamiltonian path $P_{xy}^0$ passing through $M_0$ in $Q_n^0-(F_0\setminus\{s_0t_0\})$. Next, we distinguish four cases to consider.

If $s_0t_0\notin E(P_{xy}^0)$, then choose an edge $u_0v_0\in E(P_{xy}^0)\setminus M_0$ such that $u_1v_1\notin M_1$ and $\{u_0u_1, v_0v_1\}\cap F_c = \emptyset$. Since $|E(P_{xy}^0)\setminus M_0|-|M_1|-2|F_c|\geq2^n-1-(2n-5)-2 = 2^n-2n+2 > 1$ for $n\geq4$, such an edge $u_0v_0$ exists. If $s_0t_0\in E(P_{xy}^0)$, $s_1t_1\notin M_1$, and $\{s_0s_1, t_0t_1\}\cap F_c = \emptyset$, then let $u_0v_0 = s_0t_0$. In the above two cases, since $|M_1\cup F_1|\leq1 < n-2$, by Corollary 2.4 there exists a Hamiltonian path $P_{u_1v_1}^1$ passing through $M_1$ in $Q_n^1-F_1$. Hence, $P_{xy} = P_{xy}^0+P_{u_1v_1}^1+\{u_0u_1, v_0v_1\}-u_0v_0$ is the desired Hamiltonian path.

If $s_0t_0\in E(P_{xy}^0)$ and $s_1t_1\in M_1$, then now $|F_c\cup F_1| = 0$. Choose an edge $u_0v_0\in E(P_{xy}^0)\setminus M_0$ such that $\{u_0, v_0\}\cap\{s_0, t_0\} = \emptyset$. Since $|E(P_{xy}^0)\setminus M_0|-3\geq2^n-1-(2n-6)-3 = 2^n-2n+2 > 1$ for $n\geq4$, such an edge $u_0v_0$ exists. In $Q_n^1$, by Theorem 3.1 there exists a spanning 2-path $P_{u_1v_1}^1+s_1t_1$. Hence, $P_{xy} = P_{xy}^0+P_{u_1v_1}^1+s_1t_1+\{s_0s_1, t_0t_1, u_0u_1, v_0v_1\}-\{s_0t_0, u_0v_0\}$ is the desired Hamiltonian path.

It remains to consider the case $s_0t_0\in E(P_{xy}^0)$ and $\{s_0s_1, t_0t_1\}\cap F_c\neq\emptyset$. Now, $|M_1\cup F_1| = 0$. Without loss of generality, assume that $F_c = \{s_0s_1\}$ and $s_0$ is closer to $x$ than $t_0$ on $P_{xy}^0$. Let $N(s_0) =$\{$v\in V(Q_n^0)$ $|$ $d_{Q_n^0}(s_0, v) = 1$, $d_{P_{xy}^0}(s_0, v) > 1$, and $vs_0\notin F_0$$\}$. Note that $t_0\notin N(s_0)$. Since $d_{Q_n^0-F_0}(s_0)\geq3$, we have $|N(s_0)|\geq2$.

If there exists a vertex $r_0\in N(s_0)$ such that $r_0\in V(P_{xy}^0[x, s_0])$ and $r_0\neq x$, then choose a neighbor $w_0$ of $r_0$ on $P_{xy}^0$ such that $r_0w_0\notin M_0$. When $w_0\in V(P_{xy}^0[r_0, s_0])$, by Theorem 1.1 there exists a Hamiltonian path $P_{t_1w_1}^1$ in $Q_n^1$. Hence, $P_{xy} = P_{xy}^0+P_{t_1w_1}^1+\{s_0r_0, t_0t_1, w_0w_1\}-\{s_0t_0, r_0w_0\}$ is the desired Hamiltonian path. When $w_0\in V(P_{xy}^0[x, r_0])$, choose an edge $u_0v_0\in E(P_{xy}^0[r_0, s_0])\setminus M_0$ satisfying $s_0\notin\{u_0, v_0\}$. Since $d_{P_{xy}^0}(r_0, s_0)\geq3$, such an edge $u_0v_0$ exists. In $Q_n^1$, by Theorems 3.1 and 3.2 there exists a spanning 2-path $P_{w_1u_1}^1+P_{t_1v_1}^1$. Hence, $P_{xy} = P_{xy}^0+P_{w_1u_1}^1+P_{t_1v_1}^1+\{s_0r_0, w_0w_1, u_0u_1, v_0v_1, t_0t_1\}-\{w_0r_0, u_0v_0, s_0t_0\}$ is the desired Hamiltonian path.

Otherwise, there exists at least one vertex in $N(s_0)$ which lies on $P_{xy}^0[t_0, y]$. Denote the one closest to $t_0$ by $z_0$. Note that $z_0\neq y$, otherwise, the vertex $r_0$ in the above case exists. A contraction occurs. Since $p(x)\neq p(y)$ and $p(s_0)\neq p(z_0)$, the number of odd vertices equals to the number of even vertices on $P_{xy}^0[x, s_0]+P_{xy}^0[z_0, y]$. Since $s_0$ has at least $|N(s_0)|+1$ neighbors which lie on $P_{xy}^0[x, s_0]+P_{xy}^0[z_0, y]$, we have $|V(P_{xy}^0[x, s_0]+P_{xy}^0[z_0, y])|\geq6$. Thus, $|E(P_{xy}^0[x, s_0]+P_{xy}^0[z_0, y])|\geq4$.

Choose a neighbor $w_0$ of $z_0$ on $P_{xy}^0$ such that $z_0w_0\notin M_0$. If $w_0\in V(P_{xy}^0[z_0, y])$, then by Theorem 1.1 there exists a Hamiltonian path $P_{t_1w_1}^1$ in $Q_n^1$. Hence, $P_{xy} = P_{xy}^0+P_{t_1w_1}^1+\{s_0z_0, t_0t_1, w_0w_1\}-\{s_0t_0, z_0w_0\}$ is the desired Hamiltonian path. If $w_0\in V(P_{xy}^0[s_0, z_0])$, then choose an edge $u_0v_0\in E(P_{xy}^0[x, s_0]+P_{xy}^0[z_0, y])\setminus M_0$ satisfying $s_0\notin\{u_0, v_0\}$. Since $|E(P_{xy}^0[x, s_0]+P_{xy}^0[z_0, y])|\geq4$, such an edge $u_0v_0$ exists. In $Q_n^1$, by Theorems 3.1 and 3.2 there exists a spanning 2-path $P_{w_1u_1}^1+P_{t_1v_1}^1$. Hence, $P_{xy} = P_{xy}^0+P_{w_1u_1}^1+P_{t_1v_1}^1+\{s_0z_0, t_0t_1, w_0w_1, u_0u_1, v_0v_1\}-\{s_0t_0, z_0w_0, u_0v_0\}$ is the desired Hamiltonian path.

Sub-case 1.2.2. $x\in V(Q_n^0)$, $y\in V(Q_n^1)$ (or $x\in V(Q_n^1)$, $y\in V(Q_n^0)$).

Since $|M_0\cup F_0| = 2n-5 < 2n-4$, by Theorem 1.6 when $M_0\neq\emptyset$ and Corollary 1.5 when $M_0 = \emptyset$, there exists a Hamiltonian cycle $C_0$ containing $M_0$ in $Q_n^0-F_0$. Choose a neighbor $s_0$ of $x$ on $C_0$ such that $xs_0\notin M_0$.

Sub-case 1.2.2.1. $s_0s_1\notin F_c$.

When $s_1y\notin M_1$, since $|M_1\cup F_1|\leq1 < n-2$, by Corollary 2.4 there exists a Hamiltonian path $P_{s_1y}^1$ passing through $M_1$ in $Q_n^1-F_1$. Hence, $P_{xy} = C_0+P_{s_1y}^1+s_0s_1-xs_0$ is the desired Hamiltonian path. When $s_1y\in M_1$, now $|F_c\cup F_1| = 0$ and $|M_0|\leq2n-6$. Choose an edge $u_0v_0\in E(C_0)\setminus M_0$ such that $s_0\notin\{u_0, v_0\}$ and $y\notin\{u_1, v_1\}$. Since $|E(C_0)\setminus M_0|-2-2\geq2^n-(2n-6)-4 = 2^n-2n+2 > 1$ for $n\geq4$, such an edge $u_0v_0$ exists. In $Q_n^1$, by Theorem 3.1 there exists a spanning 2-path $P_{u_1v_1}^1+s_1y$ passing through $M_1$. Hence, $P_{xy} = C_0+P_{u_1v_1}^1+s_1y+\{u_0u_1, v_0v_1, s_0s_1\}-\{xs_0, u_0v_0\}$ is the desired Hamiltonian path.

Sub-case 1.2.2.2. $s_0s_1\in F_c$. Now $|M_1\cup F_1| = 0$.

Since $d_{Q_n^0-F_0}(s_0)\geq3$, we can choose a neighbor $t_0$ of $s_0$ in $Q_n^0$ such that $d_{C_0}(t_0, s_0)\neq1$ and $s_0t_0\notin F_0$. Choose a neighbor $r_0$ of $t_0$ on $C_0$ such that $t_0r_0\notin M_0$. If $r_0$ lies on one path joining $t_0$ and $s_0$ on $C_0$ and $x$ lies on the other, then by Theorem 1.1 there exists a Hamiltonian path $P_{r_1y}^1$ in $Q_n^1$. Hence, $P_{xy} = C_0+P_{r_1y}^1+\{s_0t_0, r_0r_1\}-\{xs_0, t_0r_0\}$ is the desired Hamiltonian path. If $r_0$ and $x$ lie on the same path joining $t_0$ and $s_0$ on $C_0$, then let $u_0$ be the other neighbor of $t_0$ on $C_0$. Now, $t_0u_0\in M_0$ and $u_0\neq s_0$. Let $v_0$ be the other neighbor of $u_0$ on $C_0$. So, $u_0v_0\notin M_0$. Since $p(r_1) = p(u_1)\neq p(v_1) = p(y)$ and $r_1\neq u_1$, by Corollary 3.4 there exists a spanning 2-path $P_{r_1u_1}^1+P_{v_1y}^1$ in $Q_n^1$. Hence, $P_{xy} = C_0+P_{r_1u_1}^1+P_{v_1y}^1+\{s_0t_0, u_0u_1, v_0v_1, r_0r_1\}-\{xs_0, u_0v_0, t_0r_0\}$ is the desired Hamiltonian path; see Figure 4.

Sub-case 1.2.3. $x, y\in V(Q_n^1)$.

Since $|M_0\cup F_0| = 2n-5 < 2n-4$, by Theorem 1.6 when $M_0\neq\emptyset$ and Corollary 1.5 when $M_0 = \emptyset$, there exists a Hamiltonian cycle $C_0$ containing $M_0$ in $Q_n^0-F_0$. Choose an edge $s_0t_0\in E(C_0)\setminus M_0$ such that $\{s_0s_1, t_0t_1\}\cap F_c = \emptyset$, $s_1t_1\neq xy$, and $\{s_1, t_1\}\cap V(M_1) = \emptyset$. Since $|E(C_0)\setminus M_0|-2|F_c|-1-4|M_1| = |E(C_0)|-|M|-(2|F_c|+3|M_1|)-1\geq2^n-(2n-5)-3-1 = 2^n-2n+1 > 1$ for $n\geq4$, such an edge $s_0t_0$ exists. Since $|(M_1\cup\{s_1t_1\})\cup(F_1\setminus\{s_1t_1\})|\leq2\leq n-2$ for $n\geq4$ and $M_1\cup\{s_1t_1\}$ is a matching, by Corollary 2.4 there exists a Hamiltonian path $P_{xy}^1$ passing through $M_1\cup\{s_1t_1\}$ in $Q_n^1-(F_1\setminus\{s_1t_1\})$. Hence, $P_{xy} = C_0+P_{xy}^1+\{s_0s_1, t_0t_1\}-\{s_0t_0, s_1t_1\}$ is the desired Hamiltonian path.

Sub-case 1.3. $|M_0\cup F_0| = 2n-4$. Now, $|F_c|+|M_1\cup F_1| = 0$ and $|M_0|\geq1$.

Since $|M_0\cup F_0| = 2n-4$ and $|M_0|\geq1$, by Theorem 1.6 there exists a Hamiltonian cycle $C_0$ containing $M_0$ in $Q_n^0-F_0$.

Sub-case 1.3.1. $x, y\in V(Q_n^0)$.

Choose neighbors $s_0, t_0$ of $x, y$ on $C_0$ such that $xs_0\notin M_0$ and $t_0y\notin M_0$. If $s_0$ lies on one path joining $x$ and $y$ on $C_0$ and $r_0$ lies on the other, then by Theorem 1.1 there exists a Hamiltonian path $P_{s_1t_1}^1$ in $Q_n^1$. Hence, $P_{xy} = C_0+P_{s_1t_1}^1+\{s_0s_1, t_0t_1\}-\{xs_0, t_0y\}$ is the desired Hamiltonian path. If $s_0$ and $t_0$ lie on the same path joining $x$ and $y$ on $C_0$, then choose an edge $r_0w_0\in E(C_0)\setminus M_0$ on the other path. We may assume that $r_0$ is closer to $x$ than $w_0$ on one path joining $x$ and $y$ on $C_0$. By Theorems 3.1 and 3.2, there exists a spanning 2-path $P_{r_1s_1}^1+P_{w_1t_1}^1$ in $Q_n^1$. Hence, $P_{xy} = C_0+P_{r_1s_1}^1+P_{w_1t_1}^1+\{s_0s_1, t_0t_1, r_0r_1, w_0w_1\}-\{xs_0, t_0y, r_0w_0\}$ is the desired Hamiltonian path.

Sub-case 1.3.2. $x\in V(Q_n^0)$, $y\in V(Q_n^1)$ (or $x\in V(Q_n^1)$, $y\in V(Q_n^0)$).

Choose a neighbor $s_0$ of $x$ on $C_0$ such that $xs_0\notin M_0$. In $Q_n^1$, by Theorem 1.1 there exists a Hamiltonian path $P_{s_1y}^1$. Hence, $P_{xy} = C_0+P_{s_1y}^1+s_0s_1-xs_0$ is the desired Hamiltonian path.

Sub-case 1.3.3. $x, y\in V(Q_n^1)$.

Choose an edge $s_0t_0\in E(C_0)\setminus M_0$ satisfying $s_0t_0\neq xy$. Since $|E(C_0)\setminus M_0|-1\geq2^n-(2n-5)-1 = 2^n-2n+4 > 1$ for $n\geq4$, such an edge $s_0t_0$ exists. In $Q_n^1$, by Lemma 2.2 there exists a Hamiltonian path $P_{xy}^1$ passing through $s_1t_1$. Hence, $P_{xy} = C_0+P_{xy}^1+\{s_0s_1, t_0t_1\}-\{s_0t_0, s_1t_1\}$ is the desired Hamiltonian path.

Case 2. $|M\cap E_j| = 1$. Now, $M_c = \{w_0w_1\}$, $\{w_0, w_1\}\cap\{x, y\} = \emptyset$, $|F_c| = 0$, and $|M_1\cup F_1|\leq\lfloor\frac{2n-4-1}{2}\rfloor = n-3 < n-2$.

Sub-case 2.1. $|M_0\cup F_0|\leq2n-6$.

Sub-case 2.1.1. $x, y\in V(Q_n^0)$ (or $x, y\in V(Q_n^1)$).

By induction hypothesis and Lemma 4.2, there exists a Hamiltonian path $P_{xy}^0$ passing through $M_0$ in $Q_n^0-F_0$. Choose a neighbor $r_0$ of $w_0$ on $P_{xy}^0$. By Corollary 2.4, there exists a Hamiltonian path $P_{r_1w_1}^1$ passing through $M_1$ in $Q_n^1-F_1$. Hence, $P_{xy} = P_{xy}^0+P_{r_1w_1}^1+\{r_0r_1, w_0w_1\}-r_0w_0$ is the desired Hamiltonian path.

Sub-case 2.1.2. $x\in V(Q_n^0)$, $y\in V(Q_n^1)$ (or $x\in V(Q_n^1)$, $y\in V(Q_n^0)$).

When $p(x)\neq p(w_0)$, by induction hypothesis and Lemma 4.2, there exists a Hamiltonian path $P_{xw_0}^0$ passing through $M_0$ in $Q_n^0-F_0$. By Corollary 2.4, there exists a Hamiltonian path $P_{w_1y}^1$ passing through $M_1$ in $Q_n^1-F_1$. Hence, $P_{xy} = P_{xw_0}^0+P_{w_1y}^1+w_0w_1$ is the desired Hamiltonian path.

When $p(x) = p(w_0)$, choose a neighbor $s_1$ of $y$ in $Q_n^1$ such that $s_1\notin V(M_1)$ and $xs_0\notin M_0$. Since $n > (n-3)+1$, such a vertex $s_1$ exists. By induction hypothesis and Lemma 4.2, there exists a Hamiltonian path $P_{xs_0}^0$ passing through $M_0$ in $Q_n^0-F_0$.

If there exists a neighbor $r_0$ of $w_0$ on $P_{xs_0}^0$ such that $r_0\neq s_0$ and $r_1y\notin M_1$, then since $|M_1\cup F_1|\leq n-3$, by Lemma 3.8 there exists a spanning 2-path $P_{s_1y}^1+P_{r_1w_1}^1$ passing through $M_1$ in $Q_n^1-F_1$. Hence, $P_{xy} = P_{xs_0}^0+P_{s_1y}^1+P_{r_1w_1}^1+\{s_0s_1, w_0w_1, r_0r_1\}-r_0w_0$ is the desired Hamiltonian path; see Figure 5(1).

Otherwise, $d_{P_{xs_0}^0}(s_0, w_0) = 1$, and the other neighbor $r_0$ of $w_0$ on $P_{xs_0}^0$ satisfies $r_1y\in M_1$. Choose an edge $u_0v_0\in E(P_{xs_0}^0)\setminus M_0$ such that $u_1v_1\neq s_1w_1$ and $\{u_1, v_1\}\cap V(M_1) = \emptyset$. Since $|E(P_{xs_0}^0)\setminus M_0|-1-4|M_1| = |E(P_{xs_0}^0)|-(|M_0|+|M_1|)-1-3|M_1|\geq(2^n-1)-(2n-6)-1-3(n-3) = 2^n-5n+13 > 1$ for $n\geq4$, such an edge $u_0v_0$ exists. Since $|(M_1\cup \{u_1v_1\}\setminus\{r_1y\})\cup F_1|\leq n-3$ and $s_1w_1r_1ys_1$ is a cycle of length four, by Lemma 3.12 there exists a spanning 2-path $P_{s_1w_1}^1+r_1y$ passing through $M_1\cup\{u_1v_1\}$ in $Q_n^1-(F_1\setminus\{u_1v_1\})$. Hence, $P_{xy} = P_{xs_0}^0+P_{s_1w_1}^1+r_1y+\{s_0s_1, w_0w_1, r_0r_1, u_0u_1, v_0v_1\}-\{w_0r_0, u_0v_0, u_1v_1\}$ is the desired Hamiltonian path; see Figure 5(2).

Sub-case 2.2. $|M_0\cup F_0| = 2n-5$. Now, $|M_1\cup F_1| = 0$ and $|F_0|\geq1$.

Sub-case 2.2.1. $x, y\in V(Q_n^0)$.

Let $u_0v_0\in F_0$. By induction hypothesis and Lemma 4.2, there exists a Hamiltonian path $P_{xy}^0$ passing through $M_0$ in $Q_n^0-(F_0\setminus\{u_0v_0\})$. If $u_0v_0\notin E(P_{xy}^0)$, then choose a neighbor $r_0$ of $w_0$ on $P_{xy}^0$. If $u_0v_0\in E(P_{xy}^0)$ and $d_{P_{xy}^0}(w_0, u_0v_0) = 0$, then let $r_0w_0 = u_0v_0$. In $Q_n^1$, by Theorem 1.1 there exists a Hamiltonian path $P_{r_1w_1}^1$. Hence, $P_{xy} = P_{xy}^0+P_{r_1w_1}^1+\{r_0r_1, w_0w_1\}-r_0w_0$ is the desired Hamiltonian path. If $u_0v_0\in E(P_{xy}^0)$ and $d_{P_{xy}^0}(w_0, u_0v_0)\geq1$, then since $w_0\notin\{x, y\}$, we can choose a neighbor $r_0$ of $w_0$ on $P_{xy}^0$ such that $r_0\notin\{u_0, v_0\}$. In $Q_n^1$, by Theorem 3.1 there exists a spanning 2-path $P_{u_1v_1}^1+P_{r_1w_1}^1$. Hence, $P_{xy} = P_{xy}^0+P_{u_1v_1}^1+P_{r_1w_1}^1+\{r_0r_1, w_0w_1, u_0u_1, v_0v_1\}-\{r_0w_0, u_0v_0\}$ is the desired Hamiltonian path.

Sub-case 2.2.2. $x\in V(Q_n^0)$, $y\in V(Q_n^1)$ (or $x\in V(Q_n^1)$, $y\in V(Q_n^0)$).

Since $|M_0\cup F_0| = 2n-5 < 2n-4$, by Theorem 1.6 when $M_0\neq\emptyset$ and Corollary 1.5 when $M_0 = \emptyset$, there exists a Hamiltonian cycle $C_0$ containing $M_0$ in $Q_n^0-F_0$. If $d_{C_0}(w_0, x) = 1$, then by Theorem 1.1 there exists a Hamiltonian path $P_{w_1y}^1$ in $Q_n^1$. Hence, $P_{xy} = C_0+P_{w_1y}^1+w_0w_1-xw_0$ is the desired Hamiltonian path. If $d_{C_0}(w_0, x) = 2$, then choose neighbors $s_0, r_0$ of $x, w_0$ on $C_0$, respectively, such that $xs_0\notin M_0$ and $r_0\neq s_0$. Now, $p(s_1) = p(r_1)\neq p(w_1) = p(y)$ and $s_1, y, r_1, w_1$ are distinct vertices. If $d_{C_0}(w_0, x)\geq3$, then choose neighbors $s_0, r_0$ of $x, w_0$ on $C_0$, respectively, such that $r_1\neq y$ and $xs_0\notin M_0$. Now, $p(s_1)\neq p(y)$, $p(r_1)\neq p(w_1)$, and $s_1, y, r_1, w_1$ are distinct vertices. In the above two cases, by Theorem 3.1 there exists a spanning 2-path $P_{s_1y}^1+P_{r_1w_1}^1$ in $Q_n^1$. Hence, $P_{xy} = C_0+P_{s_1y}^1+P_{r_1w_1}^1+\{s_0s_1, r_0r_1, w_0w_1\}-\{xs_0, r_0w_0\}$ is the desired Hamiltonian path.

Sub-case 2.2.3. $x, y\in V(Q_n^1)$.

Since $|M_0\cup F_0| = 2n-5 < 2n-4$, by Theorem 1.6 when $M_0\neq\emptyset$ and Corollary 1.5 when $M_0 = \emptyset$, there exists a Hamiltonian cycle $C_0$ containing $M_0$ in $Q_n^0-F_0$. Choose a neighbor $r_0$ of $w_0$ on $C_0$. Since $r_1w_1\neq xy$, by Lemma 2.2 there exists a Hamiltonian path $P_{xy}^1$ passing through $r_1w_1$ in $Q_n^1$. Hence, $P_{xy} = P_{xy}^1+C_0+\{r_0r_1, w_0w_1\}-\{r_0w_0, r_1w_1\}$ is the desired Hamiltonian path. □

5.   Conclusions

We investigate the existence of a Hamiltonian path in $Q_n$ passing through a matching and avoiding faulty edges. From Lemmas 4.1, 4.2, and 4.3, we can obtain the following conclusion.

Theorem 5.1. For $n\geq4$, let $M$ be a matching of $Q_n$, and let $F$ be a set of edges in $Q_n-M$ with $|M\cup F|\leq2n-6$. Let $x, y\in V(Q_n)$ be such that $p(x)\neq p(y)$ and $xy\notin M$. If the degree of every vertex in $Q_n-F$ is at least $2$, and there is neither $x/y$$-$$DS$ nor $(x, y)$$-$$DS$ in $Q_n-F$, then there exists a Hamiltonian path joining $x$ and $y$ passing through $M$ in $Q_n-F$.

Author contributions

Shenyang Zhao: Methodology and Writing-original & draft; Fan Wang: Conceptualization and Writing-review & editing. All authors have read and agreed to the published version of the manuscript.

Acknowledgments

The authors would like to express their gratitude to the anonymous referees whose helpful comments and suggestions have led to a substantial improvement of the paper.

This work is supported by NSFC (grant no. 12061047), and supported by Jiangxi Provincial Natural Science Foundation (nos. 20212BAB201027 and 20192BAB211002).

Conflict of interest

The authors declare that they have no conflicts of interest in this work.