Mathematical Problems of Computer Science 51, 39–56, 2019.

UDC 519.1

Long Cycles in t-Tough Graphs with t > 1

Zhora G. Nikoghosyan

Institute for Informatics and Automation Problems of NAS RA
e-mail: zhora@ipia.sci.am

Abstract
It is proved that if G is a t-tough graph of order n and minimum degree δ with

t > 1, then either G has a cycle of length at least min{n, 2δ + 4} or G is the Petersen
graph.

Keywords: Hamilton cycle, Circumference, Minimum degree, Toughness.

1. Introduction

Only finite undirected graphs without loops or multiple edges are considered. We reserve n,
δ, κ, c and τ to denote the number of vertices (order), the minimum degree, connectivity,
circumference and the toughness of a graph, respectively. A good reference for any undefined
terms is [1].

The earliest lower bound for the circumference was developed in 1952 due to Dirac [2].

Theorem A: [2]. In every 2-connected graph, c ≥ min{n, 2δ}.

In 1986, Bauer and Schmeichel [3] proved that the bound 2δ in Theorem A can be en-
larged to 2δ + 2 by replacing the 2-connectivity condition with 1-toughness.

Theorem B: [3]. In every 1-tough graph, c ≥ min{n, 2δ + 2}.

In this paper we prove that in Theorem B the bound 2δ + 2 itself can be enlarged up to
2δ + 4 if τ > 1 and G is not the Petersen graph.

Theorem 1: Let G be a graph with τ > 1. Then either c ≥ min{n, 2δ + 4} or G is the
Petersen graph.

To prove Theorem 1, we need the following result due to Voss [4].

Theorem C: [4]. Let G be a Hamiltonian graph, {v1, v2, ..., vt} ⊆ V (G) and d(vi) ≥ t
(i = 1, 2, ..., t). Then each pair x, y of vertices of G is connected in G by a path of length at
least t.

39



40 Long Cycles in t-Tough Graphs with t > 1

2. Notations and Preliminaries

The set of vertices of a graph G is denoted by V (G), and the set of edges by E(G). For S
a subset of V (G), we denote by G\S the maximum subgraph of G with vertex set V (G)\S.
We write G[S] for the subgraph of G induced by S. For a subgraph H of G we use G\H
short for G\V (H). The neighborhood of a vertex x ∈ V (G) will be denoted by N (x).
Furthermore, for a subgraph H of G and x ∈ V (G), we define NH (x) = N (x) ∩ V (H) and
dH (x) = |NH (x)|. Let s(G) denote the number of components of a graph G. A graph G is
t-tough if |S| ≥ ts(G\S) for every subset S of the vertex set V (G) with s(G\S) > 1. The
toughness of G, denoted τ (G), is the maximum value of t for which G is t-tough (taking
τ (Kn) = ∞ for all n ≥ 1).

A simple cycle (or just a cycle) C of length t is a sequence v1v2...vtv1 of distinct vertices
v1, ..., vt with vivi+1 ∈ E(G) for each i ∈ {1, ..., t}, where vt+1 = v1. When t = 2, the cycle
C = v1v2v1 on two vertices v1, v2 coincides with the edge v1v2, and when t = 1, the cycle
C = v1 coincides with the vertex v1. So, all vertices and edges in a graph can be considered
as cycles of lengths 1 and 2, respectively. A graph G is Hamiltonian if G contains a Hamilton
cycle, i.e., a cycle of length n. A cycle C in G is dominating if G\C is edgeless.

Paths and cycles in a graph G are considered as subgraphs of G. If Q is a path or a
cycle, then the length of Q, denoted by |Q|, is |E(Q)|. We write Q with a given orientation
by
−→
Q . For x, y ∈ V (Q), we denote by x−→Q y the subpath of Q in the chosen direction from

x to y. For x ∈ V (C), we denote the h-th successor and the h-th predecessor of x on −→C by
x+h and x−h, respectively. We abbreviate x+1 and x−1 by x+ and x−, respectively. For each
X ⊂ V (C), we define X+h = {x+h|x ∈ X} and X−h = {x−h|x ∈ X}.

Special definitions: Let G be a graph, C a longest cycle in G and P = x
−→
P y a longest

path in G\C of length p ≥ 0. Let ξ1, ξ2, ..., ξs be the elements of NC (x) ∪ NC (y) occuring on
C in a consecutive order. Set

Ii = ξi
−→
C ξi+1, I

∗
i = ξ

+
i

−→
C ξ−i+1 (i = 1, 2, ..., s),

where ξs+1 = ξ1.
(1) The segments I1, I2, ..., Is are called elementary segments on C created by NC (x) ∪

NC (y).

(2) We call a path L = z
−→
L w an intermediate path between two distinct elementary

segments Ia and Ib if

z ∈ V (I∗a ), w ∈ V (I∗b ), V (L) ∩ V (C ∪ P ) = {z, w}.
(3) Define Υ(Ii1 , Ii2 , ..., Iit ) to be the set of all intermediate paths between elementary

segments Ii1 , Ii2 , ..., Iit .

Lemma 1: Let G be a graph, C a longest cycle in G and P = x
−→
P y a longest path in G\C

of length p ≥ 1. If |NC (x)| ≥ 2, |NC (y)| ≥ 2 and NC (x) 6= NC (y), then

|C| ≥
{

3δ + max{σ1, σ2} − 1 ≥ 3δ if p = 1,
max{2p + 8, 4δ − 2p} if p ≥ 2,

where σ1 = |NC (x)\NC (y)| and σ2 = |NC (y)\NC (x)|.



Zh. Nikoghosyan 41

Lemma 2: Let G be a graph, C a longest cycle in G and P = x
−→
P y a longest path in G\C

of length p ≥ 0. If NC (x) = NC (y) and |NC (x)| ≥ 2, then for each elementary segments Ia
and Ib induced by NC (x) ∪ NC (y),

(a1) if L is an intermediate path between Ia and Ib, then

|Ia| + |Ib| ≥ 2p + 2|L| + 4,

(a2) if Υ(Ia, Ib) ⊆ E(G) and |Υ(Ia, Ib)| = i for some i ∈ {1, 2, 3}, then

|Ia| + |Ib| ≥ 2p + i + 5,

(a3) if Υ(Ia, Ib) ⊆ E(G) and Υ(Ia, Ib) contains two independent intermediate edges, then

|Ia| + |Ib| ≥ 2p + 8.

Lemma 3: Let G be a graph and C a longest cycle in G. Then either |C| ≥ κ(δ + 1) or
there is a longest path P = x1

−→
P x2 in G\C with |NC (xi)| ≥ 2 (i = 1, 2).

3. Proofs

Proof of Lemma 1. Put

A1 = NC (x)\NC (y), A2 = NC (y)\NC (x), M = NC (x) ∩ NC (y).

By the hypothesis, NC (x) 6= NC (y), implying that

max{|A1|, |A2|} ≥ 1.

Let ξ1, ξ2, ..., ξs be the elements of NC (x) ∪ NC (y) occuring on C in a consecutive order. Put
Ii = ξi

−→
C ξi+1 (i = 1, 2, ..., s), where ξs+1 = ξ1. Clearly, s = |A1| + |A2| + |M|. Since C is

extreme, |Ii| ≥ 2 (i = 1, 2, ..., s). Next, if {ξi, ξi+1} ∩ M 6= ∅ for some i ∈ {1, 2, ..., s}, then
|Ii| ≥ p+2. Further, if either ξi ∈ A1, ξi+1 ∈ A2 or ξi ∈ A2, ξi+1 ∈ A1, then again |Ii| ≥ p+2.

Case 1. p = 1.
Case 1.1. |Ai| ≥ 1 (i = 1, 2).
It follows that among I1, I2, ..., Is there are |M| + 2 segments of length at least p + 2.

Observing also that each of the remaining s − (|M| + 2) segments has a length at least 2, we
have

|C| ≥ (p + 2)(|M| + 2) + 2(s − |M| − 2)
= 3(|M| + 2) + 2(|A1| + |A2| − 2)

= 2|A1| + 2|A2| + 3|M| + 2.
Since |A1| = d(x) − |M| − 1 and |A2| = d(y) − |M| − 1,

|C| ≥ 2d(x) + 2d(y) − |M| − 2 ≥ 3δ + d(x) − |M| − 2.



42 Long Cycles in t-Tough Graphs with t > 1

Recalling that d(x) = |M| + |A1| + 1, we get

|C| ≥ 3δ + |A1| − 1 = 3δ + σ1 − 1.

Analogously, |C| ≥ 3δ + σ2 − 1. So,

|C| ≥ 3δ + max{σ1, σ2} − 1 ≥ 3δ.

Case 1.2. Either |A1| ≥ 1, |A2| = 0 or |A1| = 0, |A2| ≥ 1.
Assume w.l.o.g. that |A1| ≥ 1 and |A2| = 0, i.e., |NC (y)| = |M| ≥ 2 and s = |A1| + |M|.

Hence, among I1, I2, ..., Is there are |M| + 1 segments of length at least p + 2 = 3. Taking
into account that each of the remaining s − (|M| + 1) segments has a length at least 2 and
|M| + 1 = d(y), we get

|C| ≥ 3(|M| + 1) + 2(s − |M| − 1) = 3d(y) + 2(|A1| − 1)

≥ 3δ + |A1| − 1 = 3δ + max{σ1, σ2} − 1 ≥ 3δ.
Case 2. p ≥ 2.
We first prove that |C| ≥ 2p + 8. Since |NC (x)| ≥ 2 and |NC (y)| ≥ 2, there are at least

two segments among I1, I2, ..., Is of length at least p + 2. If |M| = 0, then clearly s ≥ 4 and

|C| ≥ 2(p + 2) + 2(s − 2) ≥ 2p + 8.

Otherwise, since max{|A1|, |A2|} ≥ 1, there are at least three elementary segments of length
at least p + 2, that is

|C| ≥ 3(p + 2) ≥ 2p + 8.
So, in any case, |C| ≥ 2p + 8.

To prove that |C| ≥ 4δ − 2p, we distinguish two main cases.

Case 2.1. |Ai| ≥ 1 (i = 1, 2).
It follows that among I1, I2, ..., Is there are |M| + 2 segments of length at least p + 2.

Further, since each of the remaining s − (|M| + 2) segments has a length at least 2, we get

|C| ≥ (p + 2)(|M| + 2) + 2(s − |M| − 2)

= (p − 2)|M| + (2p + 4|M| + 4) + 2(|A1| + |A2| − 2)
≥ 2|A1| + 2|A2| + 4|M| + 2p.

Observing also that

|A1| + |M| + p ≥ d(x), |A2| + |M| + p ≥ d(y),

we have

2|A1| + 2|A2| + 4|M| + 2p
≥ 2d(x) + 2d(y) − 2p ≥ 4δ − 2p,

implying that |C| ≥ 4δ − 2p.



Zh. Nikoghosyan 43

Case 2.2. Either |A1| ≥ 1, |A2| = 0 or |A1| = 0, |A2| ≥ 1.
Assume w.l.o.g. that |A1| ≥ 1 and |A2| = 0, i.e., |NC (y)| = |M| ≥ 2 and s = |A1|+|M|. It

follows that among I1, I2, ..., Is there are |M|+ 1 segments of length at least p + 2. Observing
also that |M| + p ≥ d(y) ≥ δ, i.e. 2p + 4|M| ≥ 4δ − 2p, we get

|C| ≥ (p + 2)(|M| + 1) ≥ (p − 2)(|M| − 1) + 2p + 4|M|

≥ 2p + 4|M| ≥ 4δ − 2p.
Proof of Lemma 2. Let ξ1, ξ2, ..., ξs be the elements of NC (x) occurring on C in a consecu-

tive order. Put Ii = ξi
−→
C ξi+1 (i = 1, 2, ..., s), where ξs+1 = ξ1. To prove (a1), let L = z

−→
L w be

an intermediate path between elementary segments Ia and Ib with z ∈ V (I∗a ) and w ∈ V (I∗b ).
Put

|ξa
−→
C z| = d1, |z

−→
C ξa+1| = d2, |ξb

−→
C w| = d3, |w

−→
C ξb+1| = d4,

C′ = ξax
−→
P yξb

←−
C z

−→
L w

−→
C ξa.

Clearly,
|C′| = |C| − d1 − d3 + |L| + |P| + 2.

Since C is extreme, we have |C| ≥ |C′|, implying that d1 + d3 ≥ p + |L| + 2. By a symmetric
argument, d2 + d4 ≥ p + |L| + 2. Hence

|Ia| + |Ib| =
4∑

i=1

di ≥ 2p + 2|L| + 4.

The proof of (a1) is complete. To proof (a2) and (a3), let Υ(Ia, Ib) ⊆ E(G) and
|Υ(Ia, Ib)| = i for some i ∈ {1, 2, 3}.

Case 1. i = 1.
It follows that Υ(Ia, Ib) consists of a unique intermediate edge L = zw. By (a1),

|Ia| + |Ib| ≥ 2p + 2|L| + 4 = 2p + 6.

Case 2. i = 2.
It follows that Υ(Ia, Ib) consists of two edges e1, e2. Put e1 = z1w1 and e2 = z2w2, where

{z1, z2} ⊆ V (I∗a ) and {w1, w2} ⊆ V (I∗b ).

Case 2.1. z1 6= z2 and w1 6= w2.
Assume w.l.o.g. that z1 and z2 occur in this order on Ia.

Case 2.1.1. w2 and w1 occur in this order on Ib.
Put

|ξa
−→
C z1| = d1, |z1

−→
C z2| = d2, |z2

−→
C ξa+1| = d3,

|ξb
−→
C w2| = d4, |w2

−→
C w1| = d5, |w1

−→
C ξb+1| = d6,

C′ = ξa
−→
C z1w1

←−
C w2z2

−→
C ξbx

−→
P yξb+1

−→
C ξa.

Clearly,
|C′| = |C| − d2 − d4 − d6 + |{e1}| + |{e2}| + |P| + 2



44 Long Cycles in t-Tough Graphs with t > 1

= |C| − d2 − d4 − d6 + p + 4.
Since C is extreme, |C| ≥ |C′|, implying that d2 + d4 + d6 ≥ p + 4. By a symmetric argument,
d1 + d3 + d5 ≥ p + 4. Hence

|Ia| + |Ib| =
6∑

i=1

di ≥ 2p + 8.

Case 2.1.2. w1 and w2 occur in this order on Ib.
Putting

C′ = ξa
−→
C z1w1

−→
C w2z2

−→
C ξbx

−→
P yξb+1

−→
C ξa,

we can argue as in Case 2.1.1.

Case 2.2. Either z1 = z2, w1 6= w2 or z1 6= z2, w1 = w2.
Assume w.l.o.g. that z1 6= z2, w1 = w2 and z1, z2 occur in this order on Ia. Put

|ξa
−→
C z1| = d1, |z1

−→
C z2| = d2, |z2

−→
C ξa+1| = d3,

|ξb
−→
C w1| = d4, |w1

−→
C ξb+1| = d5,

C′ = ξax
−→
P yξb

←−
C z1w1

−→
C ξa,

C′′ = ξa
−→
C z2w1

←−
C ξa+1x

−→
P yξb+1

−→
C ξa.

Clearly,

|C′| = |C| − d1 − d4 + |{e1}| + |P| + 2 = |C| − d1 − d4 + p + 3,

|C′′| = |C| − d3 − d5 + |{e2}| + |P| + 2 = |C| − d3 − d5 + p + 3.
Since C is extreme, |C| ≥ |C′| and |C| ≥ |C′′|, implying that

d1 + d4 ≥ p + 3, d3 + d5 ≥ p + 3.

Hence,

|Ia| + |Ib| =
5∑

i=1

di ≥ d1 + d3 + d4 + d5 + 1 ≥ 2p + 7.

Case 3. i = 3.
It follows that Υ(Ia, Ib) consists of three edges e1, e2, e3. Let ei = ziwi (i = 1, 2, 3),

where {z1, z2, z3} ⊆ V (I∗a ) and {w1, w2, w3} ⊆ V (I∗b ). If there are two independent edges
among e1, e2, e3, then we can argue as in Case 2.1. Otherwise, we can assume w.l.o.g. that
w1 = w2 = w3 and z1, z2, z3 occur in this order on Ia. Put

|ξa
−→
C z1| = d1, |z1

−→
C z2| = d2, |z2

−→
C z3| = d3,

|z3
−→
C ξa+1| = d4, |ξb

−→
C w1| = d5, |w1

−→
C ξb+1| = d6,

C′ = ξax
−→
P yξb

←−
C z1w1

−→
C ξa,

C′′ = ξa
−→
C z3w1

←−
C ξa+1x

−→
P yξb+1

−→
C ξa.



Zh. Nikoghosyan 45

Clearly,

|C′| = |C| − d1 − d5 + |{e1}| + p + 2,
|C′′| = |C| − d4 − d6 + |{e3}| + p + 2.

Since C is extreme, we have |C| ≥ |C′| and |C| ≥ |C′′|, implying that

d1 + d5 ≥ p + 3, d4 + d6 ≥ p + 3.

Hence,

|Ia| + |Ib| =
6∑

i=1

di ≥ d1 + d4 + d5 + d6 + 2 ≥ 2p + 8.

Proof of Lemma 3. Choose a longest path P = x1
−→
P x2 in G\C so as to maximize |NC (x1)|.

Let y1, ..., yt be the elements of N
+
P (x2) occurring on P in a consecutive order. Put

Pi = x1
−→
P y−i x2

←−
P yi (i = 1, ..., t), H = G[V (y

−
1

−→
P x2)].

Since Pi is a longest path in G\C for each i ∈ {1, ..., t}, we can assume w.l.o.g. that P is
chosen so that |V (H)| is maximum. It follows in particular that NP (yi) ⊆ V (H) (i = 1, ..., t).

Case 1. |NC (x1)| = 0.
Since |NC (x1)| is maximum, we have |NC (yi)| = 0 (i = 1, ..., t), implying that N (yi) ⊆

V (H) and dH (yi) = d(yi) ≥ δ (i = 1, ..., t). Further, since yt = x2, we have dP (x2) ≥ δ,
that is t ≥ δ. By Theorem C, for each distinct u, v ∈ V (H), there is a path in H of length
at least δ, connecting u and v. Since H and C are connected by at least κ vertex disjoint
paths, we have |C| ≥ κ(δ + 2).

Case 2. |NC (x1)| = 1.
Since |NC (x1)| is maximum, we have |NC (yi)| ≤ 1 (i = 1, ..., t), implying that |NH (yi)| ≥

δ − 1 (i = 1, ..., t), where t ≥ δ − 1. By Theorem C, |C| ≥ κ(δ + 1).

Case 3. |NC (x1)| ≥ 2.
If |NC (yi)| ≥ 2 for some i ∈ {1, ..., t}, then we are done. Otherwise |NC (yi)| ≤ 1

(i = 1, ..., t) and, as in Case 2, |C| ≥ κ(δ + 1).

Proof of Theorem 1. If κ ≤ 2, then τ ≤ 1, contradicting the hypothesis. Let κ ≥ 3. Next,
if c ≥ 2δ + 4, then we are done. So, we can assume that

c ≤ 2δ + 3. (1)

Let C be a longest cycle in G and P = x1
−→
P x2 a longest path in G\C of length p. If

|V (P )| ≤ 0, then C is a Hamilton cycle and we are done. Let |V (P )| ≥ 1. Put X =
NC (x1) ∪ NC (x2) and let ξ1, ..., ξs be the elements of X occurring on C in a consecutive
order. Put

Ii = ξi
−→
C ξi+1, I

∗
i = ξ

+
i

−→
C ξ−i+1 (i = 1, ..., s),

where ξs+1 = ξ1.



46 Long Cycles in t-Tough Graphs with t > 1

Claim 1. Let NC (x1) = NC (x2) and let ξa, ξb be two distinct elements of X. If either

|ξa
−→
C y| + |ξb

−→
C z| ≤ p + 2 or |y−→C ξa+1| + |z

−→
C ξb+1| ≤ p + 2 for some y ∈ V (I∗a ) and z ∈ V (I∗b ),

then yz 6∈ E(G).
Proof. Assume the contrary, that is yz ∈ E(G). If |ξa

−→
C y| + |ξb

−→
C z| ≤ p + 2, then

|ξax1
−→
P x2ξb

←−
C yz

−→
C ξa| = |C| − |ξa

−→
C y| − |ξb

−→
C z| + p + 3 ≥ |C| + 1,

a contradiction. By a symmetric argument, we reach a contradiction when |y−→C ξa+1| +
|z−→C ξb+1| ≤ p + 2. ∆

Claim 2. Let NC (x1) = NC (x2) and let ξa, ξb, ξf be distinct elements of X, occurring

on
−→
C in a consecutive order. If ξ−a ξ

+
b ∈ E(G) and |ξf

−→
C y| ≤ p + 1 for some y ∈ V (I∗f ), then

yξa, yξb 6∈ E(G).
Proof. Assume the contrary. If yξa ∈ E(G), then

|ξf x1
−→
P x2ξb

←−
C ξay

−→
C ξ−a ξ

+
b

−→
C ξf| = |C| − |ξf

−→
C y| + p + 2 ≥ |C| + 1,

a contradiction. If yξb ∈ E(G), then

|ξf x1
−→
P x2ξa

−→
C ξby

−→
C ξ−a ξ

+
b

−→
C ξf| ≥ |C| + 1,

a contradiction. ∆

Case 1. p = 0.
It follows that P = x1 and s = d(x1) ≥ δ ≥ 3. Assume first that s ≥ δ + 1. If

Υ(I1, ..., Is) = ∅, then G\{ξ1, ..., ξs} has at least s+1 components, contradicting the fact that
τ > 1. Otherwise Υ(Ia, Ib) 6= ∅ for some distinct a, b ∈ {1, ..., s}. By Lemma 2, |Ia|+|Ib| ≥ 6.
Since C is extreme, we have |Ii| ≥ 2 (i = 1, ..., s) and therefore, c ≥ 6 + 2(s − 2) ≥ 2δ + 4,
contradicting (1). So, s = δ.

The next claim can easily be derived from (1) and Lemma 2.

Claim 3. (1) |Ii| + |Ij| ≤ 7 for each distinct i, j ∈ {1, ..., s}.
(2) If |Ia| + |Ib| = 7 for some distinct a, b ∈ {1, ..., s}, then |Ii| = 2 for each

i ∈ {1, ..., s}\{a, b}.
(3) If |Ia| = 5 for some a ∈ {1, ..., s}, then |Ii| = 2 for each i ∈ {1, ..., s}\{a}.
(4) There are at most three segments of length at least 3.
(5) If |Ia| ≥ 3, |Ib| ≥ 3, |If| ≥ 3 for some distinct a, b, f ∈ {1, ..., s}, then |Ia| = |Ib| =

|If| = 3.

If Υ(I1, ..., Is) = ∅, then G\{ξ1, ..., ξs} has at least s+1 components, contradicting the fact
that τ > 1. Otherwise Υ(Ii, Ij) 6= ∅ for some distinct i, j ∈ {1, ..., s}. Choose a, b ∈ {1, ..., s}
so that Υ(Ia, Ib) 6= ∅ and |Ia|+|Ib| is maximum. By definition, there is an intermediate path
L between Ia and Ib. If |L| ≥ 2, then by Lemma 2,

|Ia| + |Ib| ≥ 2p + 2|L| + 4 ≥ 8,
contradicting Claim 3(1). Otherwise |L| = 1 and therefore,

Υ(I1, ..., Is) ⊆ E(G).



Zh. Nikoghosyan 47

By Lemma 2, |Ia| + |Ib| ≥ 2p + 6 = 6. Combining this with Claim 3(1), we have
6 ≤ |Ia| + |Ib| ≤ 7.

Let L = yz, where y ∈ V (I∗a ) and z ∈ V (I∗b ).

Case 1.1. |Ia| + |Ib| = 6.
Since |Ii| ≥ 2 (i = 1, ..., s), we can assume w.l.o.g. that either |Ia| = 2, |Ib| = 4 or

|Ia| = |Ib| = 3.

Case 1.1.1. |Ia| = 2 and |Ib| = 4.
Put Ia = ξaw1ξa+1 and Ib = ξbw2w3w4ξb+1. Since |Ia| + |Ib| is extreme, we have |Ii| = 2

for each i ∈ {1, ..., s}\{b}. Clearly, y = w1. By Claim 1, z = w3 and Υ(Ia, Ib) = {w1w3}. If
Υ(I1, ..., Is) = {w1w3}, then G\{ξ1, ..., ξs, w3} has at least s + 1 components, contradicting
the fact that τ > 1. Otherwise Υ(If , Ig) 6= ∅ for some distinct f, g ∈ {1, ..., s} with {f, g} 6=
{a, b}. If {f, g} ∩ {a, b} = ∅, then by Lemma 2, |If| + |Ig| ≥ 6 and therefore,

c =
∑

i∈{a,b,f,g}
|Ii| +

∑

i∈{1,2,...,s}\{a,b,f,g}
|Ii| ≥ 12 + 2(s − 4) = 2δ + 4,

contradicting (1). Let {f, g} ∩ {a, b} 6= ∅. If f = a, then clearly g 6= b and by Lemma 2,
|Ia| + |Ig| ≥ 6, implying that |Ig| ≥ 4. But then |Ib| + |Ig| ≥ 8, contradicting Claim 3(1).
Now let f 6= a and g = b. By Lemma 2, |Ib| + |If| ≥ 6. Since |Ia| + |Ib| is extreme, we
have |Ib| + |If| = 6, which yields |If| = 2. Put If = ξf w5ξf +1. Let y1z1 be an intermediate
edge between If and Ib. By Claim 1, y1 = w5 and z1 = w3. Recalling that |Ii| = 2 for
each i ∈ {1, ..., s}\{b}, we conclude that w3 belongs to all intermediate edges in Υ(I1, ..., Is).
Then G\{ξ1, ..., ξs, w3} has at least s + 1 components, contradicting the fact that τ > 1.

Case 1.1.2. |Ia| = |Ib| = 3.
Put Ia = ξaw1w2ξa+1 and Ib = ξbw3w4ξb+1. Assume w.l.o.g. that y = w2. By Claim

1, z = w3 and Υ(Ia, Ib) = {w2w3}. If Υ(I1, ..., Is) = {w2w3}, then G\{ξ1, ..., ξs, w2} has
at least s + 1 components, contradicting the fact that τ > 1. Otherwise Υ(If , Ig) 6= ∅ for
some distinct f, g ∈ {1, ..., s} with {f, g} 6= {a, b}. If {f, g} ∩ {a, b} = ∅, then by Lemma
2, |If| + |Ig| ≥ 6 and, as in Case 1.1.1, c ≥ 12 + 2(s − 4) ≥ 2δ + 4, contradicting (1). Let
{f, g}∩{a, b} 6= ∅. Assume w.l.o.g. that f = a and g 6= b. By Lemma 2, |Ia| + |Ig| ≥ 6, that
is |Ig| ≥ 3. By Claim 3(5), |Ig| = 3. Put Ig = ξgw5w6ξg+1. Let y1z1 be an intermediate edge
with y1 ∈ V (I∗a ) and z1 ∈ V (I∗g ).

Case 1.1.2.1. g ∈ V (ξ+b+1
−→
C ξ−a ).

If y1 = w1, then by Claim 1, z1 = w6 and

ξaw1w6
←−
C w3w2

−→
C ξbx1ξg+1

−→
C ξa

is longer than C, a contradiction. Let y1 = w2. By Claim 1, z1 = w5 and therefore,
Υ(Ia, Ig) = {w2w5}.

Case 1.1.2.1.1. N (w1) ⊆ V (C).
By Claim 2, w1ξb 6∈ E(G) and w1ξg 6∈ E(G). Further, if

N (w1) ⊆ {ξ1, ..., ξs, w2}\{ξb, ξg},



48 Long Cycles in t-Tough Graphs with t > 1

then |N (w1)| ≤ s−1 = δ −1, a contradiction. Otherwise, w1z2 ∈ E(G) for some z2 ∈ V (I∗h),
where h 6∈ {a, b, g}. By Lemma 2, |Ia| + |Ih| ≥ 6, implying that |Ih| ≥ 3, which contradicts
Claim 3(4).

Case 1.1.2.1.2. N (w1) 6⊆ V (C).
It follows that w1x2 ∈ E(G) for some x2 ∈ V (G\C). Since p = 0 and C is extreme,

x2 6= x1 and N (x2) ⊆ V (C). For the same reason, x2ξa 6∈ E(G) and x2w2 6∈ E(G). By Claim
2, x2ξb 6∈ E(G). If

N (x2) ⊆ {ξ1, ..., ξs, w1}\{ξa, ξb},
then |N (x2)| ≤ s − 1 = δ − 1, a contradiction. Otherwise x2z2 ∈ E(G) for some z2 ∈ V (I∗h),
where h 6= a. But then I∗a and I∗h are connected by w1x2z2, contradicting the fact that
Υ(I1, ..., Is) ⊆ E(G).

Case 1.1.2.2. g ∈ V (ξ+a+1
−→
C ξ−b ).

If y1 = w2, then by Claim 1, z1 = w5 and we can argue as in Case 1.1.2.1. Let z1 = w1.
By Claim 1, z2 = w6 and w4w6 6∈ E(G). Further, by Claim 2, w4ξa+1 6∈ E(G) and
w4ξb 6∈ E(G). Using Claim 3(4), we have |Ii| = 2 for each i ∈ {1, ..., s}\{a, b, g}. By
Lemma 2, N (w4) ∩ V (I∗i ) = ∅ for each i ∈ {1, ..., s}\{a, b, g}.

Case 1.1.2.2.1. N (w4) ⊆ V (C).
It follows that

N (w4) ⊆ {ξ1, ..., ξs, w3, w5}\{ξa+1, ξb}.
Since |N (w4)| ≥ δ = s, we have w4w5 ∈ E(G).

Case 1.1.2.2.1.1. s ≥ 4.
Since |Ii| = 2 for each i ∈ {1, ..., s}\{a, b, g}, we can assume w.l.o.g. that |Ia−1| = 2.

Put Ia−1 = ξa−1w7ξa. Assume first that N (w7) 6⊆ V (C), that is w7x2 ∈ E(G) for some
x2 ∈ V (G\C). Since C is extreme and Υ(I1, ..., Is) ⊆ E(G), we have x2 6= x1 and

N (x2) ⊆ {ξ1, ..., ξs, w7}\{ξa−1, ξa, },

contradicting the fact that |N (x2)| ≥ δ = s. Now assume that N (w7) ⊆ V (C). By Claim 2,
w7ξa+1 6∈ E(G). Since |Ia−1| = 2 and |Ii| ≤ 3 for each i ∈ {1, ..., s}, we have by Lemma 2,
N (w7) ∩ V (I∗i ) = ∅ for each i ∈ {1, ..., s}\{a − 1}. So, N (w7) ⊆ {ξ1, ..., ξs}\{ξa+1}, contra-
dicting the fact that |N (w7)| ≥ δ = s.

Case 1.1.2.2.1.2. s = 3.
Put C = ξ1w1w2ξ2w3w4ξ3w5w6ξ1. Assume first that N (wi) 6⊆ V (C) for some i ∈

{1, 2, ..., 6}, say i = 1. This means that w1x2 ∈ E(G) for some x2 ∈ V (G\C). Since
C is extreme, x2 6= x1 and x2ξ1, x2w2 6∈ E(G). Further, since Υ(I1, I2, I3) ⊆ E(G),
we have N (x2) ⊆ {ξ2, ξ3, w1}. On the other hand, since |N (x2)| ≥ δ ≥ 3, we have
N (x2) = {ξ2, ξ3, w1}. By Claim 2, x2ξ2 6∈ E(G), a contradiction. Now assume that
N (wi) ⊆ V (C) (i = 1, ..., 6). If V (G\C) 6= {x1}, then choose x2 ∈ V (G\C) so that x2 6= x1.
Since N (wi) ⊆ V (C) (i = 1, ..., 6), we have N (x2) = N (x1). But then G\{ξ1, ξ2, ξ3} has at
least three components, contradicting the fact that τ > 1. Finally, if V (G\C) = {x1}, then
G is the Petersen graph.



Zh. Nikoghosyan 49

Case 1.1.2.2.2. N (w4) 6⊆ V (C).
It follows that w4ξ2 ∈ E(G) for some x2 ∈ V (G\C). Since C is extreme and

Υ(I1, ..., Is) ⊆ E(G), we have x2 6= x1, x2ξb+1 6∈ E(G) and N (x2) ∩ V (I∗i ) = ∅ for each
i ∈ {1, ..., s}\{b}. So, N (x2) ⊆ {ξ1, ..., ξs, w4}\{ξb+1}, implying that x2ξb ∈ E(G), which
contradicts Claim 2.

Case 1.2. |Ia| + |Ib| = 7.
By Claim 3(2), |Ii| = 2 for each i ∈ {1, ..., s}\{a, b}. By the hypothesis, either |Ia| = 2,

|Ib| = 5 or |Ia| = 3, |Ib| = 4.

Case 1.2.1. |Ia| = 2, |Ib| = 5.
Put Ia = ξaw1ξa+1 and Ib = ξbw2w3w4w5ξb+1. Clearly, y = w1. By Claim 1, z ∈ {w3, w4}.

Further, if {w1w3, w1w4} ⊆ E(G), then

ξax1ξa+1
−→
C w3w1w4

−→
C ξa

is longer than C, a contradiction. Therefore, we can assume w.l.o.g. that w1w3 ∈ E(G) and
Υ(Ia, Ib) = {w1w3}. By Claim 3(3), |Ii| = 2 for each i ∈ {1, ..., s}\{b}. By Lemma 2, each
intermediate edge has one end in V (I∗b ). If Υ(I1, ..., Is) = {w1w3}, then G\{ξ1, ..., ξs, w3}
has at least s + 1 components, contradicting the fact that τ > 1. Otherwise Υ(Ib, Ig) 6= ∅
for some g ∈ {1, ..., s}\{a, b}. Since |Ig| = 2, we can set Ig = ξgw6ξg+1. As above, either
w6w3 ∈ E(G), w6w4 6∈ E(G) or w6w3 6∈ E(G), w6w4 ∈ E(G). Assume that w6w4 ∈ E(G). If
ξg ∈ V (ξ+b+1

−→
C ξ−a ), then

ξaw1w3
←−
C ξa+1x1ξg

←−
C w4w6

−→
C ξa

is longer than C, a contradiction. If ξg ∈ V (ξ+a+1
−→
C ξ−b ), then

ξax1ξg+1
−→
C w3w1

−→
C w6w4

−→
C ξa

is longer than C, a contradiction. Now assume that w6w4 6∈ E(G), implying that
w6w3 ∈ E(G). This means that w3 belongs to each intermediate edge in Υ(I1, ..., Is). But
then G\{ξ1, ..., ξs, w3} has at least s + 1 components, contradicting the fact that τ > 1.

Case 1.2.2. |Ia| = 3, |Ib| = 4.
Put Ia = ξaw1w2ξa+1 and Ib = ξbw3w4w5ξb+1. Assume w.l.o.g. that y = w2. By Claim 1,

z ∈ {w3, w4}.

Case 1.2.2.1. w2w3 ∈ E(G).
Assume first that N (w1) 6⊆ V (C), that is w1x2 ∈ E(G) for some x2 ∈ V (G\C). Since C

is extreme, x2 6= x1 and x2ξa 6∈ E(G), x2w2 6∈ E(G). By Claim 2, x2ξa+1 6∈ E(G). Recalling
that C is extreme and Υ(I1, ..., Is) ⊆ E(G), we have

N (x2) ⊆ {ξ1, ..., ξs, w1}\{ξa, ξa+1},

contradicting the fact that |N (x2)| ≥ δ = s. Now assume that N (w1) ⊆ V (C). By Claim 1,
w1ξa+1 6∈ E(G), w1ξb 6∈ E(G) and w1w3 6∈ E(G). Further, if N (w1)∩{w4, w5} 6= ∅, then there
are two independent intermediate edges between Ia and Ib. By Lemma 2, |Ia| + |Ib| ≥ 8,



50 Long Cycles in t-Tough Graphs with t > 1

contradicting Claim 3(1). Hence, N (w1) ∩ {w4, w5} = ∅. Finally, since |Ii| = 2 for each
i ∈ {1, ..., s}\{a, b}, we have N (w1) ∩ V (I∗i ) = ∅ for each i ∈ {1, ..., s}\{a}. So,

N (w1) ⊆ {ξ1, ..., ξs, w2}\{ξa+1, ξb},
contradicting the fact that |N (w1)| ≥ δ = s when ξa+1 6= ξb. Let ξa+1 = ξb. Assume w.l.o.g.
that a = 1 and b = 2. If s = 2, then clearly τ ≤ 1, contradicting the hypothesis. Let s ≥ 3.
Recalling that |Ii| = 2 for each i ∈ {3, ..., s}, we can set I3 = ξ3w7ξ4. If N (w7) 6⊆ V (C), that
is w7x2 ∈ E(G) for some x2 ∈ V (G\C), then x2 6= x1 and

N (x2) ⊆ {ξ1, ..., ξs, w7}\{ξ3, ξ4},
contradicting the fact that |N (x2)| ≥ δ = s. Let N (w7) ⊆ V (C). By Claim 2, w7ξ2 6∈ E(G).
Hence, N (w7) ⊆ {ξ1, ..., ξs}\{ξ2}, contradicting the fact that |N (w7)| ≥ s.

Case 1.2.2.2. w2w4 ∈ E(G).
If w2w3 ∈ E(G), then we can argue as in Case 1.2.2.1. Hence, we can assume that

Υ(Ia, Ib) = {w2w4}. If Υ(I1, ..., Is) = {w2w4}, then clearly τ ≤ 1, contradicting the hypoth-
esis. Let Υ(I1, ..., Is) 6= {w2w4}. Since |Ia| = 3 and |Ii| = 2 for each i ∈ {1, ..., s}\{a, b}, we
can state by Lemma 2 that each intermediate edge has one end in V (I∗b ). Let y1z1 ∈ E(G)
for some y1 ∈ V (I∗g ) and z1 ∈ V (I∗b ), where g ∈ {1, ..., s}\{a, b}. Since |Ig| = 2, we can set
Ig = ξgw6ξg+1. Clearly y1 = w6. By Claim 1, z1 = w4. This means that w4 belongs to all
intermediate edges. Then clearly τ ≤ 1, contradicting the hypothesis.

Case 2. p = 1.
Since δ ≥ κ ≥ 3, we have |NC (xi)| ≥ δ − p = δ − 1 ≥ 2 (i = 1, 2).

Case 2.1. NC (x1) 6= NC (x2).
It follows that max{σ1, σ2} ≥ 1, where

σ1 = |NC (x1)\NC (x2)|, σ2 = |NC (x2)\NC (x1)|.
If max{σ1, σ2} ≥ 2, then by Lemma 1, c ≥ 3δ + 1 ≥ 2δ + 4, contradicting (1). Let
max{σ1, σ2} = 1. This implie s ≥ δ and |Ii| ≥ 3 (i = 1, ..., s). If s ≥ δ + 1, then
c ≥ 3s ≥ 3δ + 3 > 2δ + 4, again contradicting (1). Let s = δ, that is |Ii| = 3 (i = 1, ..., s).
By Lemma 2, Υ(I1, ..., Is) = ∅, contradicting the fact that τ > 1.

Case 2.2. NC (x1) = NC (x2).
Clearly, s = |NC (x1)| ≥ δ − p = δ − 1. If s ≥ δ, then c ≥ 3s ≥ 3δ and we can argue as in

Case 2.1. Let s = δ − 1.
The following can easily be derived from (1) and Lemma 2.

Claim 4. (1) |Ii| + |Ij| ≤ 9 for each distinct i, j ∈ {1, ..., s}.
(2) If |Ia| + |Ib| = 9 for some distinct a, b ∈ {1, ..., s}, then |Ii| = 3 for each

i ∈ {1, ..., s}\{a, b}.
(3) If |Ia| = 6 for some a ∈ {1, ..., s}, then |Ii| = 3 for each i ∈ {1, ..., s}\{a}.
(4) There are at most three segments of length at least 4.
(5) If |Ia| ≥ 4, |Ib| ≥ 4, |If| ≥ 4 for some distinct a, b, f ∈ {1, 2, ..., s}, then

|Ia| = |Ib| = |If| = 4.



Zh. Nikoghosyan 51

If Υ(I1, ..., Is) = ∅, then clearly, τ ≤ 1, contradicting the hypothesis. Otherwise
Υ(Ia, Ib) 6= ∅ for some distinct a, b ∈ {1, ..., s}. By definition, there is an intermediate
path L between Ia and Ib. If |L| ≥ 2, then by Lemma 2,

|Ia| + |Ib| ≥ 2p + 2|L| + 4 ≥ 10,

contradicting Claim 4(1). Otherwise |L| = 1 and therefore,

Υ(I1, ..., Is) ⊆ E(G).

By Lemma 2, |Ia| + |Ib| ≥ 2p + 6 = 8. Combining this with Claim 4(1), we have

8 ≤ |Ia| + |Ib| ≤ 9.

Let L = yz, where y ∈ V (I∗a ) and z ∈ V (I∗b ).

Case 2.2.1. |Ia| + |Ib| = 8.
Since |Ii| ≥ 3 (i = 1, ..., s), we can assume w.l.o.g. that either |Ia| = 3, |Ib| = 5 or

|Ia| = |Ib| = 4.

Case 2.2.1.1. |Ia| = 3 and |Ib| = 5.
Put Ia = ξaw1w2ξa+1 and Ib = ξbw3w4w5w6ξb+1. Assume w.l.o.g. that y = w2. By Claim

1, z = w4. For the same reason, N (w1) ∩ V (I∗b ) ⊆ {w5}. If w1w5 ∈ E(G), then there exist
two independent intermediate edges between Ia and Ib, which by Lemma 2 yield |Ia|+ |Ib| ≥
2p + 8 = 10, contradicting Claim 4(1). So, N (w1) ∩ V (I∗b ) = ∅. Further, if Υ(Ia, If ) 6= ∅
for some f ∈ {1, ..., s}\{a, b}, then by Lemma 2, |Ia| + |If| ≥ 2p + 6 = 8, implying that
|If| ≥ 5. But then |Ib| + |If| ≥ 10, contradicting Claim 4(1). Hence Υ(Ia, Ii) = ∅ for each
i ∈ {1, ..., s}\{a, b}. By Claim 2, w1ξa+1 6∈ E(G). Thus, if N (w1) ⊆ V (C), then

N (w1) ⊆ {ξ1, ..., ξs, w2}\{ξa+1},

contradicting the fact that |N (w1)| ≥ δ = s + 1. Now let N (w1) 6⊆ V (C) and let Q =
w1
−→
Q x3 be a longest path having only w1 in common with C. Clearly, 1 ≤ |Q| ≤ 2 and

V (Q) ∩ V (P ) = ∅. By Claim 2, x3ξa+1 6∈ E(G). Further, since Υ(I1, ..., Is) ⊆ E(G), we have
N (x3) ∩ V (I∗i ) = ∅ for each i ∈ {1, ..., s}\{a}. If |Q| = 1, then

N (x3) ⊆ {ξ1, ..., ξs, w1}\{ξa, ξa+1},

contradicting the fact that |N (x3)| ≥ δ = s + 1. If |Q| = 2, then

N (x3) ⊆ {ξ1, ..., ξs, x−3 , w1}\{ξa, ξa+1},

contradicting the fact that |N (x3)| ≥ δ = s + 1.

Case 2.2.1.2. |Ia| = |Ib| = 4.
Put Ia = ξaw1w2w3ξa+1 and Ib = ξbw4w5w6ξb+1.

Case 2.2.1.2.1. y ∈ {w1, w3}.
Assume w.l.o.g. that y = w3. By Claim 1, z = w4.



52 Long Cycles in t-Tough Graphs with t > 1

Claim 5. N (w1) ∪ N (w2) ⊆ V (C).
Proof. Assume the contrary and let Q = w1

−→
Q x3 be a longest path having only w1 in

common with C. Clearly, 1 ≤ |Q| ≤ 2 and V (Q) ∩ V (P ) = ∅. By Claim 2, x3ξa+1 6∈ E(G)
and x3ξb 6∈ E(G). Since Υ(I1, ..., Is) ⊆ E(G), we have N (x3) ∩ V (I∗i ) = ∅ for each i ∈
{1, ..., s}\{a}. If |Q| = 1, then

N (x3) ⊆ {ξ1, ..., ξs, w1, w3}\{ξa, ξa+1},

contradicting the fact that |N (x3)| ≥ δ = s + 1. If |Q| = 2, then

N (x3) ⊆ {ξ1, ..., ξs, x−3 , w1}\{ξa, ξa+1},

a contradiction. Similarly, we can reach a contradiction when N (w2) 6⊆ V (C). Claim 5 is
proved. ∆

Case 2.2.1.2.1.1. ξa+1 6= ξb.
By Claim 2, w1ξa+1 6∈ E(G) and w1ξb 6∈ E(G). By Claim 1, w1w4 6∈ E(G). Moreover, if

N (w1) ∩ V (I∗b ) 6= ∅, then there exist two independent intermediate edges between Ia and Ib,
which by Lemma 2 yield |Ia| + |Ib| ≥ 2p + 8 ≥ 10, contradicting Claim 4(1). Furthermore,
if N (w1) ∩ V (I∗i ) = ∅ for each i ∈ {1, ..., s}\{a, b}, then by Claim 5,

N (w1) ⊆ {ξ1, ..., ξs, w2, w3}\{ξa+1, ξb},

implying that |N (w1)| ≤ s = δ−1, a contradiction. Otherwise, w1v ∈ E(G), where v ∈ V (I∗f )
for some f ∈ {1, ..., s}\{a, b}. By a similar way, it can be shown that w2u ∈ E(G), where
u ∈ V (I∗g ) for some g ∈ {1, ..., s}\{a, b}. By Lemma 2, |Ia|+|If| ≥ 2p+6 = 8, that is |If| ≥ 4.
By Claim 4(5), |If| = 4. By a symmetric argument, |Id| = 4. Put If = ξf w7w8w9ξf +1. By
Claim 1, v = w9, i.e., w1w9 ∈ E(G). If d = f , then |Υ(Ia, If )| = 2 and by Lemma 2,
|Ia| + |If| ≥ 2p + 7 = 9, a contradiction. Otherwise, there are at least four elementary
segments of length at least 4, contradicting Claim 4(4).

Case 2.2.1.2.1.2. ξa+1 = ξb.
Assume w.l.o.g. that a = 1 and b = 2. If Υ(I1, I2, ..., Is) = Υ(I1, I2) = {w3w4}, then

clearly, τ ≤ 1, a contradiction. Otherwise, there is an intermediate edge uv such that
u ∈ V (I∗1 ) ∪ V (I∗2 ) and v ∈ V (I∗f ) for some f ∈ {1, 2, ..., s}\{1, 2}. Assume w.l.o.g. that
u ∈ V (I∗1 ). If u = w3, then as above, ξ2 = ξf , a contradiction. Let u 6= w3. By Lemma 2,
|I1| + |If| ≥ 8, i.e. |If| ≥ 4. By Claim 4(5), |If| = 4. Put If = ξcw7w8w9ξf +1. If u = w1,
then by Claim 1, v = w9 and

|ξ1w1w9
←−
C w4w3ξ2x2x1ξf +1

−→
C ξ1| ≥ |C| + 1,

a contradiction. If u = w2, then by Claim 1, v = w8 and

|ξ1w1w2w8
←−
C w4w3ξ2x2x1ξf +1

−→
C ξ1| ≥ |C| + 1,

again a contradiction.

Case 2.2.1.2.2. y = w2.



Zh. Nikoghosyan 53

By Claim 1, z = w5 and Υ(Ia, Ib) = {w2w5}. If |Ii| = 3 for each i ∈ {1, 2, ..., s}\{a, b},
then by Lemma 2, Υ(I1, I2, ..., Is) = {w2w5} and τ ≤ 1, contradicting the hypothesis. Oth-
erwise, |If| ≥ 4 for some f ∈ {1, 2, ..., s}\{a, b} and |Ii| = 3 for each i ∈ {1, 2, ..., s}\{a, b, f}.
By Claim 4(5), |If| = 4. Put If = ξf w7w8w9ξf +1. Clearly, Υ(I1, I2, ..., Is) = Υ(Ia, Ib, If ).
If Υ(Ia, If ) = Υ(Ib, If ) = ∅, then again τ ≤ 1, a contradiction. Let uv ∈ E(G), where
u ∈ I∗a ∪ I∗b and v ∈ V (I∗f ). Assume w.l.o.g. that u ∈ V (I∗a ). If u ∈ {w1, w3}, then we can
argue as in Case 1.2.1.2.1. Let u = w2. By Claim 1, v = w8. If w1w3 ∈ E(G), then

ξax1x2ξb
←−
C w3w1w2w5

−→
C ξa

is longer than C, a contradiction. Let w1w3 6∈ E(G). Analogously, w4w6 6∈ E(G) and
w7w9 6∈ E(G). But then {w1, w3, w4, w6, w7, w9} is an independent set of vertices and
G\{ξ1, ..., ξs, w2, w5, w8} has at least s + 4 connected components. Hence τ < 1, contra-
dicting the hypothesis.

Case 2.2.2. |Ia| + |Ib| = 9.
Since |Ii| ≥ 3 (i = 1, ..., s), we can assume w.l.o.g. that either |Ia| = 3, |Ib| = 6 or

|Ia| = 4, |Ib| = 5.

Case 2.2.2.1. |Ia| = 3 and |Ib| = 6.
By Claim 4(3), |Ii| = 3 for each i ∈ {1, ..., s}\{b}. Put

Ia = ξaw1w2ξa+1, Ib = ξbw3w4w5w6w7ξb+1.

Since |Ia| = 3, we can assume w.l.o.g. that y = w2. By Claim 1, z ∈ {w4, w5}.

Case 2.2.2.1.1. z = w4.
By Claim 1, w1w4 6∈ E(G). Next, if N (w1) ∩ V (I∗b ) 6= ∅, then there are two independent

intermediate edges between Ia and Ib and by Lemma 2, |Ia|+|Ib| ≥ 2p+8 = 10, contradicting
Claim 4(1). By Claim 2, w1ξa+1 6∈ E(G). Finally, by Lemma 2 and Claim 4(3), N (w1) ∩
V (I∗i ) = ∅ for each i ∈ {1, ..., s}\{a, b}. So, if N (w1) ⊆ V (C), then

N (w1) ⊆ {ξ1, ..., ξs, w2}\{ξa+1},
contradicting the fact that |N (w1)| ≥ δ = s + 1. Now assume that N (w1) 6⊆ V (C). Choose
a longest path Q = w1

−→
Q x3 having only w1 in common with C. Clearly, V (Q) ∩ V (P ) = ∅.

Since C is extreme, x3ξa 6∈ E(G) and x3x2 6∈ E(G). If x3ξa+1 ∈ E(G), then

ξax1x2ξb
←−
C ξa+1x3

←−
Q w1w2w4

−→
C ξa

is longer than C, a contradiction. Let x3ξa+1 6∈ E(G). If |Q| = 1, then
N (x3) ⊆ {ξ1, ..., ξs, w1}\{ξa, ξa+1},

contradicting the fact that |N (x3)| ≥ δ = s + 1. If |Q| = 2, then
N (x3) ⊆ {ξ1, ..., ξs, x−3 , w1}\{ξa, ξa+1},

contradicting the fact that |N (x3)| ≥ δ = s + 1.



54 Long Cycles in t-Tough Graphs with t > 1

Case 2.2.2.1.2. z = w5.
If w2w4 ∈ E(G), then we can argue as in Case 2.2.2.1.1. Let w2w4 6∈ E(G). It means

that w5 belongs to all intermediate edges. This implies τ ≤ 1, contradicting the hypothesis.

Case 2.2.2.2. |Ia| = 4 and |Ib| = 5.
By Claim 4(2), |Ii| = 3 and Υ(Ia, Ii) = ∅ for each i ∈ {1, ..., s}\{a, b}. If Υ(Ib, If ) 6= ∅ for

some f ∈ {1, ..., s}\{a, b}, then we can argue as in Case 2.2.1.1. Otherwise Υ(I1, ..., Is) =
Υ(Ia, Ib). If there are two independent edges in Υ(Ia, Ib), then by Lemma 2, |Ia| + |Ib| ≥ 10,
contradicting Claim 4(1). Otherwise τ ≤ 1, a contradiction.

Case 3. 2 ≤ p ≤ δ − 3.
It follows that |NC (xi)| ≥ δ − p ≥ 3 (i = 1, 2). If NC (x1) 6= NC (x2), then by Lemma 1,

|C| ≥ 4δ − 2p ≥ 3δ − p + 3 ≥ 2δ + 4, contradicting (1). Hence NC (x1) = NC (x2), implying
that |Ii| ≥ p + 2 (i = 1, 2, ..., s). Clearly, s ≥ |NC (x1)| − (|V (P )| − 1) ≥ δ − p ≥ 3. If
s ≥ δ − p + 1, then

|C| ≥ s(p + 2) ≥ (δ − p + 1)(p + 2)
= (δ − p − 1)(p − 1) + 3δ − p + 1 ≥ 3δ − p + 3 ≥ 2δ + 4,

again contradicting (1). Hence s = δ − p. It means that x1x2 ∈ E(G), that is G[V (P )]
is Hamiltonian. By symmetric arguments, NC (y) = NC (x1) for each y ∈ V (P ). If
Υ(I1, I2, ..., Is) = ∅, then τ ≤ 1, contradicting the hypothesis. Otherwise Υ(Ia, Ib) 6= ∅
for some elementary segments Ia and Ib. By definition, there is an intermediate path L
between Ia and Ib. If |L| ≥ 2, then by lemma 2,

|Ia| + |Ib| ≥ 2p + 2|L| + 4 ≥ 2p + 8.

Hence
|C| = |Ia| + |Ib| +

∑

i∈{1,...,s}\{a,b}
|Ii| ≥ 2p + 8 + (s − 2)(p + 2)

= (δ − p − 2)(p − 1) + 3δ − p + 2 ≥ 3δ − p + 3 ≥ 2δ + 4,
contradicting (1). Thus, |L| = 1, i.e. Υ(I1, I2, ..., Is) ⊆ E(G). By Lemma 2,

|Ia| + |Ib| ≥ 2p + 2|L| + 4 = 2p + 6,

which yields

|C| = |Ia| + |Ib| +
∑

i∈{1,...,s}\{a,b}
|Ii| ≥ 2p + 6 + (s − 2)(p + 2)

= (s − 2)(p − 2) + (δ − p − 3) + (3δ − p + 1) ≥ 3δ − p + 1 ≥ 2δ + 4,
contradicting (1).

Case 4. 2 ≤ p = δ − 2.
It follows that |NC (xi)| ≥ δ − p = 2 (i = 1, 2). If NC (x1) 6= NC (x2), then by Lemma 1,

|C| ≥ 4δ − 2p = 3δ − p + 2 = 2δ + 4, contradicting (1). Hence, NC (x1) = NC (x2). Clearly,
s = |NC (x1)| ≥ 2. Further, if s ≥ 3, then

|C| ≥ s(p + 2) ≥ 3δ ≥ 3δ − p + 2 = 2δ + 4,



Zh. Nikoghosyan 55

again contradicting (1). Hence, s = 2. It follows that x1x2 ∈ E(G), that is G[V (P )] is
Hamiltonian. By symmetric arguments, NC (v) = NC (x1) = {ξ1, ξ2} for each v ∈ V (P ).
If Υ(I1, I2) = ∅, then clearly, τ ≤ 1, contradicting the hypothesis. Otherwise, there is an
intermediate path L = yz such that y ∈ V (I∗1 ) and z ∈ V (I∗2 ). If |L| ≥ 2, then by Lemma 2,

|C| = |I1| + |I2| ≥ 2p + 2|L| + 4 ≥ 2p + 8 = 3δ − p + 2 = 2δ + 4,
contradicting (1). Hence |L| = 1, implying that Υ(I1, I2) ⊆ E(G). If there are two inde-
pendent intermediate edges between I1, I2, then by Lemma 2, |C| = |I1| + |I2| ≥ 2p + 8 =
3δ − p + 2 = 2δ + 4, contradicting (1). Otherwise τ ≤ 1, contradicting the hypothesis.

Case 5. 2 ≤ p = δ − 1.
It follows that |NC (xi)| ≥ δ − p = 1 (i = 1, 2).

Case 5.1. |NC (xi)| ≥ 2 (i = 1, 2).
If NC (x1) 6= NC (x2), then by Lemma 1, |C| ≥ 2p + 8 = 3δ −p + 5 > 2δ + 4, contradicting

(1). Hence, NC (x1) = NC (x2). Clearly s ≥ 2. Further, if s ≥ 3, then
|C| ≥ s(p + 2) ≥ 3(δ + 1) > 2δ + 4,

contradicting (1). Let s = 2. Since κ ≥ 3, there is an edge zw such that z ∈ V (P ) and
w ∈ V (C)\{ξ1, ξ2}. Assume w.l.o.g. that w ∈ V (I∗1 ). Then it is easy to see that |I1| ≥ δ + 3.
Since |I2| ≥ δ + 1, we have |C| ≥ 2δ + 4, contradicting (1).

Case 5.2. Either |NC (x1)| = 1 or |NC (x2)| = 1.
Assume w.l.o.g. that |NC (x1)| = 1. Put NC (x1) = {y1}. If NC (x1) 6= NC (x2),

then x2y2 ∈ E(G) for some y2 ∈ V (C)\{y1} and we can argue as in Case 4.1. Let
NC (x1) = NC (x2) = {y1}. Since κ ≥ 1, there is an edge zw such that z ∈ V (P ) and
w ∈ V (C)\{y1}. Clearly, z 6∈ {x1, x2} and x2z− ∈ E(G), where z− is the previous vertex of
z along

−→
P . Then replacing P with x1

−→
P z−x2

←−
P z, we can argue as in Case 4.1.

Case 6. p ≥ δ.
If |C| ≥ κ(δ + 1), then clearly |C| ≥ 2δ + 4, contradicting (1). Otherwise, by Lemma 3,

we can assume that |NC (xi)| ≥ 2 (i = 1, 2). Then |C| ≥ 2(p + 2) ≥ 2δ + 4, contradicting (1).

4. Conclusion

The present work studied the lower bound for the length of a longest cycle in a simple graph
in terms of toughness and minimum degree. Received lower bound is a natural extension of
the results due to Bauer and Schmeichel.

References

[1] J. A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan, London
and Elsevier, New York 1976.

[2] G. A. Dirac, “Some theorems on abstract graphs”, Proc. London, Math. Soc., vol. 2,
pp. 69-81, 1952.



5 6 Long Cycles in t-Tough Graphs with t > 1

[3 ] D . B a u e r a n d E . S c h m e ic h e l, L ong Cycles in Tough Graphs, Te c h n ic a l R e p o r t 8 6 1 2 ,
S t e ve n s In s t it u t e o f Te c h n o lo g y, 1 9 8 6 .

[4 ] H .-J. V o s s , \ B r id g e s o f lo n g e s t c ir c u it s a n d o f lo n g e s t p a t h s in g r a p h s " , B eitrage
zur Graphentheorie und deren Anwendungen, V o r g e t r . a u f d e m . in t . K o llo q., Ob e r h o f
( D D R ) , p p . 2 7 5 -2 8 6 , 1 9 7 7 .

Submitted 23.02.2019, accepted 18.04.2019.

ºñϳñ óÇÏÉ»ñ 1-Çó Ù»Í ÏáßïáõÃÛáõÝ áõÝ»óáÕ ·ñ³ýÝ»ñáõÙ

Äáñ³ ¶. ÜÇÏáÕáëÛ³Ý

ÐÐ ¶²² ÆÝýáñÙ³ïÇϳÛÇ ¨ ³íïáÙ³ï³óÙ³Ý åñáµÉ»ÙÝ»ñÇ ÇÝëïÇïáõï

e-mail: zhora@ipia.sci.am

²Ù÷á÷áõÙ

²å³óáõóíáõÙ ¿, áñ »Ã» ± Ýí³½³·áõÛÝ ³ëïÇ×³Ý áõÝ»óáÕ n-·³·³Ã³ÝÇ ·ñ³ýÝ áõÝÇ
1-Çó Ù»Í ÏáßïáõÃÛáõÝ, ³å³ ³ÛÝ áõÝÇ ³éÝí³½Ý m in fn; 2 ± + 4 g »ñϳñáõÃÛ³Ý óÇÏÉ, ϳÙ

ÏáßïáõÃÛáõÝ:

Äëèííûå öèêëû â t-æåñòêèõ ãðàôàõ ïðè t > 1

Æîðà Ã. Íèêîãîñÿí

Èíñòèòóò ïðîáëåì èíôîðìàòèêè è àâòîìàòèçàöèè ÍÀÍ ÐÀ
e-mail: zhora@ipia.sci.am

Àííîòàöèÿ

Äîêàçûâàåòñÿ, ÷òî ëþáîé n-âåðøèííûé t-æåñòêèé ãðàô ñ ìèíèìàëüíîé
ñòåïåíüþ ± ïðè t > 1 èìååò öèêë äëèíû íå ìåíüøå m in fn; 2 ± + 4 g.

Êëþ÷åâûå ñëîâà: ãàìèëüòîíîâûé öèêë, îêðóæåíèå, ìèíèìàëüíûé ñòåïåíü,
ïðî÷íîñòü.

 

ѳÙÁÝÏÝáõÙ ¿ ä»ï»ñë»ÝÇ ·ñ³ýÇ Ñ»ï:
´³Ý³ÉÇ µ³é»ñ՝     ѳÙÇÉïáÝÛ³Ý óÇÏÉ, »ñϳñ³·áõÛÝ óÇÏÉ, Ýí³½³·áõÛÝ óÇÏÉ, ³ëïÇ׳Ý,


	3_
	3_Nikoghosyan