# Energy Conditions for Hamiltonicity of Graphs

Authors: Guidong Yu; Gaixiang Cai; Miaolin Ye; Jinde Cao
Journal: Discrete Dynamics in Nature and Society
 (2014)

---

## Abstract

LetG be an undirected simple graph of order n. Let A
(
G
) be the adjacency matrix of G, and let μ
1
(
G
)
≤
μ
2
(
G
)
≤
⋯
≤
μ
n
(
G
) be its eigenvalues. The energy of G is defined as ℰ
(
G
)
=
∑
i
=
1
n
‍
|
μ
i
(
G
)
|. Denote by G
BPT a bipartite graph. In this paper, we establish the sufficient conditions for G having a Hamiltonian path or cycle or to be Hamilton-connected in terms of the energy of the complement of G, and give the sufficient condition for G
BPT having a Hamiltonian cycle in terms of the energy of the quasi-complement of G
BPT.


---

## Body

## 1. Introduction

We consider only undirected simple graphs. LetG
=
(
V
,
E
) be a graph of order n with vertex set V
=
V
(
G
)
=
{
v
1
,
v
2
,
…
,
v
n
} and edge set E
=
E
(
G
). We denote by e
(
G
) the number of edges of G. Thecomplement of G is denoted by G
c
:
=
(
V
,
E
c
), where E
c
:
=
{
x
y
:
x
∈
V, y
∈
V, x
≠
y, x
y
∉
E
}. For a bipartite graph G
BPT
=
(
X
,
Y
;
E
), thequasi-complement of G
BPT is denoted by G
BPT
*
:
=
(
X
,
Y
;
E
′
), where E
′
=
{
x
y
:
x
∈
X, y
∈
Y, x
y
∉
E
}.The degree matrix ofG is denoted by D
(
G
)
=
diag
⁡
(
d
G
(
v
1
)
,
d
G
(
v
2
)
,
…
,
d
G
(
v
n
)
), where d
G
(
v
) denotes the degree of a vertex v in the graph G. We denote by Δ
(
G
) the maximum degree of G. Theadjacency matrix of G is defined by the matrix A
(
G
)
=
[
a
i
j
] of order n, where a
i
j
=
1 if v
i is adjacent to v
j and a
i
j
=
0 otherwise. Thesignless Laplacian matrix of G is defined to be Q
(
G
)
=
D
(
G
)
+
A
(
G
). TheLaplacian matrix of G is defined to be L
(
G
)
=
D
(
G
)
-
A
(
G
). In addition, if the graph G has no isolated vertices, thenormalized Laplacian matrix is defined by ℒ
(
G
)
=
D
(
G
)
-
1
/
2
L
(
G
)
D
(
G
)
-
1
/
2. Obviously, A
(
G
), Q
(
G
), L
(
G
), and ℒ
(
G
) are real symmetric matrix. So their eigenvalues are real numbers and can be ordered. The largest eigenvalue of A
(
G
), denoted by μ
(
G
), is said to be the spectral radius of G. The largest eigenvalue of Q
(
G
), denoted by q
(
G
), is said to be the signless Laplacian spectral radius of G. Let μ
1
(
G
)
≤
μ
2
(
G
)
≤
⋯
≤
μ
n
(
G
) be the eigenvalues of A
(
G
). The energy of G is defined as ℰ
(
G
)
=
∑
i
=
1
n
‍
|
μ
i
(
G
)
|.LetG be a graph of order n. AHamiltonian cycle of G is a cycle of order n contained in G. AHamiltonian path of G is a path of order n contained in G. If G contains Hamiltonian cycles, it is said to beHamiltonian. If every two vertices of G are connected by a Hamiltonian path, it is said to beHamilton-connected. Deciding whether a graph is Hamiltonian is one of the most difficult classical problems in graph theory. Indeed, it is NP-complete.Lately, the spectral theory of graphs has been wielded to this problem. Fiedler and Nikiforov [1] present some sufficient conditions for a graph having a Hamiltonian path (or cycle) in terms of the spectral radius of the graph or its complements. Zhou [2] studies the signless Laplacian spectral radius of the complements of a graph and gives conditions for the existence of Hamiltonian path or cycle. Li [3] establishes sufficient conditions for a graph having Hamiltonian path or cycle in terms of the energy of the graph. Lu et al. [4] give sufficient conditions for a bipartite graph having Hamiltonian cycles in terms of the spectral radius of the graph. Those results imply that the graphs under discussion should be dense or have two many edges.For a sparse graphG of order n, Butler and Chung [5] show that if the nontrivial eigenvalues of the Laplacian matrix of G are sufficiently close to the average degree of G for sufficiently large n, then G is Hamiltonian. Fan and Yu [6] get that if the nontrivial eigenvalues of the normalized Laplacian matrix of G are sufficiently close to 1 for sufficiently large n, then G is Hamiltonian.In this paper, we still study the Hamiltonicity of a dense graph. We provide some sufficient conditions for a graph having a Hamiltonian path or cycle or to be Hamilton-connected in terms of the energy of the complement of the graph (maybe considered as a sparse graph) and present the sufficient conditions for a graph having a Hamiltonian cycle in terms of the energy of the quasi-complement of a bipartite graph. We get the following results, whose proofs are provided in Sections3 and 4.Theorem 1.
LetG be a graph of order n
≥
3. Then(i)
G contains a Hamiltonian path, if
(1)
ℰ
(
G
c
)
>
2
e
(
G
c
)
-
n
+
2
-
Δ
(
G
c
)
+
(
n
-
1
)
(
2
e
(
G
c
)
-
(
n
-
Δ
(
G
c
)
)
2
)
,
andn
-
2
e
(
G
c
)
≤
Δ
(
G
c
)
≤
n
-
n
-
1,
(ii)
G contains a Hamiltonian cycle, if
(2)
ℰ
(
G
c
)
>
2
e
(
G
c
)
-
n
+
3
-
Δ
(
G
c
)
+
(
n
-
1
)
(
2
e
(
G
c
)
-
(
n
-
1
-
Δ
(
G
c
)
)
2
)
,
andn
-
1
-
2
e
(
G
c
)
≤
Δ
(
G
c
)
≤
n
-
1
-
n
-
1,
(iii)
G is Hamilton-connected, if
(3)
ℰ
(
G
c
)
>
2
e
(
G
c
)
-
n
+
4
-
Δ
(
G
c
)
+
(
n
-
1
)
(
2
e
(
G
c
)
-
(
n
-
2
-
Δ
(
G
c
)
)
2
)
,
andn
-
2
-
2
e
(
G
c
)
≤
Δ
(
G
c
)
≤
n
-
2
-
n
-
1.Theorem 2.
LetG
B
P
T
=
(
X
,
Y
;
E
) be a bipartite graph of order n
=
2
r
≥
4, where |
X
|
=
|
Y
|
=
r
≥
2. Then G
B
P
T contains a Hamiltonian cycle, if
(4)
ℰ
(
G
B
P
T
*
)
>
2
e
(
G
B
P
T
*
)
+
2
-
2
Δ
(
G
B
P
T
*
)
+
(
n
-
2
)
(
2
e
(
G
B
P
T
*
)
-
2
(
r
-
Δ
(
G
B
P
T
*
)
)
2
)
,
and r
-
e
(
G
B
P
T
*
)
≤
Δ
(
G
B
P
T
*
)
≤
r
-
r.Li [3] has given some energy conditions for a graph having Hamiltonian paths or cycles as follows.Theorem 3 (see [3]).
LetG be a graph of order n(≥4). Then(i)
G contains a Hamiltonian path, if ℰ
(
G
c
)
>
2
e
(
G
c
)
-
2
n
+
2
+
e
(
G
c
)
(
n
-
1
+
1
),
(ii)
G contains a Hamiltonian cycle, if ℰ
(
G
c
)
>
2
e
(
G
c
)
-
2
n
+
4
+
(
n
-
1
)
e
(
G
c
)
/
n
(
n
+
1
+
1
).Theorem 4 (see [3]).
LetG
B
P
T
=
(
X
,
Y
;
E
) be a bipartite graph of order n
=
2
r
≥
4, where |
X
|
=
|
Y
|
=
r
≥
2. Then G
B
P
T contains a Hamiltonian cycle, if
(5)
ℰ
(
G
B
P
T
*
)
>
2
e
(
G
B
P
T
*
)
-
2
r
+
2
+
e
(
G
B
P
T
*
)
(
n
-
2
+
2
)
.Remark 5.
We now compare Theorems1 and 3, Theorems 2 and 4, respectively.
Firstly, we consider the functionf
(
x
)
=
x
+
(
n
-
1
)
(
2
e
(
G
c
)
-
x
2
). If 2
e
(
G
c
)
/
n
<
x
<
2
e
(
G
c
),
(6)
f
′
(
x
)
=
1
+
-
(
n
-
1
)
x
(
n
-
1
)
(
2
e
(
G
c
)
-
x
2
)
<
0
.
So, f
(
x
) is monotonously decreasing when 2
e
(
G
c
)
/
n
<
x
≤
2
e
(
G
c
). We notice that if n
-
2
e
(
G
c
)
≤
Δ
(
G
c
)
≤
n
/
2, n
≥
3, we have
(7)
2
e
(
G
c
)
n
<
e
(
G
c
)
≤
n
Δ
(
G
c
)
2
≤
n
-
Δ
(
G
c
)
≤
2
e
(
G
c
)
,
and Δ
(
G
c
)
≤
n
-
n
-
1. Hence, when n
-
2
e
(
G
c
)
≤
Δ
(
G
c
)
≤
n
/
2, n
≥
3, we have
(8)
2
e
(
G
c
)
-
2
n
+
2
+
e
(
G
c
)
(
n
-
1
+
1
)
=
2
e
(
G
c
)
-
2
n
+
2
+
f
(
e
(
G
c
)
)
≥
2
e
(
G
c
)
-
2
n
+
2
+
f
(
n
-
Δ
(
G
c
)
)
=
2
e
(
G
c
)
-
n
+
2
-
Δ
(
G
c
)
+
(
n
-
1
)
(
2
e
(
G
c
)
-
(
n
-
Δ
(
G
c
)
)
2
)
.
So Theorem 1(i) improves Theorem 3(i), when n
-
2
e
(
G
c
)
≤
Δ
(
G
c
)
≤
n
/
2. By a similar discussion, we have that Theorem 1(ii) improves Theorem 3(ii), when n
-
1
-
2
e
(
G
c
)
≤
Δ
(
G
c
)
≤
(
n
-
1
)
/
2.
Secondly, we consider the functiong
(
x
)
=
2
x
+
(
n
-
2
)
(
2
e
(
G
BPT
*
)
-
2
x
2
). If 2
e
(
G
BPT
*
)
/
n
<
x
<
e
(
G
BPT
*
),
(9)
g
′
(
x
)
=
2
+
-
2
(
n
-
2
)
x
(
n
-
2
)
(
2
e
(
G
BPT
*
)
-
2
x
2
)
<
0
.
So, g
(
x
) is monotonously decreasing when 2
e
(
G
BPT
*
)
/
n
<
x
≤
e
(
G
BPT
*
). We notice that if r
-
e
(
G
BPT
*
)
≤
Δ
(
G
BPT
*
)
≤
r
/
2 and r
≥
2, we have
(10)
2
e
(
G
BPT
*
)
n
<
e
(
G
BPT
*
)
2
≤
2
r
Δ
(
G
BPT
*
)
4
≤
r
-
Δ
(
G
BPT
*
)
≤
e
(
G
BPT
*
)
and Δ
(
G
BPT
*
)
≤
r
-
r. Hence, when r
-
e
(
G
BPT
*
)
≤
Δ
(
G
BPT
*
)
≤
r
/
2 and r
≥
2,
(11)
2
e
(
G
BPT
*
)
-
2
r
+
2
+
e
(
G
BPT
*
)
(
n
-
2
+
2
)
=
2
e
(
G
BPT
*
)
-
2
r
+
2
+
g
(
e
(
G
BPT
*
)
2
)
≥
2
e
(
G
BPT
*
)
-
2
r
+
2
+
g
(
r
-
Δ
(
G
BPT
*
)
)
=
2
e
(
G
BPT
*
)
+
2
-
2
Δ
(
G
BPT
*
)
+
(
n
-
2
)
(
2
e
(
G
BPT
*
)
-
2
(
r
-
Δ
(
G
BPT
*
)
)
2
)
.
So Theorem 2 improves Theorem 4, when r
-
e
(
G
BPT
*
)
≤
Δ
(
G
BPT
*
)
≤
r
/
2 and r
≥
2.


## 2. Preliminaries

LetG be a graph of order n. Ore [7] proves that if
(12)
d
G
(
u
)
+
d
G
(
v
)
≥
n
-
1
for any pair of nonadjacent vertices u and v, then G has a Hamiltonian path; if
(13)
d
G
(
u
)
+
d
G
(
v
)
≥
n
for any pair of nonadjacent vertices u and v, then G has a Hamiltonian cycle. Erdős and Gallai [8] show that if
(14)
d
G
(
u
)
+
d
G
(
v
)
≥
n
+
1
for any pair of nonadjacent vertices u and v, then G is Hamilton-connected.The idea for the closure of a graphG was given by Bondy and Chvátal [9]. For an integer k
≥
0, the k
-closure of a graph  G, denoted by 𝒞
k
(
G
), is the graph obtained from G by successively joining pairs of nonadjacent vertices whose degree sum is at least k until no such pair remains. The concept of the closure of a balanced bipartite graph is given in [9, 10]. The k
-closure of a balanced bipartite graph  G
BPT
:
=
(
X
,
Y
;
E
), where |
X
|
=
|
Y
|, denoted by 𝒞
k
(
G
BPT
), is a graph obtained from G
BPT by successively joining pairs of nonadjacent vertices x
∈
X and y
∈
Y, whose degree sum is at least k until no such pairs remain. The k-closure of a graph G or the k-closure of a balanced bipartite graph G
BPT is unique, independent of the order in which edges are added. We note that d
𝒞
k
(
G
)
(
u
)
+
d
𝒞
k
(
G
)
(
v
)
≤
k
-
1 for any pair of nonadjacent vertices u and v of 𝒞
k
(
G
), d
𝒞
k
(
G
BPT
)
(
x
)
+
d
𝒞
k
(
G
BPT
)
(
y
)
≤
k
-
1 for any pair of nonadjacent vertices x
∈
X and y
∈
Y of 𝒞
k
(
G
BPT
).Lemma 6 (see [9]).
(i) A graphG of order n has a Hamilton path, if and only if 𝒞
n
-
1
(
G
) has a Hamilton path.
(ii) A graphG of order n has a Hamilton cycle, if and only if 𝒞
n
(
G
) has a Hamilton cycle.
(iii) A graphG of order n is Hamilton-connected, if and only if 𝒞
n
+
1
(
G
) is Hamilton-connected.Lemma 7 (see [10]).
A balanced bipartite graphG
B
P
T
=
(
X
,
Y
;
E
), where |
X
|
=
|
Y
|
=
r
≥
2, has a Hamiltonian cycle, if and only if 𝒞
r
+
1
(
G
B
P
T
) has a Hamiltonian cycle.Lemma 8 (see [11]).
Lete be any edge in a graph G; one denotes by G
-
e the subgraph of G obtained by deleting the edge e. Then ℰ
(
G
)
-
2
≤
ℰ
(
G
-
e
)
≤
ℰ
(
G
)
+
2.For a graphG, let Z
(
G
)
:
=
∑
u
v
∈
E
(
G
)
‍
(
d
G
(
u
)
+
d
G
(
v
)
)
=
∑
u
∈
V
(
G
)
‍
d
G
2
(
u
).Lemma 9 (see [2]).
Let G be a graph with at least one edge. Then(15)
q
(
G
)
≥
Z
(
G
)
e
(
G
)
.LetM be a Hermitian matrix of order n and let λ
i
(
M
) be the ith largest eigenvalue of M, 1
≤
i
≤
n.Lemma 10 (see [12]).
LetB and C be Hermitian matrices of order n and let 1
≤
i, j
≤
n. If i
+
j
≤
n
+
1, then
(16)
λ
i
(
B
)
+
λ
j
(
C
)
≥
λ
i
+
j
-
1
(
B
+
C
)
.Lemma 11.
LetG be a graph. Then
(17)
μ
(
G
)
≥
q
(
G
)
-
Δ
(
G
)
.Proof.
SinceQ
(
G
)
=
A
(
G
)
+
D
(
G
), by Lemma 10
(18)
λ
1
(
A
(
G
)
)
+
λ
1
(
D
(
G
)
)
≥
λ
1
(
Q
(
G
)
)
.
Recalling that λ
1
(
A
(
G
)
)
=
μ
(
G
), λ
1
(
D
(
G
)
)
=
Δ
(
G
), and q
(
G
)
=
λ
1
(
Q
(
G
)
), the result follows.Corollary 12.
LetG be a graph with at least one edge. Then
(19)
μ
(
G
)
≥
Z
(
G
)
e
(
G
)
-
Δ
(
G
)
.Proof.
The result follows by Lemmas9 and 11.


## 3. Proof of Theorem1

(i) LetH
:
=
𝒞
n
-
1
(
G
). If H
=
K
n, then the result follows from (12). Suppose that H
≠
K
n and G does not contain a Hamilton path. Then H does not contain a Hamilton path by Lemma 6(i). We notice that d
H
(
u
)
+
d
H
(
v
)
≤
n
-
2 for any pair of nonadjacent vertices u and v (always existing) in H. Thus, for any edge u
v
∈
E
(
H
c
),
(20)
d
H
c
(
u
)
+
d
H
c
(
v
)
=
2
(
n
-
1
)
-
[
d
H
(
u
)
+
d
H
(
v
)
]
≥
n
,
and Z
(
H
c
)
=
∑
u
v
∈
E
(
H
c
)
‍
[
d
H
c
(
u
)
+
d
H
c
(
v
)
]
≥
n
e
(
H
c
). By Corollary 12,
(21)
μ
(
H
c
)
≥
Z
(
H
c
)
e
(
H
c
)
-
Δ
(
H
c
)
≥
n
-
Δ
(
H
c
)
≥
n
-
Δ
(
G
c
)
.By Cauchy-Schwartz inequality, we have that(22)
ℰ
(
H
c
)
=
∑
i
=
1
n
‍
|
μ
i
(
H
c
)
|
=
μ
(
H
c
)
+
∑
i
=
1
n
-
1
‍
|
μ
i
(
H
c
)
|
≤
μ
(
H
c
)
+
(
n
-
1
)
∑
i
=
1
n
-
1
‍
μ
i
2
(
H
c
)
=
μ
(
H
c
)
+
(
n
-
1
)
(
∑
i
=
1
n
‍
μ
i
2
(
H
c
)
-
μ
2
(
H
c
)
)
=
μ
(
H
c
)
+
(
n
-
1
)
(
2
e
(
H
c
)
-
μ
2
(
H
c
)
)
;
the equality holds if and only if |
μ
1
(
H
c
)
|
=
|
μ
2
(
H
c
)
|
=
⋯
=
|
μ
n
-
1
(
H
c
)
|.Letf
(
x
)
=
x
+
(
n
-
1
)
(
2
e
(
H
c
)
-
x
2
). If 2
e
(
H
c
)
/
n
<
x
<
2
e
(
H
c
),
(23)
f
′
(
x
)
=
1
+
-
(
n
-
1
)
x
(
n
-
1
)
(
2
e
(
H
c
)
-
x
2
)
<
0
.
So, f
(
x
) is monotonously decreasing when 2
e
(
H
c
)
/
n
<
x
<
2
e
(
H
c
). We find that
(24)
2
e
(
H
c
)
n
≤
2
e
(
G
c
)
n
≤
Δ
(
G
c
)
<
n
-
Δ
(
G
c
)
≤
μ
(
H
c
)
<
2
e
(
H
c
)
,
when Δ
(
G
c
)
≤
n
-
n
-
1.Thus(25)
ℰ
(
H
c
)
≤
f
(
μ
(
H
c
)
)
≤
f
(
n
-
Δ
(
G
c
)
)
=
n
-
Δ
(
G
c
)
+
(
n
-
1
)
(
2
e
(
H
c
)
-
(
n
-
Δ
(
G
c
)
)
2
)
.Lets
:
=
e
(
H
)
-
e
(
G
). We use C
(
n
,
k
) to denote the number of k-combinations of a set with n distinct elements. Then e
(
G
c
)
-
e
(
H
c
)
=
(
C
(
n
,
2
)
-
e
(
G
)
)
-
(
C
(
n
,
2
)
-
e
(
H
)
)
=
s. Because H has at least two nonadjacent vertices u and v such that d
H
(
u
)
+
d
H
(
v
)
≤
n
-
2, then e
(
H
)
≤
(
n
-
2
)
+
C
(
n
-
2,2
)
=
(
n
2
-
3
n
+
2
)
/
2. Hence s
≤
(
n
2
-
3
n
+
2
)
/
2
-
e
(
G
)
=
(
n
2
-
3
n
+
2
)/2
-
(
C
(
n
,
2
)
-
e
(
G
c
)
)
=
e
(
G
c
)
-
n
+
1.By Lemma8, we have that ℰ
(
H
c
)
≥
ℰ
(
G
c
)
-
2
s. Thus ℰ
(
H
c
)
≥
ℰ
(
G
c
)
-
2
e
(
G
c
)
+
2
n
-
2. Because e
(
H
c
)
≤
e
(
G
c
), we have that
(26)
ℰ
(
G
c
)
≤
2
e
(
G
c
)
-
n
+
2
-
Δ
(
G
c
)
+
(
n
-
1
)
(
2
e
(
G
c
)
-
(
n
-
Δ
(
G
c
)
)
2
)
,
a contradiction.(ii) LetH
-
=
𝒞
n
(
G
). If H
-
=
K
n, then the result follows from (13). Suppose that H
-
≠
K
n and G does not contain a Hamilton cycle. Then H
- does not contain a Hamilton cycle too by Lemma 6(ii). By a similar discussion in the proof of Theorem 1(i), we have that d
H
-
c
(
u
)
+
d
H
-
c
(
v
)
≥
n
-
1 for any edge u
v
∈
E
(
H
-
c
) and
(27)
Z
(
H
-
c
)
=
∑
u
v
∈
E
(
H
-
c
)
‍
[
d
H
-
c
(
u
)
+
d
H
-
c
(
v
)
]
≥
(
n
-
1
)
e
(
H
-
c
)
.By Corollary12,
(28)
μ
(
H
-
c
)
≥
Z
(
H
-
c
)
e
(
H
-
c
)
-
Δ
(
H
-
c
)
≥
n
-
1
-
Δ
(
H
-
c
)
≥
n
-
1
-
Δ
(
G
c
)
.We find that(29)
2
e
(
H
-
c
)
n
≤
2
e
(
G
c
)
n
≤
Δ
(
G
c
)
<
n
-
1
-
Δ
(
G
c
)
≤
μ
(
H
-
c
)
<
2
e
(
H
-
c
)
,
when Δ
(
G
c
)
≤
n
-
1
-
n
-
1. Using similar arguments as in the proof of Theorem 1(i), we have that
(30)
ℰ
(
H
-
c
)
≤
f
(
μ
(
H
-
c
)
)
≤
f
(
n
-
1
-
Δ
(
G
c
)
)
=
n
-
1
-
Δ
(
G
c
)
+
(
n
-
1
)
(
2
e
(
H
-
c
)
-
(
n
-
1
-
Δ
(
G
c
)
)
2
)
.Lets
:
=
e
(
H
-
)
-
e
(
G
). Then e
(
G
c
)
-
e
(
H
-
c
)
=
(
C
(
n
,
2
)
-
e
(
G
)
)
-
(
C
(
n
,
2
)
-
e
(
H
-
)
)
=
s. Because H
- has at least two nonadjacent vertices u and v such that d
H
-
(
u
)
+
d
H
-
(
v
)
≤
n
-
1, then e
(
H
-
)
≤
(
n
-
1
)
+
C
(
n
-
2,2
)
=
(
n
2
-
3
n
+
4
)
/
2. Hence s
≤
(
n
2
-
3
n
+
4
)
/
2
-
e
(
G
)
=
(
n
2
-
3
n
+
4
)/2
-
(
C
(
n
,
2
)
-
e
(
G
c
)
)
=
e
(
G
c
)
-
n
+
2.By Lemma8, we have that ℰ
(
H
-
c
)
≥
ℰ
(
G
c
)
-
2
s. Thus ℰ
(
H
-
c
)
≥
ℰ
(
G
c
)
-
2
e
(
G
c
)
+
2
n
-
4. Because e
(
H
-
c
)
≤
e
(
G
c
), we have that
(31)
ℰ
(
G
c
)
≤
2
e
(
G
c
)
-
n
+
3
-
Δ
(
G
c
)
+
(
n
-
1
)
(
2
e
(
G
c
)
-
(
n
-
1
-
Δ
(
G
c
)
)
2
)
,
a contradiction.(iii) LetH
^
=
𝒞
n
+
1
(
G
). If H
^
=
K
n, then the result follows from (14). Suppose that H
^
≠
K
n and G is not Hamilton-connected. Then H
^ is not Hamilton-connected by Lemma 6(iii). By a similar discussion in the proof of Theorem 1(i), we have that d
H
^
c
(
u
)
+
d
H
^
c
(
v
)
≥
n
-
2 for any edge u
v
∈
E
(
H
^
c
), and
(32)
Z
(
H
^
c
)
=
∑
u
v
∈
E
(
H
^
c
)
‍
[
d
H
^
c
(
u
)
+
d
H
^
c
(
v
)
]
≥
(
n
-
2
)
e
(
H
^
c
)
.By Corollary12,
(33)
μ
(
H
^
c
)
≥
Z
(
H
^
c
)
e
(
H
^
c
)
-
Δ
(
H
^
c
)
≥
n
-
2
-
Δ
(
H
^
c
)
≥
n
-
2
-
Δ
(
G
c
)
.We notice that(34)
2
e
(
H
^
c
)
n
≤
2
e
(
G
c
)
n
≤
Δ
(
G
c
)
<
n
-
2
-
Δ
(
G
c
)
≤
μ
(
H
^
c
)
<
2
e
(
H
^
c
)
,
when Δ
(
G
c
)
≤
n
-
2
-
n
-
1. Using similar arguments as in the proof of Theorem 1(i), we have that
(35)
ℰ
(
H
^
c
)
≤
f
(
μ
(
H
^
c
)
)
≤
f
(
n
-
2
-
Δ
(
G
c
)
)
=
n
-
2
-
Δ
(
G
c
)
+
(
n
-
1
)
(
2
e
(
H
^
c
)
-
(
n
-
2
-
Δ
(
G
c
)
)
2
)
.Lets
:
=
e
(
H
^
)
-
e
(
G
). Then e
(
G
c
)
-
e
(
H
^
c
)
=
(
C
(
n
,
2
)
-
e
(
G
)
)
-
(
C
(
n
,
2
)
-
e
(
H
^
)
)
=
s. Because H
^ has at least two nonadjacent vertices u and v such that d
H
^
(
u
)
+
d
H
^
(
v
)
≤
n.H
^ has at least two nonadjacent vertices u and v such that d
H
^
(
u
)
+
d
H
^
(
v
)
≤
n, then e
(
H
^
)
≤
n
+
C
(
n
-
2,2
)
=
(
n
2
-
3
n
+
6
)
/
2. Hence s
≤
(
n
2
-
3
n
+
6
)
/
2
-
e
(
G
)
=
(
n
2
-
3
n
+
6
)
/
2
-
(
C
(
n
,
2
)
-
e
(
G
c
)
)
=
e
(
G
c
)
-
n
+
3.By Lemma8, we have that ℰ
(
H
^
c
)
≥
ℰ
(
G
c
)
-
2
s. Thus ℰ
(
H
^
c
)
≥
ℰ
(
G
c
)
-
2
e
(
G
c
)
+
2
n
-
6. Because e
(
H
^
c
)
≤
e
(
G
c
), we have that
(36)
ℰ
(
G
c
)
≤
2
e
(
G
c
)
-
n
+
4
-
Δ
(
G
c
)
+
(
n
-
1
)
(
2
e
(
G
c
)
-
(
n
-
2
-
Δ
(
G
c
)
)
2
)
,
a contradiction.


## 4. Proof of Theorem2

Proof.
Suppose thatG
BPT does not contain a Hamilton cycle. Then H
BPT
:
=
𝒞
r
+
1
(
G
BPT
) does not contain a Hamilton cycle by Lemma 7. Then H
BPT is not K
r
,
r by (13). Observe that d
H
BPT
(
x
)
+
d
H
BPT
(
y
)
≤
r for any pair of nonadjacent vertices x
∈
X and y
∈
Y (always existing) in H
BPT. Thus,
(37)
d
H
BPT
*
(
x
)
+
d
H
BPT
*
(
y
)
=
r
-
d
H
BPT
(
x
)
+
r
-
d
H
BPT
(
y
)
≥
r
,
for any pair of adjacent vertices x
∈
X and y
∈
Y in H
BPT
*. Then
(38)
Z
(
H
BPT
*
)
=
∑
u
∈
V
(
H
BPT
*
)
‍
d
H
BPT
*
2
(
u
)
=
∑
x
y
∈
E
(
H
BPT
*
)
‍
(
d
H
BPT
*
(
x
)
+
d
H
BPT
*
(
y
)
)
≥
r
e
(
H
BPT
*
)
.
By Corollary 12, we have that
(39)
μ
(
H
BPT
*
)
≥
Z
(
H
BPT
*
)
e
(
H
BPT
*
)
-
Δ
(
H
BPT
*
)
≥
r
-
Δ
(
H
BPT
*
)
≥
r
-
Δ
(
G
BPT
*
)
.
SinceH
BPT
* is a bipartite graph, μ
n
(
H
BPT
*
)
=
-
μ
1
(
H
BPT
*
). By Cauchy-Schwartz inequality, we have
(40)
ℰ
(
H
BPT
*
)
=
∑
i
=
1
n
‍
|
μ
i
(
H
BPT
*
)
|
=
2
μ
(
H
BPT
*
)
+
∑
i
=
2
n
-
1
‍
|
μ
i
(
H
BPT
*
)
|
≤
2
μ
(
H
BPT
*
)
+
(
n
-
2
)
∑
i
=
2
n
-
1
‍
μ
i
2
(
H
BPT
*
)
=
2
μ
(
H
BPT
*
)
+
(
n
-
2
)
(
∑
i
=
1
n
‍
μ
i
2
(
H
BPT
*
)
-
2
μ
2
(
H
BPT
*
)
)
=
2
μ
(
H
BPT
*
)
+
(
n
-
2
)
(
2
e
(
H
BPT
*
)
-
2
μ
2
(
H
BPT
*
)
)
;
the equality holds if and only if |
μ
2
(
H
BPT
*
)
|
=
⋯
=
|
μ
n
-
1
(
H
BPT
*
)
|.
Letg
(
x
)
=
2
x
+
(
n
-
2
)
(
2
e
(
H
BPT
*
)
-
2
x
2
). If 2
e
(
H
BPT
*
)
/
n
<
x
<
e
(
H
BPT
*
),
(41)
g
′
(
x
)
=
2
+
-
2
(
n
-
2
)
x
(
n
-
2
)
(
2
e
(
H
BPT
*
)
-
2
x
2
)
<
0
.
So, g
(
x
) is monotonously decreasing when 2
e
(
H
BPT
*
)
/
n
<
x
<
e
(
H
BPT
*
). We find that
(42)
2
e
(
H
BPT
*
)
n
≤
Δ
(
G
BPT
*
)
<
r
-
Δ
(
G
BPT
*
)
≤
μ
(
H
BPT
*
)
<
e
(
H
BPT
*
)
,
when Δ
(
G
c
)
≤
r
-
r. So
(43)
ℰ
(
H
BPT
*
)
≤
g
(
μ
(
H
BPT
*
)
)
≤
g
(
r
-
Δ
(
G
BPT
*
)
)
=
2
(
r
-
Δ
(
G
BPT
*
)
)
+
(
n
-
2
)
(
2
e
(
H
BPT
*
)
-
2
(
r
-
Δ
(
G
BPT
*
)
)
2
)
.
Let t
:
=
e
(
H
BPT
)
-
e
(
G
BPT
). Then e
(
G
BPT
*
)
-
e
(
H
BPT
*
)
=
(
r
2
-
e
(
G
BPT
)
)
-
(
r
2
-
e
(
H
BPT
)
)
=
t. Because H
BPT has two nonadjacent vertices x
∈
X and y
∈
Y such that d
H
BPT
(
x
)
+
d
H
BPT
(
y
)
≤
r, so e
(
H
BPT
)
≤
(
r
-
1
)
2
+
r
=
r
2
-
r
+
1. Hence t
≤
r
2
-
r
+
1
-
e
(
G
BPT
)
=
r
2
-
r
+
1
-
(
r
2
-
e
(
G
BPT
*
)
)
=
e
(
G
BPT
*
)
-
r
+
1.
By Lemma8, we have that ℰ
(
H
BPT
*
)
≥
ℰ
(
G
BPT
*
)
-
2
t. Then ℰ
(
H
BPT
*
)
≥
ℰ
(
G
BPT
*
)
-
2
e
(
G
BPT
*
)
+
2
r
-
2. Because e
(
H
BPT
*
)
≤
e
(
G
BPT
*
), we have that
(44)
ℰ
(
G
BPT
*
)
≤
2
e
(
G
BPT
*
)
+
2
-
2
Δ
(
G
BPT
*
)
+
(
n
-
2
)
(
2
e
(
G
BPT
*
)
-
2
(
r
-
Δ
(
G
BPT
*
)
)
2
)
,
a contradiction.



---

*Source: 305164-2014-03-06.xml*