D:\TeX_522\main.DVI


Mathematical Problems of Computer Science 52, 14{20, 2019.

U D C 5 1 9 .1

Relative Lengths of P aths and Cycles in 2-Connected

Gr aphs

Zh o r a G. N iko g h o s ya n

Institute for Informatics and Automation Problems of NAS RA

e-mail: zhora@ipia.sci.am

Abstract

Let l be the length of a longest path in a 2-connected graph G and c the circum-
ference - the length of a longest cycle in G. In 1952, Dirac proved that c >

p
2l, by

noting that "actually c ¸ 2
p

l, but the proof of this result, which is best possible,
is rather complicated". Let L1; L2; :::; Lm be a vine on a longest path of G. In this
paper, using the parameter m, we present a more general sharp bound for the circum-
ference c including the bound c ¸ 2

p
l as an immediate corollary, based on elementary

arguments.
Keywords: Longest cycle, Longest path, Circumference, Vine.

1 . In t r o d u c t io n

W e c o n s id e r o n ly u n d ir e c t e d g r a p h s wit h n o lo o p s o r m u lt ip le e d g e s . L e t G b e a 2 -c o n n e c t e d
g r a p h . W e u s e c a n d l t o d e n o t e t h e c ir c u m fe r e n c e ( t h e le n g t h o f a lo n g e s t c yc le ) a n d t h e
le n g t h ( t h e n u m b e r o f e d g e s ) o f a lo n g e s t p a t h o f G. A g o o d r e fe r e n c e fo r a n y u n d e ¯ n e d
t e r m s is [1 ].

In 1 9 5 2 , D ir a c [2 ] p r o ve d t h e fo llo win g .

T heor em A: [2 ]. In every 2-connected graph, c >
p

2 l.

In t h e s a m e p a p e r [2 ], D ir a c c o n s id e r e d a s h a r p ve r s io n o f Th e o r e m A b y n o t in g t h a t
" a c t u a lly c ¸ 2

p
l, b u t t h e p r o o f o f t h is r e s u lt , wh ic h is b e s t p o s s ib le , is r a t h e r c o m p lic a t e d " .

A n a lo g o u s qu e s t io n s we r e s t u d ie d fo r k-c o n n e c t e d g r a p h s wh e n k ¸ 3 b y B o n d y a n d L o c ke
( [4 ],[5 ]) .

In t h is p a p e r , u s in g a n e w p a r a m e t e r , we p r e s e n t a m o r e g e n e r a l s h a r p b o u n d fo r t h e
c ir c u m fe r e n c e c in 2 -c o n n e c t e d g r a p h s in t e r m s o f l a n d t h e le n g t h o f a vin e o n a lo n g e s t
p a t h o f G, in c lu d in g t h e b o u n d c ¸ 2

p
l a s a c o r o lla r y, b a s e d o n e le m e n t a r y a r g u m e n t s . In

o r d e r t o fo r m u la t e t h is r e s u lt , we n e e d s o m e a d d it io n a l d e ¯ n it io n s a n d n o t a t io n s .
Th e s e t o f ve r t ic e s o f a g r a p h G is d e n o t e d b y V ( G) a n d t h e s e t o f e d g e s b y E ( G) . If Q

is a p a t h o r a c yc le , t h e n t h e le n g t h o f Q, d e n o t e d b y l ( Q ) , is jE ( Q ) j - t h e n u m b e r o f e d g e s
in Q. W e wr it e a c yc le Q wit h a g ive n o r ie n t a t io n b y

¡!
Q . Fo r x; y 2 V ( Q ) , we d e n o t e b y

1 4



Zh. Nikoghosyan 1 5

x
¡!
Q y t h e s u b p a t h o f Q in t h e c h o s e n d ir e c t io n fr o m x t o y. W e u s e P = x

¡!
P y t o d e n o t e a

p a t h wit h e n d ve r t ic e s x a n d y in t h e d ir e c t io n fr o m x t o y. W e s a y t h a t ve r t e x z1 p r e c e d e s

ve r t e x z2 o n
¡!
Q if z1, z2 o c c u r o n

¡!
Q in t h is o r d e r , a n d in d ic a t e t h is r e la t io n s h ip b y z1 Á z2.

W e will wr it e z1 ¹ z2 wh e n e it h e r z1 = z2 o r z1 Á z2.
L e t P = x

¡!
P y b e a p a t h . A vin e o f le n g t h m o n P is a s e t

fLi = xi
¡!
L iyi : 1 · i · mg

o f in t e r n a lly-d is jo in t p a t h s s u c h t h a t

( a ) V ( Li ) \ V ( P ) = fxi; yig ( i = 1 ; :::; m) ,
( b ) x = x1 Á x2 Á y1 ¹ x3 Á y2 ¹ x4 Á ::: ¹ xm Á ym¡1 Á ym = y o n P .

Th e m a in r e s u lt is t h e fo llo win g .

T heor em 1: L et G be a 2-connected graph. If fL1; L2; :::; Lmg is a vine on a longest path
of G, then

c ¸

8
>><
>>:

2l
m+1

+ m+1
2

; when m is odd;

2l¡ 1
2

m+1
+ m+1

2
; when m is even:

E quivalently, Theorem 1 can be formulated as follows, implying D irac's conjecture as an im-
mediate corollary.

T heor em 2: L et G be a 2-connected graph. If fL1; L2; :::; Lmg is a vine on a longest path
of G, then

c ¸

8
>><
>>:

q
4 l + ( c ¡ m ¡ 1 ) 2; when m is odd;

q
4 l + ( c ¡ m ¡ 1 ) 2 ¡ 1 ; when m is even:

Cor ollar y 1: In every 2-connected graph, c ¸ 2
p

l.

Note that if m is odd, then c > 2
p

l.
The following lemma guarantees the existence of at least one vine on a longest path in a

2-connected graph.
T he Vine Lemma: [3 ]. L et G be a k-connected graph and P a path in G. Then there are
k ¡ 1 pairwise-disjoint vines on P .

2 . P r o o fs

P r oof of T heor em 1. L e t P = x
¡!
P y b e a lo n g e s t p a t h in G a n d le t

fLi = xi
¡!
L iyi : 1 · i · mg

b e a vin e o f le n g t h m o n P . P u t



1 6 Relative Lengths of Paths and Cycles in 2-Connected Graphs

Li = xi
¡!
L iyi ( i = 1 ; :::; m) ; A1 = x1

¡!
P x2; Am = ym¡1

¡!
P ym;

Ai = yi¡1
¡!
P xi+1 ( i = 2 ; 3 ; :::; m ¡ 1 ) ;

Bi = xi+1
¡!
P yi ( i = 1 ; :::; m ¡ 1 ) ;

l ( Ai ) = ai ( i = 1 ; :::; m ) ; l ( Bi ) = bi ( i = 1 ; :::; m ¡ 1 ) :
U s in g t h e g ive n vin e L1; L2; :::; Lm, we c o n s t r u c t a n u m b e r o f a p p r o p r ia t e c yc le s a n d

o b t a in a lo we r b o u n d fo r t h e c ir c u m fe r e n c e a s a m e a n o f t h e ir le n g t h s . Fir s t , we p u t

Q0 =
m[

i=1

( Ai [ Li ) ;

Qi =
m¡i[

j=i+1

( Aj [ Lj ) [ Bi [ Bm¡i;

wh e r e i 2 f 1 ; 2 ; :::; ( m ¡ 1 ) = 2 g wh e n m is o d d , a n d i 2 f 1 ; 2 ; :::; ( m ¡ 2 ) =2 g wh e n m is e ve n .
S in c e l ( Li ) ¸ 1 ( i = 1 ; 2 ; :::; m) a n d a1 ¸ 1 , am ¸ 1 , we h a ve

c ¸ l ( Q0 ) =
mX

i=1

l ( Li ) + a1 + am +
m¡1X

i=2

ai ¸ m + a1 + am: ( 1 )

Case 1. m is o d d .
Fo r e a c h i 2 f 1 ; 2 ; :::; ( m ¡ 1 ) = 2 g, we h a ve

c ¸ l ( Qi ) = bi + bm¡i +
m¡iX

j=i+1

( aj + l ( Lj ) )

¸ bi + bm¡i +
m¡iX

j=i+1

aj + m ¡ 2 i: ( 2 )

B y s u m m in g ( 1 ) a n d ( 2 ) , we g e t

m + 1

2
c ¸

m¡1
2X

i=0

l ( Qi ) ¸
m¡1X

i=1

bi +
mX

i=1

ai +
m + 1

2
m ¡ 2

m¡1
2X

i=1

i:

S in c e l =
Pm¡1

i=1 bi +
Pm

i=1 ai, we h a ve

m + 1

2
c ¸ l + m + 1

2
m ¡ m

2 ¡ 1
4

= l +
( m + 1 ) 2

4
;

im p lyin g t h a t

c ¸ 2 l
m + 1

+
m + 1

2
:

Case 2. m is e ve n .
A s in Ca s e 1 , fo r e a c h i 2 f 1 ; 2 ; :::; ( m ¡ 2 ) =2 g,

c ¸ l ( Qi ) ¸ bi + bm¡i +
m¡iX

j=i+1

aj + m ¡ 2 i: ( 3 )



Zh. Nikoghosyan 1 7

Case 2.1. 1
2
c ¸ b m

2
.

B y s u m m in g ( 1 ) , ( 3 ) a n d 1
2
c ¸ b m

2
, we g e t

m

2
c +

1

2
c ¸

Ã
m¡1X

i=1

bi +
mX

i=1

ai

!
+

m¡2
2X

i=0

( m ¡ 2 i)

= l +
m

2
m ¡ 2

m¡2
2X

i=0

i = l +
m ( m + 2 )

4
;

im p lyin g t h a t

c ¸
2 l ¡ 1

2

m + 1
+

m + 1

2
:

Case 2.2. 1
2
( c + 1 ) · b m

2
.

P u t

R0 = B m
2
[

m
2[

i=1

( Ai [ Li ) ;

Rm = B m
2
[

m[

i= m+2
2

( Ai [ Li ) :

Fu r t h e r , fo r e a c h i 2 f 1 ; 2 ; :::; m¡2
2

g, we p u t

Ri = B m
2
[ Bi [

m
2[

j=i+1

( Aj [ Lj ) ;

Rm¡i = B m
2
[ Bm¡i [

m¡i[

j= m+2
2

( Aj [ Lj ) :

Th e n c le a r ly,

c ¸ l ( R0 ) = b m
2

+

m
2X

i=1

( ai [ l ( Li ) ) ¸ b m
2

+

m
2X

i=1

ai +
m

2
; ( 4 )

c ¸ l ( Rm ) = b m
2

+
mX

i=
m+2

2

( ai [ l ( Li ) )

¸ b m
2

+
mX

i=
m+2

2

ai +
m

2
: ( 5 )

Fu r t h e r m o r e , fo r e a c h i 2 f 1 ; 2 ; :::; m¡2
2

g,

c ¸ l ( Ri ) = b m
2

+ bi +

m
2X

j=i+1

( aj + l ( Lj ) )

¸ b m
2

+ bi +
m

2
¡ i; ( 6 )



1 8 Relative Lengths of Paths and Cycles in 2-Connected Graphs

c ¸ l ( Rm¡i ) = b m
2

+ bm¡i +
m¡iX

j= m+2
2

( aj + l ( Lj ) )

¸ b m
2

+ bm¡i +
m

2
¡ i: ( 7 )

B y s u m m in g ( 4 ) , ( 5 ) , ( 6 ) a n d ( 7 ) , we g e t

mc ¸ mb m
2

+
mX

i=1

ai +

Ã
m¡1X

i=1

bi ¡ b m
2

!
+ m

m

2
¡ 2

m¡2
2X

i=1

i

= ( m ¡ 1 ) b m
2

+

Ã
mX

i=1

ai +
m¡1X

i=1

bi

!
+

m2 + 2 m

4

¸ ( m ¡ 1 ) ( c + 1 )
2

+ l +
m2 + 2 m

4
;

im p lyin g t h a t

c ¸ 2 l
m + 1

+
( m + 2 ) 2 ¡ 6

2 ( m + 1 )
¸

2 l ¡ 1
2

m + 1
+

m + 1

2
:

Th e o r e m 1 is p r o ve d .

P r oof of T heor em 2. B y ( 1 ) , c ¸ m + a1 + a2 ¸ m + 2 . L e t c = m + y + 2 fo r s o m e in t e g e r
y ¸ 0 . B y s u b s t it u t in g m = c ¡ y ¡ 2 in Th e o r e m 1 , we g e t

c ¸
q

4 l + ( y + 1 ) 2 =
q

4 l + ( c ¡ m ¡ 1 ) 2

wh e n m is o d d ; a n d

c ¸
q

4 l + y2 =
q

4 l + ( c ¡ m ¡ 2 ) 2

wh e n m is e ve n . Th e o r e m 2 is p r o ve d .

To s h o w t h e s h a r p n e s s o f t h e b o u n d s in Th e o r e m s 1 a n d 2 , le t P = x
¡!
P y b e a p a t h a n d

le t

fLi = xi
¡!
L iyi : 1 · i · mg

b e a vin e o n P . P u t

Li = xi
¡!
L iyi ( i = 1 ; :::; m) ; A1 = x1

¡!
P x2; Am = ym¡1

¡!
P ym;

Ai = yi¡1
¡!
P xi+1 ( i = 2 ; 3 ; :::; m ¡ 1 ) ; Bi = xi+1

¡!
P yi ( i = 1 ; :::; m ¡ 1 ) ;

l ( Ai ) = ai ( i = 1 ; :::; m ) ; l ( Bi ) = bi ( i = 1 ; :::; m ¡ 1 ) :
L e t y ¸ 0 b y a n in t e g e r a n d

a1 = am =
y

2
+ 1 ; a2 = a3 = ::: = am¡1 = 0 ;

bi = bm¡i =
y

2
+ i + 1 ( i = 1 ; 2 ; :::; b( m ¡ 1 ) =2 c) :



Zh. Nikoghosyan 1 9

If m is o d d , t h e n it is e a s y t o s e e t h a t

c = m + y + 2 =
2 l

m + 1
+

m + 1

2
=

q
4 l + ( c ¡ m ¡ 1 ) 2:

If m is e ve n , we p u t bm=2 =
y
2

+ m+2
2

, im p lyin g t h a t

c = m + y + 2 =
2 l ¡ 1

2

m + 1
+

m + 1

2
=

q
4 l + ( c ¡ m ¡ 1 ) 2 ¡ 1 :

Th u s , t h e b o u n d s in Th e o r e m s 1 a n d 2 a r e b e s t p o s s ib le .

References

[1 ] J.A . B o n d y a n d U .S .R . Mu r t y, Graph Theory with Applications, Ma c m illa n , L o n d o n
a n d E ls e vie r , N e w Y o r k, 1 9 7 6 .

[2 ] G.A . D ir a c , \ S o m e t h e o r e m s o n a b s t r a c t g r a p h s " , P roc. L ondon, M ath. Soc., vo l. 2 , p p .
6 9 -8 1 , 1 9 5 2 .

[3 ] J. A . B o n d y, B asic Graph Theory: P aths and Circuits, H a n d b o o k o f c o m b in a t o r ic s , vo l.
1 ,2 , E ls e vie r , A m s t e r d a m , 1 9 9 0 .

[4 ] J. A . B o n d y a n d S . C. L o c ke , \ R e la t ive le n g t h s o f p a t h s a n d c yc le s in k-c o n n e c t e d
g r a p h s " , Annals of D iscrete M athematics, vo l. 8 , p p . 2 5 3 -2 5 9 , 1 9 8 0 .

[5 ] S .C. L o c ke , \ R e la t ive le n g t h s o f p a t h s a n d c yc le s in k-c o n n e c t e d g r a p h s " , J . of Comb.
Theory, S e r ie s B 3 2 , p p . 2 0 6 -2 2 2 , 1 9 8 2 .

Submitted 25.05.2019, accepted 10.10.2019.

ÞÕóݻñÇ ¨ óÇÏÉ»ñÇ Ñ³ñ³µ»ñ³Ï³Ý »ñϳñáõÃÛáõÝÝ»ñÇ Ù³ëÇÝ
2-ϳå³Ïóí³Í ·ñ³ýÝ»ñáõÙ

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

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

e-mail: zhora@ipia.sci.am

²Ù÷á÷áõÙ

¸Çóáõù l-Á 2-ϳå³Ïóí³Í G ·ñ³ýÇ ³Ù»Ý³»ñϳñ ßÕóÛÇ »ñϳñáõÃÛáõÝÝ ¿, ÇëÏ
c-Ý` ³Ù»Ý³»ñϳñ óÇÏÉÇ »ñϳñáõÃÛáõÝÁ: ¸Çñ³ÏÁ 1952-ÇÝ óáõÛó ïí»ó, áñ c >

p
2 l,

ÙÇ³Å³Ù³Ý³Ï Ýß»Éáí, áñ Çñ³Ï³ÝáõÙ c ¸ 2
p

l, áñÁ Ñݳñ³íáñ É³í³·áõÛÝÝ ¿, µ³Ûó
³Ûë ·Ý³Ñ³ï³Ï³ÝÇ ³å³óáõÛóÁ µ³í³Ï³Ý³ã³÷ µ³ñ¹ ¿: ¸Çóáõù L1; L2; :::; Lm-
Á G ·ñ³ýÇ ³Ù»Ý³»ñϳñ ßÕóÛÇ íñ³ ÙÇ µ³Õ»Õ ¿: Ü»ñϳ ³ß˳ï³ÝùáõÙ m
å³ñ³Ù»ïñÇ û·ÝáõÃÛ³Ùµ µVñíáõÙ ¿ ÙÇ ³í»ÉÇ ÁݹѳÝáõñ ·Ý³Ñ³ï³Ï³Ý, áñï»ÕÇó



2 0 Relative Lengths of Paths and Cycles in 2-Connected Graphs

c ¸ 2
p

l ·Ý³Ñ³ï³Ï³ÝÁ µËáõÙ ¿ áñå»ë ³ÝÙÇç³Ï³Ý ѻ勉Ýù` ÑÇÙÝí³Í áã µ³ñ¹
¹³ïáÕáõÃÛáõÝÝ»ñÇ íñ³:

´³Ý³ÉÇ µ³é»ñ` ³Ù»Ý³»ñϳñ óÇÏÉ, ³Ù»Ý³»ñϳñ ßÕó, ³Ù»Ý³»ñϳñ óÇÏÉÇ
»ñϳñáõÃÛáõÝ, µ³Õ»Õ:

Îòíîñèòåëüíûå äëèíû öåïåé è öèêëîâ â 2-ñâÿçíûõ ãðàôàõ

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

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

Àííîòàöèÿ

Ïóñòü l îáîçíà÷àåò äëèíó äëèííåéøåé öåïè ãðàôà G, à c îáîçíà÷àåò äëèíó
äëèííåéøåãî öèêëà. Â 1952ã. Äèðàê äîêàçàë, ÷òî c >

p
2 l, îòìåòèâ, ÷òî ”â

ñàìîì äåëå èìååò ìåñòî c ¸ 2
p

l, ÷òî óëó÷øèòü íåâîçìîæíî, íî äîêàçàòåëüñòâî
ýòîé îöåíêè äîñòàòî÷íî ñëîæíî”. Ïóñòü L1; L2; :::; Lm - ïëþù íà äëèííåéøåé
öåïè ãðàôà G. Â íàñòîÿùåé ðàáîòå ïðèâîäèòñÿ íîâàÿ áîëåå îáùàÿ îöåíêà,
îòêóäà âûòåêàåò ñïðàâåäëèâîñòü îöåíêè c ¸ 2

p
l êàê íåïîñðåäñòâåííîå ñëåäñòâèå,

îñíîâàííîå íà ýëýìåíòàðíûõ ñîîáðàæåíèé.
Êëþ÷åâûå ñëîâà: äëèííåéøèé öèêë, äëèíííåéøàÿ öåïü, äëèíà äëèííåéøåãî

öèêëà, ïëþù.