1 Introduction
A Hamilton path in a graph G is a path containing all vertices of G, and a Hamilton cycle in G is a cycle containing all vertices of G. A graph is said to be Hamiltonian if it contains a Hamilton cycle. It is well known that determining whether a given graph is Hamiltonian is NP-complete. More generally, the Hamiltonian problem concerns the search for conditions that guarantee the existence of a Hamilton cycle. Named after Sir William Rowan Hamilton and inspired by his Icosian game, this problem dates back to the 1850s. It is therefore natural and important to study sufficient conditions for Hamiltonicity. A classical result is Dirac’s theorem [Reference Dirac4], which states that every graph of order n with minimum degree at least
$n/2$
is Hamiltonian. Dirac’s theorem initiated the study of degree conditions for Hamiltonicity, and many refinements and generalisations have since been established (see [Reference Chvátal and Erdős3] and the survey [Reference Gould5]).
Beyond Hamiltonicity itself, stronger Hamiltonian properties have also attracted considerable attention. Among them, Hamiltonian-connectedness is a natural strengthening of Hamiltonicity. A graph G is Hamiltonian-connected if every two distinct vertices of G are joined by a Hamilton path. Among the classical sufficient conditions for Hamiltonian-connectedness, Ore’s theorem and the Chvátal–Erdős theorem are two of the most fundamental results.
Define
$\sigma _2(G)=\min \{d_G(u)+d_G(v):u,v\in V(G)\text { and }uv\notin E(G)\}$
if G is not complete, and define
$\sigma _2(G)=\infty $
otherwise. In 1963, Ore [Reference Ore11] proved the following result.
Theorem 1.1 (Ore [Reference Ore11])
Let G be a graph of order
$n\ge 3$
. If
$\sigma _2(G)\ge n+1$
, then G is Hamiltonian-connected.
In 1972, Chvátal and Erdős [Reference Chvátal and Erdős3] established the following sufficient condition for Hamiltonian-connectedness in terms of its connectivity and independence number.
Theorem 1.2 (Chvátal–Erdős [Reference Chvátal and Erdős3])
Let
$k\ge 2$
be an integer. If G is a k-connected graph with
$\alpha (G)\le k-1$
, then G is Hamiltonian-connected.
The concept of an
$[s,t]$
-graph is closely related to the independence number. A graph G is called an
$[s,t]$
-graph if every induced subgraph of G on s vertices contains at least t edges. This notion naturally extends the concept of independence number, since
$\alpha (G)\le k$
if and only if G is a
$[k+1,1]$
-graph. Moreover, every
$[s,t]$
-graph is also an
$[s+1,t+1]$
-graph. Therefore, it is natural to ask whether the Chvátal–Erdős theorem can be extended to the setting of
$[s,t]$
-graphs.
Recently, Cheng [Reference Cheng2] obtained the following generalisation. The join
$G\vee H$
of two graphs G and H is obtained from the disjoint union of G and H by adding edges joining every vertex of G to every vertex of
$H.$
Theorem 1.3 (Cheng [Reference Cheng2])
Let
$k\ge 2$
be an integer. If the graph G is a k-connected
$[k+1,2]$
-graph, then G is Hamiltonian-connected unless
$G=kK_1\vee G_k$
, where
$G_k$
is an arbitrary graph of order k.
Theorem 1.3 can be viewed as a genuine generalisation of the Chvátal–Erdős theorem. Indeed, if G satisfies the assumptions of Theorem 1.2, then G is a k-connected
$[k,1]$
-graph and, hence, also a
$[k+1,2]$
-graph. The exceptional graph
$kK_1\vee G_k$
has independence number k, and so this exceptional case cannot occur under the condition
$\alpha (G)\le k-1$
and Theorem 1.3 reduces to Theorem 1.2.
In the setting of
$[s,t]$
-graphs, several results on Hamiltonicity and pancyclicity have been obtained in recent years. In 2005, Liu and Wang [Reference Liu and Wang8] proved that every
$2$
-connected
$[4,2]$
-graph of order at least
$6$
is Hamiltonian. Later, Liu [Reference Liu10] studied the pancyclicity of
$[4,2]$
-graphs and proved that every
$2$
-connected
$[4,2]$
-graph of order at least seven is pancyclic. An alternative proof of this result was given in [Reference Zhan13]. An edge e of a graph G of order n is called a pancyclic edge if e lies on a cycle of length k for every integer k with
$3\le k\le n$
. Very recently, Li and Zhan [Reference Li and Zhan6] strengthened the last result by proving that every
$2$
-connected
$[4,2]$
-graph of order at least seven contains a pancyclic edge.
For
$[5,3]$
-graphs, Li and Wang established the following Hamiltonicity result in 2006.
Theorem 1.4 (Li and Wang [Reference Li and Wang7])
Every
$2$
-connected
$[5,3]$
-graph of order at least eight with minimum degree at least three is Hamiltonian.
Very recently, Liu and Liu proved the following pancyclicity theorem for
$[5,3]$
-graphs.
Theorem 1.5 (Liu and Liu [Reference Liu and Liu9])
Every
$2$
-connected
$[5,3]$
-graph of order at least nine with minimum degree at least three is pancyclic.
Motivated by these results, we study the Hamiltonian-connectedness of
$[5,3]$
-graphs. Before presenting our main result, we recall another graph parameter closely related to Hamiltonian properties, namely toughness. The toughness of a graph G, denoted by
$\tau (G)$
, is defined by
where
$c(G-S)$
denotes the number of connected components of
$G-S$
, if G is not complete, and
$\tau (G)=\infty $
otherwise. For a positive real number t, a graph G is called t-tough if
$\tau (G)\ge t$
.
Toughness is closely connected with Hamiltonian properties. It is well known that every Hamiltonian graph is
$1$
-tough, while every Hamiltonian-connected graph has toughness greater than
$1$
. Moreover, by the definition of toughness, every t-tough noncomplete graph is
$\lceil 2t\rceil $
-connected and, hence, has minimum degree at least
$\lceil 2t\rceil $
. Our main result is as follows.
Theorem 1.6. Every
$[5,3]$
-graph of order at least nine with toughness greater than one is Hamiltonian-connected.
Remark 1.7. The toughness condition in Theorem 1.6 cannot be replaced by
$3$
-connectivity alone. For each integer
$n\ge 6$
, let
$G_n$
be the graph obtained from a clique
$K_{n-2}$
by adding two vertices x and y such that
$N(x)=N(y)=\{a,b,c\}$
for some three vertices
$a,b,c$
of
$K_{n-2}$
. A typical example with
$n=10$
is shown in Figure 1.
A
$3$
-connected
$[5,3]$
-graph that is not Hamiltonian-connected.
It is easy to see that
$G_n$
is a
$3$
-connected
$[5,3]$
-graph. However, since deleting the set
$\{a,b,c\}$
leaves exactly three components, namely the two isolated vertices
$x,y$
and the clique
$K_{n-5}$
, we have
$\tau (G_n)\leq 1$
. Moreover,
$G_n$
is pancyclic and, hence,
$\tau (G_n)=1$
. Since every Hamiltonian-connected graph has toughness greater than
$1$
, it follows that
$G_n$
is not Hamiltonian-connected.
2 Proof of Theorem 1.6
In this section, we prove Theorem 1.6. Before proceeding, we introduce some notation and record several observations that will be used throughout the proof. We consider finite simple graphs, and use standard terminology and notation from [Reference Bondy and Murty1, Reference West12]. For a graph G, we denote by
$V(G)$
and
$E(G)$
its vertex set and edge set, respectively. For a vertex
$u\in V(G)$
and a subgraph
$H\subseteq G$
, let
$N_H(u)$
denote the set of neighbours of u in
$V(H)$
. For a subset
$S\subseteq V(G)$
, define
$N_G(S)=\bigcup _{x\in S}N_G(x)\setminus S$
and let
$N_H(S)=N_G(S)\cap V(H)$
. For a subset
$S\subseteq V(G)$
, the subgraph of G induced by S is denoted by
$G[S]$
and we write
$G-S$
for the induced subgraph
$G[V(G)\setminus S]$
. For two disjoint vertex subsets
$A,B\subseteq V(G)$
, we say that A is complete to B if every vertex of A is adjacent to every vertex of B, and that A is anticomplete to B if there are no edges between A and B. Let P be an oriented
$(u,v)$
-path. For two vertices
$x,y\in V(P)$
, we write
$P[x,y]$
for the segment of P between x and y,
$\overrightarrow {P}[x,y]$
for the segment from x to y following the orientation of P, and
$\overleftarrow {P}[x,y]$
for the segment from x to y in the reverse direction. Moreover, for
$x\in V(P)\setminus \{v\}$
, let
$x^{+}$
denote the successor of x on P and for
$x\in V(P)\setminus \{u\}$
, let
$x^{-}$
denote the predecessor of x on P. For a subset
$S\subseteq V(P)$
, define
$S^{+}=\{x^{+}:x\in S\setminus \{v\}\}$
and
$S^{-}=\{x^{-}:x\in S\setminus \{u\}\}$
. For any positive integer t, denote
$[t]=\{1,2,\ldots , t\}$
.
Proof of Theorem 1.6
Let
$u,v\in V(G)$
be any two distinct vertices and let P be a longest
$(u,v)$
-path in G. We may assume that P is not a Hamilton path of G. Write
$P=x_1x_2\cdots x_\ell $
, where
$x_1=u$
and
$x_\ell =v$
. Let H be a component of
$G-V(P)$
and let
$N_P(H)=\{x_{i_1},x_{i_2},\ldots , x_{i_t}\}$
. Since G has toughness greater than
$1$
, it is
$3$
-connected and, hence,
$t\ge 3$
. We start from the following claim.
Claim 1.
$N_P^+(H)$
is an independent set.
Proof. Otherwise, suppose that
$x_{i_p}^+$
and
$x_{i_q}^+$
are adjacent for some
$p,q\in [t]$
. Furthermore, assume by symmetry that
$p<q$
. Since
$x_{i_p},x_{i_q}$
both have a neighbour in H, there is a path Q between
$x_{i_p},x_{i_q}$
with the interior in H. Consequently,
is a
$(u,v)$
-path longer than P, which is a contradiction. This proves Claim 1.
Since P is a longest
$(u,v)$
-path, H has no two consecutive neighbours on P. Thus,
$x_{i_j}x_{i_{j+1}}\notin E(P)$
for any
$j\in [t-1]$
. That is,
$N_P^+(H)\cap N_P(H)=\emptyset $
.
Claim 2.
$\{u,v\}\subseteq N_P(H)$
.
Proof. Otherwise, by symmetry, we may assume that
$v\notin N_P(H)$
. Since G is a
$[5,3]$
-graph, by Claim 1,
$|V(H)|=1$
and
$t=3$
. Let
$V(H)=\{x\}$
. This implies that
$\{x_{i_1}^+,x_{i_2}^+,x_{i_3}^+,x\}$
is an independent set. Since G is a
$[5,3]$
-graph,
$V(G)\setminus \{x_{i_1},x_{i_2},x_{i_3},x\}$
is complete to
$\{x_{i_1}^+,x_{i_2}^+,x_{i_3}^+\}$
. Since
$G[\{x_{i_1},x,x_{i_1}^+,x_{i_2}^+,x_{i_3}^+\}]$
has size at least
$3$
, we have either
$x_{i_1}x_{i_2}^+\in E(G)$
or
$x_{i_1}x_{i_3}^+\in E(G)$
. Suppose that
$u\notin N_P(H)$
.
-
• If $x_{i_1}x_{i_2}^+\in E(G)$
, then
$ ux_{i_1}^+\overrightarrow {P}[x_{i_1}^+,x_{i_2}]x_{i_2}xx_{i_1}\overleftarrow {P}[x_{i_1},x_2]x_2x_{i_2}^+\overrightarrow {P}[x_{i_2}^+,v]v$
is a
$(u,v)$
-path longer than P (see Figure 2(a)), which is a contradiction.Figure 2Illustrations for Claim 2.
Figure 2 Long description
Panel a shows a horizontal line of nodes labeled u, x sub 2, x sub i sub 1, x sub i sub 1 super plus, x sub i sub 2, x sub i sub 2 super plus, x sub i sub 3, and v. A thick orange path connects u to x sub 2, then jumps to x sub i sub 1, continues to x sub i sub 1 super plus, then goes up to node x, down to x sub i sub 2, then to x sub i sub 2 super plus, x sub i sub 3, and finally v. Two curved orange paths exist below the baseline: one connecting u to x sub i sub 1 super plus and another connecting x sub 2 to x sub i sub 2 super plus. A thin black line connects x to x sub i sub 3.
Panel b shows a horizontal line of nodes labeled u, x sub i sub 1 super minus, x sub i sub 1, x sub i sub 1 super plus, x sub i sub 2, x sub i sub 3, x sub i sub 3 super plus, and v. The thick orange path follows the baseline from u to x sub i sub 1 super minus, then jumps to x sub i sub 1, goes up to node x, down to x sub i sub 3, then to x sub i sub 3 super plus, and finally v. Below the baseline, curved orange paths connect x sub i sub 1 super minus to x sub i sub 1 super plus, and x sub i sub 1 to x sub i sub 3 super plus. Thin black lines connect x to x sub i sub 1 super plus and x sub i sub 2.
-
• If $x_{i_1}x_{i_3}^+\in E(G)$
, then
$u\overrightarrow {P}[u,x_{i_1}^-]x_{i_1}^-x_{i_1}^+\overrightarrow {P}[x_{i_1}^+,x_{i_3}]x_{i_3}xx_{i_1}x_{i_3}^+\overrightarrow {P}[x_{i_3}^+,v]v$
is a
$(u,v)$
-path longer than P (see Figure 2(b)), which is a contradiction.
Therefore,
$u\in N_P(H)$
, that is,
$i_1=1$
. Suppose that
$\ell \geq i_3+3$
. Note that
$\{x_{\ell -1},x_{\ell }\}$
is complete to
$\{x_{i_1}^+,x_{i_2}^+\}$
. It follows that
$uxx_{i_2}\overleftarrow {P}[x_{i_2},x_{i_1}^+]x_{i_1}^+x_{\ell -1}\overleftarrow {P}[x_{\ell -1},x_{i_2}^+]x_{i_2}^+x_{\ell }$
is a
$(u,v)$
-path longer than P, which is a contradiction. Therefore,
$i_{3}+1\leq \ell \leq i_{3}+2$
. Since
$|V(G)|\ge 9$
, we have either
$i_2\ge 4$
or
$i_3\ge i_2+3$
.
Suppose
$\ell =i_{3}+2$
. We consider the following two cases.
-
• If $i_2\geq 4$
, then
$uxx_{i_2}\overrightarrow {P}[x_{i_2},x_{i_3}^+]x_{i_3}^+x_{i_2}^-\overleftarrow {P}[x_{i_2}^-,x_2]x_2v$
is a
$(u,v)$
-path longer than P, which is a contradiction. -
• If $i_3\ge i_2+3$
, then
$u\overrightarrow {P}[u,x_{i_2}]x_{i_2}xx_{i_3}x_{i_3}^+x_{i_3}^-\overleftarrow {P}[x_{i_3}^-,x_{i_2}^+]x_{i_2}^+v$
is a
$(u,v)$
-path longer than P, which is a contradiction.
Suppose
$\ell =i_{3}+1$
. We consider the following three cases.
-
• If $i_2\geq 5$
, then
$ux_2x_3x_{i_2}^+\overrightarrow {P}[x_{i_2}^+,x_{i_3}]x_{i_3}xx_{i_2}\overleftarrow {P}[x_{i_2},x_4]x_4v$
is a
$(u,v)$
-path longer than P, which is a contradiction. -
• If $i_2=4 $
, then
$i_3\geq i_2+3$
as
$|V(G)|\geq 9$
. From this, it follows that
$u\overrightarrow {P}[u,x_{i_2}^-]x_{i_2}^-x_{i_2}^+x_{i_2}xx_{i_3}\overleftarrow {P}[x_{i_3},x_{i_2}^{+2}]x_{i_2}^{+2}v$
is a
$(u,v)$
-path longer than P, which is a contradiction. -
• If $i_2=3 $
, then
$i_3\geq i_2+4$
as
$|V(G)|\geq 9$
and
$ux_2x_{i_2}^{+2}x_{i_2}^+x_{i_2}xx_{i_3}\overleftarrow {P}[x_{i_3},x_{i_2}^{+3}]x_{i_2}^{+3}v$
is a
$(u,v)$
-path longer than P, which is a contradiction.
This proves Claim 2.
Claim 3.
$t=3$
.
Proof. Since
$V(H)$
is anticomplete to
$N_P^+(H)$
,
$|N_P^+(H)|\leq 3$
. By Claim 2, we may assume that
$t=4$
. Note that
$|N_P^+(H)|=3$
. Since G is a
$[5,3]$
-graph, by Claim 1,
$|V(H)|=1$
. Let
$V(H)=\{x\}$
. Since
$|V(G)|\geq 9$
, by symmetry, either
$i_2\geq 4$
or
$i_3\geq i_2+3$
. Suppose that
$i_2\geq 4$
. We consider the following two cases.
-
• If $i_2\geq 4$
and
$i_3\geq i_2+3$
, then
$u\overrightarrow {P}[u,x_{i_2}^-]x_{i_2}^-x_{i_2}^+x_{i_2}xx_{i_3}\overleftarrow {P}[x_{i_3},x_{i_2}^{+2}]x_{i_2}^{+2}x_{i_3}^+\overrightarrow {P}[x_{i_3}^+,v]v$
is a
$(u,v)$
-path longer than P (see Figure 3(a)), which is a contradiction.Figure 3Illustrations for Claim 3.
Figure 3 Long description
The image contains two panels, (a) and (b).
Panel (a) shows a horizontal line of nodes starting with u on the far left, followed by x sub i sub 2 super minus, x sub i sub 2, x sub i sub 2 super plus, x sub i sub 2 super plus 2, x sub i sub 3, x sub i sub 3 super plus, and ending with v on the far right. An apex node x is positioned above the center. Thick orange paths connect u to x sub i sub 2 super minus, x sub i sub 2 to x, x to x sub i sub 3, and x sub i sub 3 super plus to v. A straight thin line connects u to x and x to v. Below the baseline, a thick orange curved path connects x sub i sub 2 super minus to x sub i sub 2 super plus, and another connects x sub i sub 2 super plus 2 to x sub i sub 3 super plus.
Panel (b) shows a similar horizontal line of nodes: u, x sub i sub 2 super minus, x sub i sub 2, x sub i sub 2 super plus, x sub i sub 3, and v. The apex node x is above. Thick orange paths connect u to x sub i sub 2 super minus, x sub i sub 2 to x, x to x sub i sub 3, and x sub i sub 3 to v. A thin line connects u to x and x to v. Below the baseline, a single thick orange curved path connects x sub i sub 2 super minus to x sub i sub 2 super plus. A straight thick orange segment also connects x sub i sub 2 to x sub i sub 2 super plus on the baseline.
-
• If $i_2\geq 4$
and
$i_3=i_2+2$
, then
$u\overrightarrow {P}[u,x_{i_2}^-]x_{i_2}^-x_{i_2}^+x_{i_2}xx_{i_3}\overrightarrow {P}[x_{i_3},v]v$
is a
$(u,v)$
-path longer than P (see Figure 3(b)), which is a contradiction.
Therefore,
$i_2= 3$
. By symmetry,
$i_3=\ell -2$
. This implies that
$i_3\geq i_2+3$
. Note that
$\{x_2,x_4,x_{\ell -1}\}$
and
$\{x_2,x_{\ell -3},x_{\ell -1}\}$
are two independent sets. However, it follows that
$G[\{x,x_2,x_4,x_{\ell -3},x_{\ell -1}\}]$
has size at most one, which is a contradiction. This proves Claim 3.
Claim 4.
$c(G-V(P))=1$
.
Proof. Otherwise, let
$H'$
be the component of
$G-V(P)$
distinct from H. Then clearly,
$|V(H)|=|V(H')|=1.$
Write
$V(H)=\{x\}$
and
$V(H')=\{y\}$
. By Claim 3, we may assume that
$N_P(y)=\{u,v,x_j\}.$
Without loss of generality, assume that
$j\ge i_2$
. We assert that
$j=i_2$
. Suppose to the contrary that
$j\ne i_2$
. Then,
$G[\{x,y,x_2,x_{i_2}^+,x_j^+\}]$
contains at most two edges, which is a contradiction. Hence,
$j=i_2$
. Thus,
$c(G-\{u,v,x_{i_2}\})\geq 3$
, which implies that
$\tau (G)\le 1,$
which is a contradiction. This proves Claim 4.
Claim 5.
$|V(H)|=1$
.
Proof. Otherwise, we may assume that
$|V(H)|\geq 2$
. By Claim 3,
$S=\{u,v,x_{i_2}\}$
is a vertex cut of G such that H is a component of
$G-S$
. Since G has toughness greater than
$1$
, it follows that
$c(G-S)=2$
. Let
$H'$
be the other component of
$G-S$
. Then,
$V(H')=V(G)\setminus (V(H)\cup S).$
Since G is
$3$
-connected and
$|V(H)|\ge 2$
, there exists a
$(u,x_{i_2})$
-path
$P_u$
in G whose internal vertices lie in
$V(H)$
and whose order is at least
$4$
, and there exists a
$(v,x_{i_2})$
-path
$P_v$
in G whose internal vertices lie in
$V(H)$
and whose order is at least
$4$
. Next, we assert that
$|V(H')|\geq 5$
. Suppose to the contrary that
$|V(H')|\leq 4$
. Indeed, by the existence of
$P_u$
and
$P_v$
, we must have
$i_2=4$
and
$\ell =7$
. Let
$x,x'\in V(H)$
. Note that
$x_2x_5\notin E(G)$
. Since
$G[\{x,x',x_2,x_5,x_6\}]$
has size at least
$3$
,
$x_2x_6\in E(G)$
. However, it follows that
$ux_2x_6x_5x_4P_vv$
is a
$(u,v)$
-path longer than P, which is a contradiction.
Suppose that
$H'$
is not Hamiltonian-connected. Then,
$H'$
is noncomplete. Let
$y,y'$
be two nonadjacent vertices of
$H'$
. Since
$|V(H)|\ge 2$
and H is connected, there exists an edge
$xx'$
in H. Now, let
$z\in V(H')\setminus \{y,y'\}$
be arbitrary. Consider the induced subgraph
$G[\{x,x',y,y',z\}]$
. Since G is a
$[5,3]$
-graph, this induced subgraph has at least
$3$
edges. However,
$\{x,x'\}$
is anticomplete to
$\{y,y',z\}$
and
$yy'\notin E(G)$
. Hence, the only possible edges in
$G[\{x,x',y,y',z\}]$
are
$xx'$
,
$yz$
and
$y'z$
. It follows that both
$yz$
and
$y'z$
belong to
$E(G)$
. Therefore,
$V(H')\setminus \{y,y'\}$
is complete to
$\{y,y'\}$
. This implies that
$\deg _{H'}(y)+\deg _{H'}(y')=2(|V(H')|-2)$
. Hence, we see that
$\sigma _2(H')\ge 2(|V(H')|-2)$
. Since
$|V(H')|\ge 5$
, we have
$2(|V(H')|-2)\ge |V(H')|+1$
. Therefore,
$\sigma _2(H')\ge |V(H')|+1$
. It follows from Theorem 1.1 that
$H'$
is Hamiltonian-connected, to the contrary to our hypothesis. Consequently,
$H'$
must be Hamiltonian-connected.
Since G is
$3$
-connected and
$H'$
is Hamiltonian-connected, there exists a
$(u,x_{i_2})$
-path
$Q_u$
in G such that
$V(H')\subseteq Q_u$
. However, it follows that
$uQ_ux_{i_2}P_vv$
is a
$(u,v)$
-path longer than P, which is a contradiction. This proves Claim 5.
By Claim 5, let
$V(H)=\{x\}$
. Since the choice of P was arbitrary, the same argument applies to any longest
$(u,v)$
-path Q. Hence, for every longest
$(u,v)$
-path Q,
Claim 6.
$i_2\geq 4$
and
$\ell \geq i_2+3$
.
Proof. Otherwise, by symmetry, we may assume that
$i_2=3$
. Since
$|V(G)|\ge 9$
, it follows that
$\ell \ge i_2+5$
. Note that
$x_2$
is anticomplete to
$\{x_4,x_{\ell -1}\}$
. Since G has minimum degree at least three, choose
$x_j\in N(x_2)\cap \{x_5,\ldots ,x_{\ell -2}\}$
such that the subscript j is as small as possible.
Suppose that
$j\geq 6$
. Note that
$\{x_2,x_4,x_{j-1},x_{\ell -1}\}\cap N(x)=\emptyset $
and
$x_{j-1}\notin N(x_2)$
. Since
$G[\{x,x_2,x_4,x_{j-1},x_{\ell -1}\}]$
has size at least three,
$x_j^-x_{\ell -1}\in E(G)$
. However, it follows that
$ux_2x_j\overrightarrow {P}[x_j,x_{\ell -1}]x_{\ell -1}x_j^-\overleftarrow {P}[x_j^-,x_3]x_3xv$
is a
$(u,v)$
-path longer than P, which is a contradiction. Therefore,
$j=5$
.
If
$x_4x_{\ell -1}\in E(G)$
, then
$ux_2x_5\overrightarrow {P}[x_5,x_{\ell -1}]x_{\ell -1}x_4x_3xv$
is a
$(u,v)$
-path longer than P, which gives a contradiction. Therefore,
$\{x_2,x_4,x_{\ell -1}\}$
is an independent set. Since
$G[\{x,x_2,x_4,x_6,x_{\ell -1}\}]$
has size at least three,
$x_4x_6\in E(G)$
. This implies that
$uxx_3x_2x_5x_4x_6\overrightarrow {P}[x_6,v]v$
is a
$(u,v)$
-path longer than P, which is a contradiction. This proves Claim 6.
Since
$|V(G)|\ge 9$
, either
$i_2\ge 5$
or
$\ell \ge i_2+4$
. By symmetry, we may assume that
$\ell \ge i_2+4$
.
Claim 7.
$i_2\geq 5$
.
Proof. By Claim 6, we may assume that
$i_2=4$
. If
$v_{\ell -1}v_2\in E(G)$
, then
$ux_2x_{\ell -1}$
$\overleftarrow {P}[x_{\ell -1},x_{i_2}]x_{i_2}xv$
is a longest
$(u,v)$
-path. By (2.1),
$ux_3\in E(G)$
. This implies that
$ux_3x_2x_{\ell -1}\overleftarrow {P}[x_{\ell -1},x_{i_2}]x_{i_2}xv$
is a
$(u,v)$
-path longer than P, which is a contradiction. Hence,
$x_{\ell -1}$
is anticomplete to
$\{x_2,x_3\}$
. On the one hand, since
$G[\{x,x_2,x_3,x_5,x_{\ell -1}\}]$
has size at least three,
$x_5x_{\ell -1}\in E(G)$
. On the other hand, since
$G[\{x,x_2,x_3,x_6,x_{\ell -1}\}]$
has size at least three, either
$x_2x_6\in E(G)$
or
$x_3x_6\in E(G)$
. We consider the following two cases.
-
• If $x_2x_6\in E(G)$
, then
$ux_2x_6\overrightarrow {P}[x_6,x_{\ell -1}]x_{\ell -1}x_5x_4xv$
is a longest
$(u,v)$
-path. By (2.1),
$ux_3\in E(G)$
. This implies that
$ux_3x_2x_2x_6\overrightarrow {P}[x_6,x_{\ell -1}]x_{\ell -1}x_5x_4xv$
is a
$(u,v)$
-path longer than P, which is a contradiction. -
• If $x_3x_6\in E(G)$
, then
$ux_2x_3x_6\overrightarrow {P}[x_6,x_{\ell -1}]x_{\ell -1}x_5x_4xv$
is a
$(u,v)$
-path longer than P, which is a contradiction.
This proves Claim 7.
Since
$G[\{x,x_2,x_{i_2}^-,x_{i_2}^+,x_{\ell -1}\}]$
has size at least three, either
$x_2x_{i_2}^-\in E(G)$
or
$x_{i_2}^+x_{\ell -1}\in E(G)$
. By symmetry, we may assume that
$x_{i_2}^+x_{\ell -1}\in E(G)$
. If
$x_{i_2}^-x_{i_2}^{+2}\in E(G)$
, then
$u\overrightarrow {P}[u,x_{i_2}^-]x_{i_2}^-x_{i_2}^{+2}\overrightarrow {P}[x_{i_2}^{+2},x_{\ell -1}]x_{\ell -1}x_{i_2}^+x_{i_2}xv$
is a
$(u,v)$
-path longer than P, which is a contradiction. Therefore,
$x_{i_2}^-x_{i_2}^{+2}\notin E(G)$
. If
$x_2x_{i_2}^{+2}\in E(G)$
, then
$uxx_{i_2}\overleftarrow {P}[x_{i_2},x_2]x_2x_{i_2}^{+2}\overrightarrow {P}[x_{i_2}^{+2},v]v$
is a longest
$(u,v)$
-path. By (2.1),
$vx_{i_2}^{+}\in E(G)$
. This implies that
is a
$(u,v)$
-path longer than P, which is a contradiction. Therefore,
$x_2x_{i_2}^{+2}\notin E(G)$
.
Since
$G[\{x,x_2,x_{i_2}^-,x_{i_2}^{+2},x_{\ell -1}\}]$
has size at least three,
$x_2x_{i_2}^-\in E(G)$
. By symmetry,
$x_{i_2}^{-2}x_{\ell -1}\notin E(G)$
. Since
$G[\{x,x_{i_2}^{-2},x_{i_2}^{-},x_{i_2}^{+2},x_{\ell -1}\}]$
has size at least three,
$x_{i_2}^{-2}x_{i_2}^{+2}\in E(G)$
. However, it follows that
$uxx_{i_2}x_{i_2}^-x_2\overrightarrow {P}[x_2,x_{i_2}^{-2}]x_{i_2}^{-2}x_{i_2}^{+2}\overrightarrow {P}[x_{i_2}^{+2},v]v$
is a longest
$(u,v)$
-path. By (2.1),
$vx_{i_2}^{+}\in E(G)$
. Thus,
$uxx_{i_2}x_{i_2}^-x_2\overrightarrow {P}[x_2,x_{i_2}^{-2}]x_{i_2}^{-2}x_{i_2}^{+2}\overrightarrow {P}[x_{i_2}^{+2},x_{\ell -1}]x_{\ell -1}x_{i_2}^{+}v$
is a
$(u,v)$
-path longer than P, which is a contradiction. This completes the proof of Theorem 1.6.
