# An existence criterion for a cycle such that the vertex set beyond this
cycle is independent

Nikolai Karol

(2020)

Abstract

We prove that if $G$ is a 2-connected graph with
$\delta(G)\geqslant\frac{v(G)+2}{3}$ then $G$ has a cycle $W$ such that
$V(G-W)$ is independent. This result is best possible in the sense that it
becomes false if $\frac{v(G)+2}{3}$ is replaced by any smaller number.

1 Introduction

The Hamiltonian cycle existence problem is well-known and well explored. Apart
from classical Dirac and Ore’s criteria, Chvátal’s theorems (see [1]) are
worthy of mention. In addition to these results, there is a problem whether
the graph power is Hamiltonian. There are classical results here: well-known
Fleischner’s theorem (see [3]) and Chartrand and Kapoor’s theorem of [2].

As for long cycles, there is classical Linial’s theorem of [4].

Theorem (N. Linial, 1975) Let $G$ be a 2-connected graph and

$m=\min\limits_{xy\notin E(G)}d_{G}(x)+d_{G}(y)\text{.}$

Then the length of the longest cycle of G is at least min(m, v(G)).

Thomassen’s paper [5] contains an existence criterion in planar graphs for a
cycle with special condition: the vertex set beyond it must be independent.
Our work contains the following existence criterion for such a cycle in terms
of graph’s minimum degree.

######  Theorem 1.

Let $G$ be a 2-connected graph, $v(G)=n$ and
$\delta(G)\geqslant\frac{n+2}{3}$. Then $G$ has a cycle such that the vertex
set beyond this cycle is independent.

2 Proof of Theorem 1

We will invoke the following classical lemma in our proof, which is used in
the proofs of Ore’s theorem and several Chvátal’s theorems.

######  Lemma 1.

Let $m>2$ and $u_{1}...u_{m}$ be a path of the maximal length in the graph
$G$, $d_{G}(u_{1})+d_{G}(u_{m})\geqslant m$. Then $G$ has a cycle of length m.

## Proof of Theorem 1.

For the sake of convenience, 5 Claims are highlighted.

We highlight that we will use $\delta(G)\geqslant\frac{n}{3}$. We will use
$\delta(G)\geqslant\frac{n+2}{3}$ in a couple of places only.

Assuming the converse, there exists graph $G$ such that $v(G)=n$,
$\delta(G)\geqslant\frac{n+2}{3}$, $G$ does not contain a cycle such that the
vertex set beyond it is independent.

Assume that $n<6$. Since $G$ is 2-connected, $\delta(G)\geqslant 2$. If
$n\in\\{3,4\\}$ then it follows from $\delta(G)\geqslant 2$ that the graph
contains a cycle. This cycle satisfies all the requirements because the vertex
set beyond the cycle contains at most 1 vertex. If $n=5$ then $G$ also has a
cycle. If the cycle length is 4 or 5 then, similarly, this cycle meets all the
requirements. Hence, the cycle length is 3. Let us denote vertices of the
cycle by $r_{1},r_{2},r_{3}$ and the remaining vertices by $r_{4},r_{5}$. If
$r_{4}r_{5}\notin E(G)$ then cycle $r_{1}r_{2}r_{3}$ obviously meets all the
conditions. Consequently, $r_{4}r_{5}\in E(G)$. Since $G$ is connected,
$e_{G}(\\{r_{1},r_{2},r_{3}\\},\\{r_{4},r_{5}\\})\geqslant 1$. Without loss of
generality, $r_{1}r_{4}\in E(G)$. Since $G$ is 2-connected, $G-\\{r_{1}\\}$ is
connected. Therefore, $e_{G}(\\{r_{2},r_{3}\\},\\{r_{4},r_{5}\\})\geqslant 1$.
Without loss of generality, $r_{2}r_{4}\in E(G)$ or $r_{2}r_{5}\in E(G)$. If
$r_{2}r_{4}\in E(G)$ then $r_{1}r_{4}r_{2}r_{3}$ is a suitable cycle (see
figure 1 a). If $r_{2}r_{5}\in E(G)$ then $r_{1}r_{4}r_{5}r_{2}r_{3}$ is a
suitable Hamiltonian cycle (see figure 1 b).

Figure 1: $n=5$.

Therefore, from now on we have that

$n\geqslant 6\textit{.}$ $None$

If all aforementioned properties (2-connectivity, minimum degree, lack of the
required cycle) remain, we add an edge to the graph. Obviously, 2-connectivity
and minimum degree properties remain after adding an edge, so we add an edge
if absence of the required cycle remains. Let us perform this procedure as
long as we can, we stop the procedure if we cannot add any edge. We do not
want to make new notations, so we use the same symbol $G$ for the graph we
obtain after stopping the procedure. Consequently, $G$ has the following
property:

For any $d_{1},d_{2}\in V(G)$ such that $d_{1}d_{2}\notin E(G)$, there is a
path between $d_{1}$ and $d_{2}$ such that the vertex set beyond this path is
independent.

######  Claim 1.

$G$ has a Hamiltonian path.

###### Proof.

Figure 2: $z_{t}\in A$ and $z_{t-2}\in B$ for some $t$.

Consider the longest path $L_{0}$ in the graph $G$ such that its endpoints are
not adjacent to each other and the vertex set beyond this path is independent.
Assuming the converse, this is not a Hamiltonian path. Then there are $k<n$
vertices in $L_{0}$. Let us number them in the order of passing the path:
$z_{1},z_{2},...,z_{k}$. We say that vertex $z_{i}$ is on the right of vertex
$z_{j}$ if $i>j$ and vertex $z_{i}$ is on the left of vertex $z_{j}$ if $i<j$.
Let $A=N_{G}(z_{1})$, $B=N_{G}(z_{k})$. It is clear that $A\cup B\subset
L_{0}$ (otherwise, $L_{0}$ may be lengthened due to some vertex from $A\cup
B\setminus L_{0}$). Then, since $d_{G}(z_{1})\geqslant\frac{n}{3}$ and
$d_{G}(z_{k})\geqslant\frac{n}{3}$, $|A\cap L_{0}|\geqslant\frac{n}{3}$ and
$|B\cap L_{0}|\geqslant\frac{n}{3}$.

Note that, for any $t$, the following property is satisfied: if $z_{t}\in A$
then $z_{t-2}\notin B$. Assuming the converse, $z_{t}\in A$ and $z_{t-2}\in B$
(see figure 2). If $N_{G}(z_{t-1})\subseteq L_{0}$ then note that there is a
cycle of length $k-1$ (see figure 2). The vertex set beyond this cycle
consists of the vertex set beyond $L_{0}$ (which is independent) and the
vertex $z_{t-1}$. Then, since $N_{G}(z_{t-1})\subseteq L_{0}$, this cycle is
suitable. Hence, $N_{G}(z_{t-1})\nsubseteq L_{0}$. Let $h\in
N_{G}(z_{t-1})\cap(G-L_{0})$. Then there is a path of length $k+1$ such that
the vertex set beyond this path is independent:
$z_{1}z_{2}...z_{t-2}z_{k}z_{k-1}z_{k-2}...z_{t}z_{t-1}h$ (see figure 3). This
is a contradiction to the suggestion that $L_{0}$ is the longest path such
that $V(G-L_{0})$ is independent.

Figure 3: $z_{t}\in A$ and $z_{t-2}\in B$ for some $t$,
$N_{G}(z_{t-1})\cap(G-L_{0})\neq\varnothing$.

Since the path $L_{0}$ is not Hamiltonian, $k<n$, and there exists a vertex
$y\notin L_{0}$. Since $V(G-L_{0})$ is independent, $N_{G}(y)\subset
V(L_{0})$. Let $\mu=|N_{G}(y)|$. Let $C$ be a set of all vertices $z_{t}$ such
that $z_{t+1}y\in E(G)$. Since $\delta(G)\geqslant\frac{n}{3}$,
$\mu\geqslant\frac{n}{3}$ and $|C|\geqslant\mu$ (because $z_{1}$ cannot be a
neighbour of $y$, otherwise the path $L_{0}$ can be obviously lengthened from
$z_{1}...z_{k}$ to $yz_{1}...z_{k}$ with maintaining the condition about
independence of the set of remaining vertices).

Note that $B\cap C=\varnothing$ (see figure 4).

Figure 4: If $z_{t}\in B\cap C$ then $z_{t+1}y,z_{t}z_{k}\in E(G)$. Then the
path (bold in the illustration) $z_{1}z_{2}...z_{t}z_{k}z_{k-1}...z_{t+1}y$
has length $k+1$, and the vertex set beyond this path is independent, a
contradiction to the choice of $L_{0}$.

Consequently, we proved the following:

1) $|A|\geqslant\frac{n}{3}$, $|B|\geqslant\frac{n}{3}$,
$|C|\geqslant\frac{n}{3}$.

2) $B\cap C=\varnothing$.

3) If $z_{t}\in A$ then $z_{t-2}\notin B$.

We say that $z_{t}$ is blocked if $z_{t+2}\in A$. It follows from the fact 3)
that $\\{\text{blocked vertices}\\}\cap B=\varnothing$. Also,
$\\{\text{blocked vertices}\\}\cap C=\varnothing$. Indeed, suppose that
$z_{t}$ is blocked and $z_{t}\in C$. Then $z_{t+1}y\in E(G)$ and
$z_{1}z_{t+2}\in E(G)$. Then the path
$yz_{t+1}z_{t}z_{t-1}...z_{1}z_{t+2}z_{t+3}...z_{k}$ is longer than the path
$L_{0}$, and the set of remaining vertices is independent (it is similar to
what happens in figure 4).

By definition, every vertex from $A$ (recall that $|A|\geqslant\frac{n}{3}$)
generates the blocked vertex except $z_{2}$ ($z_{1}\notin A$ because it is not
neighbour to itself). Therefore, there are at least $\frac{n}{3}-1$ blocked
vertices.

Thus, three sets {blocked vertices}, $B$, $C$ are pairwise disjoint and their
cardinalities are at least $\frac{n}{3}-1$, $\frac{n}{3}$, $\frac{n}{3}$
respectively. Since all these three sets are subsets of
$\\{z_{1},...,z_{k-1}\\}$ (obviously, $z_{k}\notin\\{\text{blocked
vertices}\\}\cup B\cup C$),
$k-1\geqslant\frac{n}{3}-1+\frac{n}{3}+\frac{n}{3}=n-1$. But $k<n$ because the
path $L_{0}$ is not Hamiltonian, a contradiction.

∎

By Claim 1, $G$ has a Hamiltonian path. Let us number path’s vertices in the
order of passing the path: $x_{1},x_{2},...,x_{n}$. As before, we say that
$x_{i}$ is on the right of $x_{j}$ if $i>j$ and $x_{i}$ is on the left of
$x_{j}$ if $i<j$. Since $d_{G}(x_{1})\geqslant\frac{n}{3}$, there exists an
index $i\geqslant\frac{n}{3}+1$ such that $x_{1}x_{i}\in E(G)$. Vertices
$x_{1}$, $x_{2}$, …, $x_{i}$ form a cycle (in this order of passing) and all
the remaining vertices $x_{i+1}$, $x_{i+2}$, …, $x_{n}$ form a path (in this
order of passing) (see figure 5). Hence, the graph $G$ contains a cycle of
length at least $\frac{n}{3}+1$ such that all the remaining vertices form a
path.

Figure 5: The graph $G$ has a cycle $x_{1}x_{2}...x_{i}$, all the remaining
vertices form a path $x_{i+1}x_{i+2}...x_{n}$. Figure 6: Vertices of the graph
$G$ are divided into 2 disjoint sets: the cycle $T$ and the path $H$.

Let $r$ be the largest integer such that there exists a cycle of length $r$
(let this cycle be $T$) such that all the remaining vertices form a path (let
this path be $H$). We proved that $r\geqslant\frac{n}{3}+1$. The cycle $T$ has
$r$ vertices, therefore the path $H$ has $n-r$ vertices and $n-r-1$ edges (see
figure 6).

######  Claim 2.

$r\geqslant\frac{n}{2}$.

###### Proof.

Assuming the converse, $r<\frac{n}{2}$. Let
$N_{G}(x_{1})=\\{x_{\alpha_{1}},...,x_{\alpha_{f}}\\}$ and
$N_{G}(x_{n})=\\{x_{\beta_{1}},...,x_{\beta_{g}}\\}$. Since
$\delta(G)\geqslant\frac{n}{3}$, $f\geqslant\frac{n}{3}$ and
$g\geqslant\frac{n}{3}$. Note that, for any $1\leqslant i\leqslant f$ and
$1\leqslant j\leqslant g$, property $\alpha_{i}-1\neq\beta_{j}+1$ holds
because otherwise there is a cycle of length $n-1$ (it contains all the
vertices except $x_{\alpha_{i}-1}=x_{\beta_{j}+1}$, that is:
$x_{1}x_{2}...x_{\beta_{j}}x_{n}...x_{\alpha_{i}}$). This cycle is suitable
because the vertex set beyond this cycle (that is, one vertex) is independent.
Also note that, for any $1\leqslant i\leqslant f$ and $1\leqslant j\leqslant
g$, inequalities $\alpha_{i}<\frac{n}{2}$ and $\beta_{j}>\frac{n}{2}$ hold
(otherwise there is a suitable cycle of length at least $\frac{n}{2}$ such
that all the remaining vertices form a path: $x_{1}x_{2}...x_{\alpha_{i}}$ or
$x_{\beta_{j}}x_{\beta_{j}+1}...x_{n}$). Consider the vertex
$x_{\lceil\frac{n}{2}\rceil}$. We proved that it is on the right of all the
neighbours of $x_{1}$ and it is on the left of all the neighbours of $x_{n}$.
Note that, for any $1\leqslant i\leqslant f$ and $1\leqslant j\leqslant g$,
properties $x_{\lceil\frac{n}{2}\rceil}x_{\alpha_{i}-1}\notin E(G)$ and
$x_{\lceil\frac{n}{2}\rceil}x_{\beta_{i}+1}\notin E(G)$ hold (otherwise there
is a cycle of length at least $\frac{n}{2}$ such that all the remaining
vertices form a path: see figures 7 a and 7 b respectively). Since all the
vertices $x_{\alpha_{i}-1}$ and $x_{\beta_{i}+1}$ are distinct,
$x_{\lceil\frac{n}{2}\rceil}$ is not adjacent to at least $\frac{2n}{3}$
distinct vertices and it is not adjacent to itself. Then, since $v(G)=n$,
$d_{G}(x_{\lceil\frac{n}{2}\rceil})\leqslant\frac{n}{3}-1$, contrary to
$\delta(G)\geqslant\frac{n}{3}$.

∎

Figure 7: If $x_{\lceil\frac{n}{2}\rceil}x_{\alpha_{i}-1}\in E(G)$ or
$x_{\lceil\frac{n}{2}\rceil}x_{\beta_{i}+1}\in E(G)$ then there is a cycle
(bold in the figure) of length at least $\frac{n}{2}$ such that all the
remaining vertices form a path.

Let us come back directly to the proof of Theorem 1 and consider 2 cases.

Case 1. There are 2 distinct vertices of the cycle $T$ such that the first
vertex is adjacent to some endpoint (let this endpoint be $a$) of the path $H$
and the second vertex is adjacent to the second endpoint (let this endpoint of
the path $H$ be $b$).

Let $\rho_{a}=|N_{G}(a)\cap V(T)\setminus N_{G}(b)|$, let vertices from
$N_{G}(a)\cap V(T)\setminus N_{G}(b)$ be a-vertices or vertices of type a. Let
$\rho_{b}=|N_{G}(b)\cap V(T)\setminus N_{G}(a)|$, let vertices from
$N_{G}(b)\cap V(T)\setminus N_{G}(a)$ be b-vertices or vertices of type b.
Also, let $\rho_{ab}=|N_{G}(a)\cap N_{G}(b)\cap V(T)|$, let vertices from
$N_{G}(a)\cap N_{G}(b)\cap V(T)$ be ab-vertices or vertices of type ab). Note
that every vertex of the cycle $T$ cannot pertain to 2 types simultaneously
but it can pertain to none of the types (if it is not adjacent to $a$ and
$b$). Note that two vertices of the same type cannot be neighbours in the
order of passing the cycle (otherwise the cycle can be lengthened by one of
the vertices $a$, $b$, and the remaining vertices form a path; or a
Hamiltonian cycle exists, see figure 8).

Figure 8: If an endpoint of $H$ ($b$ in this illustration) is adjacent to two
neighbours in the order of passing the cycle then the cycle $T$ may be
lengthened due to this endpoint and the remaining vertices form a path, a
contradiction to the choice of the cycle $T$.

Note that there are no 2 distinct vertices of the cycle $T$ with three
conditions:

1) first vertex is adjacent to $a$;

2) second vertex is adjacent to $b$;

3) the distance between these vertices by edges of the cycle $T$ is at most
$n-r$.

Assume the converse. Note that there is a cycle (it passes the edges of the
major half of the cycle $T$ between these vertices, endpoints of this section
are adjacent to $a$ and $b$, and it passes the path $H$, see figure 9) such
that the vertex set beyond this cycle forms a path and its cardinality is at
most $n-r-1$. Hence, there are at least $r+1$ vertices in this cycle, contrary
to the definition of $r$: we have found a cycle that satisfies all the
requirements of the cycle in the definition of $r$, but this cycle is larger
than the cycle $T$.

Figure 9: If one vertex of the cycle $T$ is adjacent to $a$, the other one is
adjacent to $b$ and the distance between them by edges of the cycle $T$ is at
most $n-r$ then there exists another cycle (bold in this figure), and its
existence is contrary to the definition of $r$.

Therefore, if there are 2 distinct vertices of different types (or both of
them have type $ab$) then the distance between them is at least $n-r+1$.

Case 1.1. The cycle T has neither a-vertices or b-vertices.

By the condition of the case 1.1, $\rho_{a}=\rho_{b}=0$. Then, by the
condition of the case 1, $\rho_{ab}\geqslant 2$.

The vertex $a$ is adjacent to $\rho_{ab}$ vertices of the cycle $T$ and it may
be adjacent to some vertices of the path $H$, not including itself.
Consequently, the vertex $a$ is adjacent to at most $\rho_{ab}+n-r-1$
vertices. Since $\delta(G)\geqslant\frac{n+2}{3}$,
$\rho_{ab}+n-r-1\geqslant\frac{n+2}{3}\Rightarrow\frac{2n-5}{3}+\rho_{ab}\geqslant
r$.

Since the distance between every $ab-$vertices by the edges of the cycle $T$
is at least $n-r+1$, the cycle $T$ contains at least $\rho_{ab}(n-r+1)$ edges.
Then, since the cycle $T$ has $r$ edges,
$r\geqslant\rho_{ab}(n-r+1)\Rightarrow(\rho_{ab}+1)r\geqslant\rho_{ab}(n+1)$.
By applying the estimate of $r$ from the previous paragraph, we obtain that

$(\rho_{ab}+1)(\frac{2n-5}{3}+\rho_{ab})\geqslant\rho_{ab}(n+1)\Rightarrow\frac{2n-5}{3}\rho_{ab}+\frac{2n-5}{3}+\rho_{ab}^{2}\geqslant
n\rho_{ab}\Rightarrow$

$\Rightarrow 3\rho_{ab}^{2}-5\rho_{ab}-5\geqslant(\rho_{ab}-2)n\textit{.}$

If $\rho_{ab}=2$ then this inequality does not hold. Therefore,
$\rho_{ab}\geqslant 3\Rightarrow\rho_{ab}-2>0$. Hence,

$3\rho_{ab}^{2}-5\rho_{ab}-5\geqslant(\rho_{ab}-2)n\Rightarrow\frac{3\rho_{ab}^{2}-5\rho_{ab}-5}{\rho_{ab}-2}\geqslant
n\textit{.}$

It is clear that

$3\rho_{ab}+1>\frac{3\rho_{ab}^{2}-5\rho_{ab}-5}{\rho_{ab}-2}\textit{.}$

Consequently,

$3\rho_{ab}+1>n\Rightarrow\rho_{ab}>\frac{n-1}{3}\textit{.}$

Recall that $r\geqslant\rho_{ab}(n-r+1)$. Note that $n-r+1\geqslant 0$ because
otherwise $r=n$, and the cycle $T$ is Hamiltonian and therefore suitable.
Then, since $\rho_{ab}>\frac{n-1}{3}$, we get that

$r>\frac{n-1}{3}(n-r+1)\textit{.}$

It is clear that $r\leqslant n$. Then $n-r+1>0$. If $n-r+1=1$ then $r=n$, and
hence the cycle $T$ is Hamiltonian and therefore suitable. If $n-r+1=2$ then
$r=n-1$, and hence the cycle $T$ does not contain only one vertex, so it is
suitable too. If $n-r+1\geqslant 3$ then $r>\frac{n-1}{3}(n-r+1)\Rightarrow
r>n-1$. Thus, this case is handled.

Case 1.2. The cycle $T$ contains an a-vertex or a b-vertex.

A section of type a or an a-section is a consecutive (in the order of passing
the cycle $T$) vertex set such that, firstly, it consists of all the vertices
between two a-vertices (hence, extreme vertices of an a-section are
a-vertices), secondly, it cannot be lengthened, thirdly, it does not include
vertices of other types (a-section can consist of one vertex). Sections of
type b or b-sections, sections of type ab or ab-sections have analogous
definitions. Edges of the cycle are naturally divided into at most 4 groups:
edges in a-sections, edges in b-sections, edges in ab-sections and edges
between 2 distinct sections. Let $\gamma_{a}$ be the number of $a-$sections,
let $\gamma_{b}$ be the number of $b-$sections, let $\gamma_{ab}$ be the
number of $ab-$sections. By the conditions of the cases 1 and 1.1, there are
at least 2 positive integers among three numbers $\rho_{a},\rho_{b},\rho_{ab}$
(respectively, there are at least 2 positive integers among three numbers
$\gamma_{a},\gamma_{b},\gamma_{ab}$). Hence,
$\gamma_{a}+\gamma_{b}+\gamma_{ab}\geqslant 2$. Consequently, the cycle $T$
does not consist of only one section.

It follows from the observation before the case 1.1 that there are at least
$n-r+1$ edges (in the order of passing the cycle $T$) between 2 distinct
sections. Also, there are at least $n-r+1$ edges (in the order of passing the
cycle $T$) between 2 distinct ab-vertices in an ab-section. Let us consider
all the edges of the cycle $T$ that does not constitute edges from a-sections
and b-sections. For this purpose, we fix some direction of the cycle $T$.
Walking around the cycle $T$ in this direction, there are at least $n-r+1$
edges between distinct sections after passing an a-section or a b-section.
Also, there are at least $n-r+1$ edges between distinct sections or in ab-
section after an ab-vertex. Thus, there are at least
$(n-r+1)(\rho_{ab}+\gamma_{a}+\gamma_{b})$ edges from the cycle $T$ that do
not constitute edges inside a-section or b-section.

Let us consider any a-section. Let it be $s$ a-vertices in this section. It is
clear that if $s=1$ then this section consists of at least $2s-2$ edges. Since
an a-vertex does not have a-vertices and b-vertices among its 2 neighbours in
the order of passing the cycle (figure 8 is dedicated to that), if $s\geqslant
2$ then this section has at least $2s-1$ edges. Hence, any $s$ a-section has
at least $2s-2$ edges. Therefore, there are at least $2\rho_{a}-2\gamma_{a}$
edges inside a-sections. Similarly, there are at least $2\rho_{b}-2\gamma_{b}$
edges inside b-sections. Hence, there are at least
$2(\rho_{a}+\rho_{b})-2(\gamma_{a}+\gamma_{b})$ edges inside a-sections and
b-sections.

Thus, there are at least
$(n-r+1)(\gamma_{a}+\gamma_{b}+\rho_{ab})+2(\rho_{a}+\rho_{b})-2(\gamma_{a}+\gamma_{b})$
edges in the cycle $T$. Since the cycle $T$ consists of $r$ edges, the
following inequality holds:

$r\geqslant(n-r+1)(\gamma_{a}+\gamma_{b}+\rho_{ab})+2(\rho_{a}+\rho_{b})-2(\gamma_{a}+\gamma_{b})\geqslant$

$\geqslant(n-r-2)(\gamma_{a}+\gamma_{b}+\rho_{ab})+2(\rho_{a}+\rho_{b})+3\rho_{ab}\textit{.}$

It follows from $\gamma_{a}+\gamma_{b}+\gamma_{ab}\geqslant 2$ and
$\rho_{ab}\geqslant\gamma_{ab}$ that $\gamma_{a}+\gamma_{b}+\rho_{ab}\geqslant
2$. Also, $n-r-2\geqslant 0$, because otherwise $r=n$ or $r=n-1$, these cases
are handled before the case 1.2. Consequently,

$r\geqslant 2(n-r-2)+2(\rho_{a}+\rho_{b})+3\rho_{ab}\Rightarrow 3r\geqslant
2(n-2)+2(\rho_{a}+\rho_{b})+3\rho_{ab}\Rightarrow$

$\Rightarrow
r\geqslant\frac{2}{3}(\rho_{a}+\rho_{b})+\frac{2}{3}n-\frac{4}{3}+\rho_{ab}\textit{.}$

The vertex $a$ has $\rho_{a}+\rho_{ab}$ neighbours among vertices of the cycle
$T$. Also, it can be adjacent to all the vertices of the path $H$ except
itself. Therefore, the vertex $a$ is adjacent to at most
$n-r-1+\rho_{a}+\rho_{ab}$ vertices. On the other hand,
$d_{G}(a)\geqslant\frac{n+2}{3}$. Therefore, $\frac{n+2}{3}\leqslant
n-r-1+\rho_{a}+\rho_{ab}$. The same is true for the vertex $b$. Hence,
$\frac{n+2}{3}\leqslant n-r-1+\rho_{b}+\rho_{ab}$. Consequently,
$\frac{n+2}{3}\leqslant n-r-1+min(\rho_{a},\rho_{b})+\rho_{ab}$. Thus,

$r\leqslant\frac{2n-5}{3}+min(\rho_{a},\rho_{b})+\rho_{ab}\textit{.}$

It follows from this and the previous inequalities that

$\frac{2n-5}{3}+min(\rho_{a},\rho_{b})+\rho_{ab}\geqslant\frac{2}{3}(\rho_{a}+\rho_{b})+\frac{2}{3}n-\frac{4}{3}+\rho_{ab}\Rightarrow$

$\Rightarrow
min(\rho_{a},\rho_{b})\geqslant\frac{2}{3}(\rho_{a}+\rho_{b})+\frac{1}{3}\textit{.}$

Then it follows from
$\frac{2}{3}(\rho_{a}+\rho_{b})\geqslant\frac{4}{3}min(\rho_{a},\rho_{b})$
that

$min(\rho_{a},\rho_{b})\geqslant\frac{4}{3}min(\rho_{a},\rho_{b})+\frac{1}{3}\Rightarrow
0\geqslant\frac{1}{3}min(\rho_{a},\rho_{b})+\frac{1}{3}\textit{.}$

This is impossible, a contradiction.

Case 2. There are no 2 distinct vertices of the cycle $T$ such that one of
them is adjacent to $a$ and the second vertex is adjacent to $b$.

In this case, one of the vertices $a$, $b$ has at most 1 neighbour among
vertices of the cycle $T$. Without loss of generality, $a$ has at most 1
neighbour among vertices of the cycle $T$. Since
$d_{G}(a)\geqslant\frac{n}{3}$, $a$ has at least $\frac{n}{3}-1$ neighbours
among vertices of the path $H$. Hence, the path $H$ contains (including $a$)
at least $\frac{n}{3}-1+1=\frac{n}{3}$ vertices. Then, since the path $H$ has
$n-r$ vertices,

$n-r\geqslant\frac{n}{3}\Rightarrow r\leqslant\frac{2n}{3}\textit{.}$ $None$

######  Claim 3.

a) Any endpoint of $H$ has at most $\frac{r}{3}$ neighbours among vertices of
the cycle $T$.

b) If the graph $G(H)$ is Hamiltonian then any vertex of the graph $G(H)$ has
at most $\frac{r}{3}$ neighbours among vertices of the cycle $T$.

###### Proof.

a) Firstly, let us prove that for the vertex $a$. Assuming the converse, $a$
has more than $\frac{r}{3}$ neighbours among vertices of the cycle $T$. Since
$a$ has at most one neighbour among vertices of the cycle $T$,
$1>\frac{r}{3}\Rightarrow r<3$. By Claim 2, $r\geqslant\frac{n}{2}$. Hence,
$3>\frac{n}{2}\Rightarrow n<6$, contrary to (1).

Figure 10: $b_{2}$ cannot be adjacent to some vertex of the path $H$, because
otherwise there is a cycle (bold in the illustration), and its existence is
contrary to the choice of the cycle $T$.

It remains to prove that for the vertex $b$. Let us consider $k_{b}$
neighbours of the vertex $b$ in the cycle $T$ (keeping terminology, they are
vertices of the type $b$ or b-vertices). Note that b-vertices cannot be
neighbours in the order of passing the cycle, because otherwise the cycle $T$
may be lengthened due to the vertex $b$, and the remaining vertices form a
path (this is illustrated in figure 8).

Assume that there are two b-vertices (we denote them by $b_{1}$ and $b_{3}$)
such that they have exactly one vertex (we denote it by $b_{2}$) between them
in the order of passing the cycle $T$. We proved that $bb_{2}\notin E(G)$.
Note that $e_{G}(b_{2},H)=0$, because otherwise there is a cycle that is
larger than $T$, and the remaining vertices form a path (see figure 10).
Hence, $N_{G}(b_{2})\subset T$. Note that if two neighbours of $b_{2}$ are
adjacent by the edge of the cycle $T$ then $b_{2}$ may be ’inserted’ between
these neighbours, and hence there is a cycle that includes all the vertices of
the cycle $T$ and the vertex $b$ (hence, it is larger than $T$), and the
vertex set beyond this cycle forms a path (see figure 11). Hence, there are no
two neighbours of $b_{2}$ that are neighbours in the order of passing the
cycle $T$. Since the cycle $T$ consists of $r-1$ vertices except $b_{2}$,
$b_{2}$ is adjacent to at most $\lceil\frac{r-1}{2}\rceil$ vertices. Thus,
$\lceil\frac{r-1}{2}\rceil\geqslant\frac{n+2}{3}\Rightarrow\frac{r}{2}\geqslant\frac{n+2}{3}\Rightarrow
r\geqslant\frac{2(n+2)}{3}$ because $d_{G}(b_{2})\geqslant\frac{n+2}{3}$. This
is a contradiction to (2).

Figure 11: If $b_{2}$ is adjacent to two vertices of the cycle $T$ that are
adjacent to each other by an edge of the cycle $T$ then there is a cycle (bold
in this figure), and its existence is contrary to the choice of the cycle $T$.

Therefore, there are no two b-vertices in the cycle $T$ that are adjacent to
each other by an edge of the cycle $T$ or have exactly one vertex between them
in the order of passing the cycle $T$. Consequently, $b$ has at most
$\frac{r}{3}$ neighbours among vertices of the cycle $T$ because $T$ has $r$
vertices.

b) If the graph $G(H)$ is Hamiltonian then any vertex of the path $H$ may be
an endpoint of some Hamiltonian path in the graph $G(V(H))$. Applying Claim 3
(item a) to this vertex and this Hamiltonian path, we obtain the desired
property.

∎

Figure 12: The path $H$ and the vertex $c$ form a cycle (bold in this
illustration) such that the vertex set beyond this cycle forms a path.

######  Claim 4.

$G(V(H))$ has a Hamiltonian cycle.

###### Proof.

Let us consider 2 cases.

Case a: $e_{G}(a,T)\geqslant 1$ and $e_{G}(b,T)\geqslant 1$.

By the condition of the case 2, $e_{G}(a,T)=1$, $e_{G}(b,T)=1$ and
$|N_{G}(\\{a,b\\})\cap T|=1$. Let $\\{c\\}=N_{G}(\\{a,b\\})\cap T$, $ca,cb\in
E(G)$. Consider subgraph $G(H)$. Since $a$ and $b$ have one neighbour in the
cycle $T$, $d_{G(H)}(a)\geqslant\frac{n}{3}-1$,
$d_{G(H)}(b)\geqslant\frac{n}{3}-1$. The graph $G(H)$ has a Hamiltonian path
$H$. Applying Lemma 1 to the path $H$ that has $n-r$ vertices: if
$d_{G(H)}(a)+d_{G(H)}(b)\geqslant n-r$ then graph $G(H)$ has a Hamiltonian
cycle (this is the desired property). Otherwise,
$n-r>d_{G(H)}(a)+d_{G(H)}(b)\geqslant\frac{n}{3}-1+\frac{n}{3}-1=\frac{2n}{3}-2\Rightarrow
r<\frac{n}{3}+2$. Note that the path $H$ and the vertex $c$ form a cycle on
$n-r+1$ vertices such that the vertex set beyond this cycle forms a path (see
figure 12). Then, by the definition of $r$, the following holds: $r\geqslant
n-r+1\Rightarrow r\geqslant\frac{n+1}{2}$. If $r>\frac{n+1}{2}$ then
$r\geqslant\frac{n}{2}+1$. Then it follows from $r<\frac{n}{3}+2$ that
$\frac{n}{3}+2>\frac{n}{2}+1\Rightarrow n<6$, a contradiction to (1).
Consequently, $r=\frac{n+1}{2}$. Then $n$ is odd, and since $r<\frac{n}{3}+2$,
we have that $\frac{n}{3}+2>\frac{n+1}{2}\Rightarrow n<9$. Since $n$ is odd
and (1) holds, $n=7$, $r=\frac{n+1}{2}=4$. It follows from the previous
observations that the graph has two cycles (let them be $T_{1}$ and $T_{2}$)
on 4 vertices that have common vertex $c$. And there is no such a cycle on 5
vertices that the remaining 2 vertices are adjacent to each other (moreover,
there is no such a cycle on 5 vertices that the remaining 2 vertices are not
adjacent, because otherwise this cycle meets all the requirements). Therefore,
$G$ does not have a cycle on 5 vertices. Since $G$ is 2-connected, $G-\\{c\\}$
is connected. Hence, there is an edge $c_{1}c_{2}\in E(G)$ for some $c_{1}\in
V(T_{1})\setminus\\{c\\}$ and $c_{2}\in V(T_{2})\setminus\\{c\\}$ (see figure
13). Since $T_{1}$ and $T_{2}$ are cycles and $|T_{1}|=|T_{2}|=4$, there exist
paths from $c_{1}$ and $c_{2}$ to $c$ whose lengths are at least 2 and these
paths pass the edges of the cycles $T_{1}$ and $T_{2}$ respectively.
Concatenation of these paths and the edge $c_{1}c_{2}$ form a cycle whose size
is at least 5. Since the graph does not have a cycle of size 5, this cycle’s
size is 6 or 7. Hence, it is Hamiltonian or this cycle contains all the
vertices except one and hence it is suitable.

Case b: $e_{G}(a,T)=0$ or $e_{G}(b,T)=0$.

Figure 13: $n=7$.

Without loss of generality, $e_{G}(a,T)=0$. Keeping previous notations, let
$k_{b}$ be the number of neighbours of $b$ in the cycle $T$. Consider $G(H)$.
Since the vertex $a$ does not have neighbours among vertices of the cycle $T$
and the vertex $b$ have $k_{b}$ such neighbours,
$d_{G(H)}(a)\geqslant\frac{n}{3}$ and $d_{G(H)}(b)\geqslant\frac{n}{3}-k_{b}$.
The graph $G(H)$ contains a Hamiltonian path $H$. Recall that $|V(H)|=n-r$.
Applying Lemma 1 to the path $H$: if $d_{G(H)}(a)+d_{G(H)}(b)\geqslant n-r$
then the graph $G(H)$ is Hamiltonian (that is the desired property).
Consequently,
$n-r>d_{G(H)}(a)+d_{G(H)}(b)\geqslant\frac{n}{3}+\frac{n}{3}-k_{b}=\frac{2n}{3}-k_{b}\Rightarrow
k_{b}>r-\frac{n}{3}$. By Claim 3 (item a), $k_{b}\leqslant\frac{r}{3}$. Thus,
the following inequalities are deduced: $k_{b}\leqslant\frac{r}{3}$ and
$k_{b}>r-\frac{n}{3}\Rightarrow\frac{r}{3}>r-\frac{n}{3}\Rightarrow n>2r$,
contrary to Claim 2.

∎

By Claim 4, $G(V(H))$ has a Hamiltonian cycle. From now on we will call $H$ a
cycle.

Consider all pairs $(p,q)$ of distinct vertices of the cycle $H$ such that
$pp_{0},qq_{0}\in E(G)$ for some distinct $p_{0},q_{0}\in V(T)$ (there exist
such pairs or a pair of vertices because $G$ is 2-connected). Let us fix a
pair $(p,q)$ such that the distance between $p$ and $q$ by the edges of the
cycle $H$ is the shortest among such pairs. Let $p_{0},q_{0}\in V(T)$ be
distinct ($p_{0}\neq q_{0}$) neighbours of $p$ and $q$ respectively.

Let $H_{1}$ and $H_{2}$ be two sections of the cycle $T$ between $p$ and $q$
(see figure 14). Without loss of generality, $|V(H_{1})|\leqslant|V(H_{2})|$.
Note that, for any vertex $f\in V(H_{1})$, inequality
$d_{G(V(H))}(f)\geqslant\frac{n}{3}$ holds. Indeed, assume the converse. Since
$d_{G}(f)\geqslant\frac{n}{3}$, $f$ has a neighbour (let it be $f_{1}$) in
$V(T)$. Recall that $p_{0}\neq q_{0}$. Without loss of generality, $f_{1}\neq
p_{0}$. Then $f$ and $p$ have two distinct neighbours in $T$, and the path
between $f$ and $p$ by the edges of the cycle $H$ is shorter then the similar
path between $p$ and $q$, contrary to the choice of $p$ and $q$.

Figure 14: Partition of the cycle $H$ into $H_{1}$ and $H_{2}$; edges $pp_{0}$
and $qq_{0}$, where $p_{0}$ and $q_{0}$ are distinct vertices of the cycle
$T$.

######  Claim 5.

The graph $G(V(H))$ has a Hamiltonian path with endpoints $p$ and $q$.

###### Proof.

Consider the longest path with endpoints $p$ and $q$ (let it be $L_{2}$ and
let it be $\eta$ vertices in it) among all such paths that if some vertex
$d\in V(H)$ does not belong to this path then
$d_{G(V(H))}(d)\geqslant\frac{n}{3}$, and all the vertices of the cycle $H$,
which do not belong to this path, form a path (let this path be $L_{1}$ with
endpoints $p_{1}$ and $q_{1}$). Such a path $L_{2}$ exists, because it follows
from the proved before that the path $pH_{2}q$ is suitable (it has at least
$\frac{n-r}{2}+1$ vertices and hence $\eta\geqslant\frac{n-r}{2}+1$). Assuming
the converse, let $L_{2}$ be not a Hamiltonian path. Then the path $L_{1}$
contains $n-r-\eta\geqslant 1$ vertices. By the condition on $L_{2}$,
$d_{G(V(H))}(p_{1})\geqslant\frac{n}{3}$. Therefore, there are at least
$\frac{n}{3}-(n-r-\eta-1)=r+\eta+1-\frac{2n}{3}$ neighbours of the vertex
$p_{1}$ among vertices of the path $L_{2}$. Note that neighbours of the vertex
$p_{1}$ cannot be neighbours in the order of passing the path $L_{2}$
(otherwise, the vertex $p_{1}$ can be ’inserted’ between these neighbours into
the path $L_{2}$ (see figure 15), and then the path $L_{2}$ is longer, and all
the remaining vertices form a path, and their degrees in $G(V(H))$ are at
least $\frac{n}{3}$, contrary to the choice of the path $L_{2}$). Thus,
$\eta\geqslant
2(r+\eta+1-\frac{2n}{3})-1\Rightarrow\eta\leqslant\frac{4n}{3}-2r-1$.

Figure 15: Partition of the cycle $H$ into two paths: $L_{1}$ and $L_{2}$.
Demonstration that $p_{1}$ cannot have two consecutive (in the order of
passing the path $L_{2}$) neighbours in $L_{2}$.

We need to prove that $G(V(L_{1}))$ has a Hamiltonian cycle. Assuming the
converse, $G(V(L_{1}))$ does not have a Hamiltonian cycle. Firstly, let us
consider the case, where $L_{1}$ contains at least 3 vertices. Since it has
$n-r-\eta$ vertices and $L_{1}$ is a path, by Lemma 1,
$d_{G(L_{1})}(p_{1})+d_{G(L_{1})}(q_{1})<n-r-\eta$. Without loss of
generality, $d_{G(L_{1})}(p_{1})<\frac{n-r-\eta}{2}$. Then there are at least
$\frac{n}{3}-\frac{n-r-\eta-1}{2}=\frac{r+\eta+1}{2}-\frac{n}{6}$ neighbours
of the vertex $p_{1}$ among vertices of the path $L_{2}$. Recall that (see
figure 15) neighbours of $p_{1}$ cannot be neighbours in the order of passing
the path $L_{2}$, and hence $\eta\geqslant
2(\frac{r+\eta+1}{2}-\frac{n}{6})-1\Rightarrow\eta\geqslant
r+\eta-\frac{n}{3}\Rightarrow\frac{n}{3}\geqslant r$, contrary to Claim 2.

So, it remains to consider the case, where $L_{1}$ consists of one vertex or
two vertices. Then $\eta\geqslant n-r-2$, and since
$\eta\leqslant\frac{4n}{3}-2r-1$, we have that $\frac{4n}{3}-2r-1\geqslant
n-r-2\Rightarrow r\leqslant\frac{n}{3}+1$. By Claim 2,
$r\geqslant\frac{n}{2}$. Then $\frac{n}{3}+1\geqslant\frac{n}{2}\Rightarrow
n\leqslant 6$. Then, by (1), $n=6$, and hence all the inequalities in this
paragraph are actually equalities. Thus, $n=6$, $r=\frac{n}{2}=3$,
$\eta=n-r-2=1$. But $\eta\geqslant 2$ because $L_{2}$ includes distinct
vertices $p$ and $q$, a contradiction.

Consequently, $G(V(L_{1}))$ has a Hamiltonian cycle. From now on we will call
$L_{1}$ a cycle.

Figure 16: For each neighbour of $p_{1}$ we mark the following two vertices in
accordance with the fixed order of passing the path $L_{2}$.

We need to prove that there exist 2 vertices of the path $L_{2}$ such that one
of them is adjacent to $p_{1}$, the other one is adjacent to $q_{1}$, and they
are neighbours in the path $L_{2}$ or they have exactly one vertex between
them in the order of passing the path $L_{2}$. Assuming the converse, they do
not exist. We fix some direction of the path $L_{2}$ (for instance, from $p$
to $q$). Recall that there are at least $r+\eta+1-\frac{2n}{3}$ neighbours of
$p_{1}$ among vertices of the path $L_{2}$. For each of them, we mark the
following two vertices in accordance with the fixed order of passing the path
$L_{2}$ (see figure 16). Since it is proved (figure 15 is dedicated to that)
that all the neighbours of the vertex $p_{1}$ are not neighbours in the order
of passing the path $L_{2}$, no vertex is marked twice. Hence, there are at
least $2(r+\eta+1-\frac{2n}{3}-1)$ marked vertices (for $q$ we do not mark
anything, and hence we lose two vertices, and for the neighbour of $q$ in the
path $L_{2}$ we mark only one vertex, and hence we lose one vertex, and
therefore we lose at most two vertices because $q$ and the neighbour of $q$ in
the path $L_{2}$ cannot be neighbours of the vertex $p_{1}$ simultaneously).
Since we assumed the converse, all the neighbours of $q_{1}$ in the path
$L_{2}$ (there are at least $r+\eta+1-\frac{2n}{3}$ such neighbours) cannot be
marked. Thus,

$\eta\geqslant r+\eta+1-\frac{2n}{3}+2(r+\eta+1-\frac{2n}{3}-1)\Rightarrow$

$\Rightarrow 0\geqslant r+1-\frac{2n}{3}+2r+2\eta-\frac{4n}{3}\Rightarrow
2n\geqslant 3r+2\eta+1\textit{.}$

Since $\eta\geqslant\frac{n-r}{2}+1$, we have $2n\geqslant
3r+n-r+2+1\Rightarrow n\geqslant 2r+3\Rightarrow r<\frac{n}{2}$, contrary to
Claim 2.

Figure 17: There is a Hamiltonian path in $G(V(H))$ with endpoints $p$ and $q$
if $y_{1}$ and $y_{2}$ are neighbours in the order of passing the path
$L_{2}$.

Consequently, there exist 2 vertices of the path $L_{2}$ such that one of them
is adjacent to $p_{1}$, the other one is adjacent to $q_{1}$ and they are
neighbours in the path $L_{2}$ or they have exactly one vertex between them in
the order of passing the path $L_{2}$. Let them be $y_{1}$ and $y_{2}$, let
$y_{1}$ be closer to the vertex $p$ in the order of passing the path $L_{2}$,
and $y_{2}$ \- closer to $q$, and, without loss of generality, let $y_{1}$ be
adjacent to $p_{1}$, $y_{2}$ be adjacent to $q_{1}$. If $y_{1}$ and $y_{2}$
are neighbours in the order of passing of the path $L_{2}$ then there exists a
Hamiltonian path in $V(H)$ with endpoints $p$ and $q$ (see figure 17).

Therefore, there is a vertex (we denote it by $z$) between $y_{1}$ and $y_{2}$
in the path $L_{2}$. Since $z$ is a neighbour of both $y_{1}$ and $y_{2}$, as
it was already mentioned (figure 15 is dedicated to that),
$e_{G}(z,\\{p_{1},q_{1}\\})=0$. Assume that $e_{G}(z,L_{1})\geqslant 1$. Then
note that there is a path with endpoints $p$ and $q$ such that this path
includes $V(L_{2})$ and at least one another vertex (it passes the path
$L_{2}$ from $p$ to $z$, then it enters the cycle $L_{1}$, passes the edges of
the cycle $L_{1}$ to the vertex $q_{1}$, goes to the vertex $y_{2}$ and then
passes the edges of the path $L_{2}$ to the vertex $q$, see figure 18), a
contradiction to the choice of the cycle $L_{2}$.

Figure 18: If $z$ has a neighbor from the cycle $L_{1}$ then there is a path
(marked in bold) from $p$ to $q$ whose existence is contrary to the choice of
$L_{2}$.

Hence, $e_{G}(z,L_{1})=0$. Suppose, $z$ has two consecutive neighbours in the
order of passing the path $L_{2}$. Then there is the following Hamiltonian
path in $V(H)$ with endpoints $p$ and $q$: it goes from $p$ to $y_{1}$ by the
edges of the path $L_{2}$, it passes the edge $y_{1}p_{1}$, then it goes by
the edges of the path $L_{1}$ to $q_{1}$, after that it enters the vertex
$y_{2}$, and then it goes to $q$ by the edges of the path $L_{2}$ and, in so
doing, we insert $z$ somewhere in this path between these neighbours (see
figure 19).

Thus, $z$ does not have two consecutive neighbours in the order of passing the
path $L_{2}$. Let it be $\tau_{1}$ vertices in the path $L_{2}$ between $p$
and $y_{1}$ (first section of the path $L_{2}$) and let it be $\tau_{2}$
vertices in the path $L_{2}$ between $y_{2}$ and $q$ (second section of the
path $L_{2}$). Then $\tau_{1}+\tau_{2}=\eta-1$. Since the vertex $z$ does not
have two consecutive neighbours among vertices of the path $L_{2}$ in the
order of passing the path $L_{2}$, it has at most $\frac{\tau_{1}+1}{2}$
neighbours in the first section and at most $\frac{\tau_{2}+1}{2}$ neighbours
in the second section. Therefore, it has at most
$\frac{\tau_{1}+1}{2}+\frac{\tau_{2}+1}{2}=1+\frac{\tau_{1}+\tau_{2}}{2}=1+\frac{\eta-1}{2}=\frac{\eta+1}{2}$
neighbours among vertices of the path $L_{2}$.

Figure 19: If $z$ has two consecutive neighbours in the order of passing the
path $L_{2}$ then there is a Hamiltonian path in $V(H)$ (marked in bold).

By Claim 3 (item b), $z$ has at most $\frac{r}{3}$ neighbours in the cycle
$T$. Consequently, $d_{G}(z)\leqslant\frac{\eta+1}{2}+\frac{r}{3}$. Then it
follows from $d_{G}(z)\geqslant\frac{n+2}{3}$ that
$\frac{n+2}{3}\leqslant\frac{\eta+1}{2}+\frac{r}{3}\Rightarrow 2n+4\leqslant
3\eta+3+2r\Rightarrow\eta\geqslant\frac{2n}{3}+\frac{1}{3}-\frac{2r}{3}$.
Since $\eta\leqslant\frac{4n}{3}-2r-1$, we have that
$\frac{4n}{3}-2r-1\geqslant\frac{2n}{3}+\frac{1}{3}-\frac{2r}{3}\Rightarrow\frac{2n}{3}-\frac{4}{3}\geqslant\frac{4r}{3}\Rightarrow\frac{n}{2}>r$,
contrary to Claim 2.

∎

Finally, by Claim 5, there is a Hamiltonian path (we denote it by $H_{0}$) in
the graph $G(V(H))$ with endpoints $p$ and $q$. Then there is a cycle: the
path $H_{0}$, the edges $pp_{0}$ and $qq_{0}$ and the major half of the cycle
$T$ between $p_{0}$ and $q_{0}$ (see figure 20). The length of this cycle is
at least $\frac{r}{2}+2+n-r-1=n-\frac{r}{2}+1$ (2 edges $pp_{0}$, $qq_{0}$ and
the major half of the cycle $T$ have at least $\frac{r}{2}+2$ edges and the
Hamiltonian path in the graph $G(V(H))$; since there are exactly $n-r$
vertices, there are $n-r-1$ edges in this path). Note that this is a cycle
such that all other vertices beyond this cycle are one of the halves of the
cycle $T$, that is, they form a path. Then it follows from the choice of the
cycle $T$ that the following must be true: $r\geqslant
n-\frac{r}{2}+1\Rightarrow\frac{3r}{2}>n\Rightarrow r>\frac{2n}{3}$, contrary
to (2). ∎

Figure 20: If there is a Hamiltonian path $H_{0}$ in the graph $G(V(H))$ with
endpoints $p$ and $q$ then there is a cycle whose existence is contrary to the
choice of $T$.

3 Our estimate cannot be improved

######  Claim 6.

Our result is best possible in the sense that it becomes false if
$\frac{n+2}{3}$ is replaced by any smaller number. More specifically, for any
$n\geqslant 8$ and for any $2<\nu<\frac{n+2}{3}$, there exists a 2-connected
graph $G$ such that $v(G)=n$, $\delta(G)=\nu$ and in which there is no a cycle
such that the vertex set beyond this cycle is independent.

###### Proof.

Figure 21: Our example for $n=8$, $\nu=3$.

Let us take some 2 vertices, call them $f_{1}$ and $f_{2}$ and divide the
remaining vertices into 3 groups: the first two groups contain exactly $\nu-1$
vertices (let them be $A_{1}$ and $A_{2}$), and the third has $n-2\nu$
vertices (let it be $A_{3}$). There are such edges in this graph: any two
vertices in the same group are adjacent to each other, any two vertices in
distinct groups are not adjacent to each other, and the vertices $f_{1}$ and
$f_{2}$ are adjacent to all vertices, but not to each other (see figure 21).
Note that $\delta(G)=\nu$. Indeed, if $v\in A_{1}\cup A_{2}$ then
$d_{G}(v)=\nu$, $d_{G}(f_{1})=d_{G}(f_{2})=n-2\geqslant\nu$ (since $n\geqslant
3$, $n-2\geqslant\frac{n}{3}>\nu$), and if $v\in A_{3}$ then
$d_{G}(v)=n-2\nu+1\geqslant\nu$.

Let us show that this graph is 2-connected. It is sufficient to show that
$G-\\{v\\}$ is connected for any $v\in V(G)$. Without loss of generality,
$v\neq f_{1}$. Clearly, $G-\\{v\\}$ is connected because all vertices in
$(G-\\{v\\})\setminus\\{f_{2}\\}$ are adjacent to $f_{1}$, and $f_{2}$ is
adjacent to all vertices in $G\setminus\\{v_{1}\\}$.

It remains to prove that there is no a cycle in this graph such that the
vertex set beyond this cycle is independent. Assuming the converse, there
exists such a cycle. Then note that it must contain some vertices from all
groups $A_{1}$, $A_{2}$, $A_{3}$ (otherwise, some entire group is not
contained in the cycle, but any group has edges because $A_{1}$ and $A_{2}$
have $\nu-1>1$ vertices, $A_{3}$ has $n-2\nu>1$ vertices). Thus, this cycle
has vertices from all three groups. But, when this cycle goes from one group
to another group, it must visit one of the vertices $f_{1}$, $f_{2}$. There
are 3 groups $A_{1}$, $A_{2}$, $A_{3}$ and 2 vertices $f_{1}$, $f_{2}$, a
contradiction.

∎

## References

  * [1] J. A. Bondy, U. S. R. Murty. Graph Theory With Applications. Elsevier Science, 1976.
  * [2] G. Chartrand, S. F. Kapoor. The cube of every connected graph is 1-Hamiltonian. J. Res. Nat. Bur. Standards Sect. B 73 (1969), 47-48.
  * [3] R. Diestel. Graph Theory. Springer, 1997-2016 (editions 1-5).
  * [4] N. Linial. A lower bound on the circumference of a graph. Discrete Math. v.15 (1976) p.297-300.
  * [5] C. Thomassen. A theorem on paths in planar graphs. Journal of Graph Theory, Vol.7 (1983) 169-176.