Nikoghosyan_ARTicle.DVI


Mathematical Problems of Computer Science 50, 15{34, 2018.

A Shar p I mpr ovement of a T heor em of B auer and

Schmeichel

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 G be a graph on n vertices with minimum degree ±. The earliest nontrivial
lower bound for the circumference c (the length of a longest cycle in G) was estab-
lished in 1952 due to Dirac in terms of n and ±: (i) if G is a 2-connected graph, then
c ¸ minfn; 2±g. The bound in Theorem (i) is sharp. In 1986, Bauer and Schmeichel
gave a version of this classical result for 1-tough graphs: (ii) if G is a 1-tough graph,
then c ¸ minfn; 2±+2g. In this paper we present an improvement of (ii), which is sharp
for each n: (iii) if G is a 1-tough graph, then c ¸ minfn; 2± + 2g when n ´ 1(mod 3);
c ¸ minfn; 2± + 3g when n ´ 2(mod 3) or n ´ 1(mod 4); and c ¸ minfn; 2± + 4g
otherwise.

Keywords: Hamilton cycle; circumference; minimum degree; 1-tough graphs.

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

Th r o u g h o u t t h is a r t ic le we c o n s id e r o n ly ¯ n it e u n d ir e c t e d g r a p h s wit h o u t lo o p s o r m u lt ip le
e d g e 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) .
W e u s e n, ± a n d c t o d e n o t e t h e o r d e r o f G, t h e m in im u m d e g r e e a n d 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 in G, r e s p e c t ive ly. 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
[2 ].

Th e e a r lie s t n o n t r ivia l lo we r b o u n d fo r t h e c ir c u m fe r e n c e wa s e s t a b lis h e d in 1 9 5 2 d u e t o
D ir a c [4 ] in t e r m s o f n a n d ±:

T heor em A [4]: If G is a 2-connected graph, then c ¸ m in fn; 2 ±g.

Th e b o u n d 2 ± in Th e o r e m A is s h a r p .
In 1 9 7 3 , Ch v¶a t a l [3 ] in t r o d u c e d t h e c o n c e p t o f t o u g h n e s s . S in c e t h e n a lo t o f r e s e a r c h h a s

b e e n d o n e t o wa r d s ¯ n d in g t h e e xa c t a n a lo g s o f c la s s ic a l H a m ilt o n ia n r e s u lt s u n d e r a d d it io n a l
1 -t o u g h c o n d it io n in s t e a d o f 2 -c o n n e c t ivit y - a n a lt e r n a t ive a n d s t r o n g e r n e c e s s a r y c o n d it io n
fo r a g r a p h t o b e H a m ilt o n ia n .

Th e a n a lo g o f t h e c la s s ic a l Th e o r e m A fo r 1 -t o u g h g r a p h s wa s e s t a b lis h e d b y B a u e r a n d
S c h m e ic h e l ( [1 ], 1 9 8 6 ) .

1 5



1 6 A Sharp Improvement of a Theorem of Bauer and Schmeichel

T heor em B [1]: If G is a 1-tough graph, then c ¸ m in fn; 2 ± + 2 g.

Th e b o u n d 2 ± + 2 in Th e o r e m B is s h o wn [1 ] t o b e s h a r p b y c o n s t r u c t in g g r a p h s o f o r d e r
n ´ 1 ( mod 3 ) wit h c = 2 ± + 2 .

In t h is p a p e r we s h o w t h a t t h e b o u n d 2 ± + 2 in Th e o r e m B is s h a r p if a n d o n ly if
n ´ 1 ( mod 3 ) . Fu r t h e r m o r e , we p r e s e n t a s h a r p r e ¯ n e m e n t o f Th e o r e m B , wh ic h is s h a r p
fo r e a c h n.

T heor em 1: E very 1-tough graph is either Hamiltonian, or

c ¸

8
><
>:

2 ± + 2 when n ´ 1 ( mod 3 ) ;
2 ± + 3 when n ´ 2 ( mod 3 ) or n ´ 1 ( mod 4 ) ;
2 ± + 4 otherwise:

To s e e t h a t Th e o r e m 1 is s h a r p fo r e a c h n, le t H1; H2; :::; Hh b e d is jo in t c o m p le t e g r a p h s
wit h d is t in c t ve r t ic e s xi; yi 2 V ( Hi ) ( i = 1 ; 2 ; :::; h) . Fo r m a n e w g r a p h H ( t1; t2; :::; th )
b y id e n t ifyin g t h e ve r t ic e s x1; x2; :::; xh a n d a d d in g a ll p o s s ib le e d g e s b e t we e n y1; y2; :::; yh,
wh e r e ti = jV ( Hi ) j ( i = 1 ; 2 ; :::; h) . Th e g r a p h H ( ± + 1 ; ± + 1 ; ± + 1 ) s h o ws t h a t t h e b o u n d
2 ± + 2 in Th e o r e m 1 c a n n o t b e r e p la c e d b y 2 ± + 3 wh e n n ´ 1 ( mod 3 ) . N e xt , t h e g r a p h s
H ( ± + 2 ; ± + 1 ; ± + 1 ) a n d H ( ± + 1 ; ± + 1 ; ± + 1 ; ± + 1 ) s h o w t h a t t h e b o u n d 2 ± + 3 c a n n o t b e
r e p la c e d b y 2 ±+4 wh e n n ´ 2 ( mod 3 ) o r n ´ 1 ( mod 4 ) . Fin a lly, t h e g r a p h H ( ±+2 ; ±+2 ; ±+1 )
s h o ws t h a t t h e b o u n d 2 ± + 4 c a n n o t b e r e p la c e d b y 2 ± + 5 .

2 . N o t a t io n s a n d P r e lim in a r ie s

L e t G b e a g r a p h . Fo r S a s u b s e t o f V ( G) , we d e n o t e b y GnS t h e m a xim u m s u b g r a p h o f G
wit h ve r t e x s e t V ( G) nS. W e wr it e hSi fo r t h e s u b g r a p h o f G in d u c e d b y S. Fo r a s u b g r a p h
H o f G we u s e GnH s h o r t fo r GnV ( H ) . Th e n e ig h b o r h o o d a n d t h e d e g r e e o f a ve r t e x
x 2 V ( G) will b e d e n o t e d b y N ( x) a n d d( x ) , r e s p e c t ive ly. Fu r t h e r m o r e , fo r a s u b g r a p h H o f
G a n d x 2 V ( G) , we d e ¯ n e NH ( x ) = N ( x ) \ V ( H ) a n d dH ( x ) = jNH ( x ) j. L e t s( G ) d e n o t e
t h e n u m b e r o f c o m p o n e n t s o f a g r a p h G. A g r a p h G is 1 -t o u g h if jSj ¸ s( GnS ) fo r e ve r y
s u b s e t S o f t h e ve r t e x s e t V ( G) wit h s( GnS ) > 1 . A g r a p h G o n n ve r t ic e s is H a m ilt o n ia n
if G c o n t a in s a H a m ilt o n c yc le , i.e ., a c yc le o f le n g t h n.

P a t h s a n d c yc le s in a g r a p h G a r e c o n s id e r e d a s s u b g r a p h s o f 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 jQj, is jE ( Q ) j. W e wr it e 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 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. Fo r x 2 V ( C ) , we d e n o t e t h e h-t h s u c c e s s o r a n d t h e h-t h p r e d e c e s s o r o f x o n ¡!C b y
x+h a n d x¡h, r e s p e c t ive ly. W e a b b r e via t e x+1 a n d x¡1 b y x+ a n d x¡, r e s p e c t ive ly. Fo r e a c h
X ½ V ( C ) , we d e ¯ n e X+ = fx+jx 2 Xg a n d X¡ = fx¡jx 2 Xg.

Special de¯nitions. L e t G b e a g r a p h , C a lo n g e s t c yc le in G a n d P = x
¡!
P y a lo n g e s t

p a t h in GnC o f le n g t h p ¸ 0 . L e t »1; »2; :::; »s b e t h e e le m e n t s o f NC ( x ) [ NC ( y ) o c c u r r in g
o n

¡!
C in a c o n s e c u t ive o r d e r . S e t

Ii = »i
¡!
C »i+1; I

¤
i = »

+
i

¡!
C »¡i+1 ( i = 1 ; 2 ; :::; s) ;

wh e r e »s+1 = »1.



Zh. Nikoghosyan 1 7

( 1 ) Th e s e g m e n t s I1; I2; :::; Is a r e c a lle d e le m e n t a r y s e g m e n t s o n C in d u c e d b y NC ( x ) [
NC ( y ) .

( 2 ) W e c a ll a p a t h L = z
¡!
L w a n in t e r m e d ia t e p a t h b e t we e n t wo d is t in c t e le m e n t a r y

s e g m e n t s Ia a n d Ib, if

z 2 V ( I¤a ) ; w 2 V ( I¤b ) ; V ( L) \ V ( C [ P ) = fz; wg:

( 3 ) D e ¯ n e (̈ Ii1; Ii2; :::; Iit ) t o b e t h e s e t o f a ll in t e r m e d ia t e p a t h s b e t we e n e le m e n t a r y
s e g m e n t s Ii1 ; Ii2 ; :::; Iit .

( 4 ) If (̈ I1; :::; Is ) µ E, t h e n t h e m a xim u m n u m b e r o f in t e r m e d ia t e in d e p e n d e n t e d g e s
( n o t h a vin g a c o m m o n ve r t e x) in (̈ I1; :::; Is ) will b e d e n o t e d b y ¹ ( )̈ .

( 5 ) W e s a y t h a t t wo in t e r m e d ia t e in d e p e n d e n t e d g e s w1w2; w3w4 h a ve a c r o s s in g , if e it h e r

w1; w3; w2; w4 o r w1; w4; w2; w3 o c c u r o n
¡!
C in a c o n s e c u t ive o r d e r .

Lemma 1: L et G be a graph, C a longest cycle in G and P = x
¡!
P y a longest path in GnC

of length p ¸ 1 . If jNC ( x ) j ¸ 2 , jNC ( y ) j ¸ 2 and NC ( x) 6= NC ( y ) , then

c ¸
(

3 ± + m a xf¾1; ¾2g ¡ 1 ¸ 3 ± if p = 1 ;
4 ± ¡ 2 p if p ¸ 2 ;

where ¾1 = jNC ( x ) nNC ( y ) j and ¾2 = jNC ( y ) nNC ( x ) j.

Lemma 2: L et G be a graph, C a longest cycle in G and P = x
¡!
P y a longest path in GnC

of length p ¸ 0 . L et NC ( x ) = NC ( y ) , jNC ( x ) j ¸ 2 and f; g 2 f 1 ; :::; sg.

(a1) If L 2 (̈ If ; Ig ) , then

jIf j + jIgj ¸ 2 p + 2 jLj + 4 :

(a2) If (̈ If ; Ig ) µ E ( G ) and j (̈ If ; Ig ) j = " for some " 2 f 1 ; 2 ; 3 g, then

jIf j + jIgj ¸ 2 p + " + 5 ;

(a3) If (̈ If ; Ig ) µ E ( G ) and (̈ If ; Ig ) contains two independent intermediate edges, then

jIfj + jIgj ¸ 2 p + 8 :

Th e fo llo win g r e s u lt is d u e t o V o s s [5 ].

Lemma 3 [5]: L et G be a Hamiltonian graph, fv1; v2; :::; vtg µ 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.



1 8 A Sharp Improvement of a Theorem of Bauer and Schmeichel

3 . P r o o fs

P r oof of Lemma 1. P u t

A1 = NC ( x ) nNC ( y ) ; A2 = NC ( y ) nNC ( x ) ; M = NC ( x) \ NC ( y ) :

B y t h e h yp o t h e s is , NC ( x ) 6= NC ( y ) , im p lyin g t h a t

m a xfjA1j; jA2jg ¸ 1 :

L e t »1; »2; :::; »s b e t h e e le m e n t s o f NC ( x ) [ NC ( y ) o c c u r r in g o n
¡!
C in a c o n s e c u t ive o r d e r .

P u t Ii = »i
¡!
C »i+1 ( i = 1 ; 2 ; :::; s) , wh e r e »s+1 = »1. Cle a r ly, s = jA1j + jA2j + jMj. S in c e C is

e xt r e m e , we h a ve jIij ¸ 2 ( i = 1 ; 2 ; :::; s) . N e xt , if f»i; »i+1g\M 6= ; fo r s o m e i 2 f 1 ; 2 ; :::; sg,
t h e n jIij ¸ p + 2 . Fu r t h e r , if e it h e r »i 2 A1, »i+1 2 A2 o r »i 2 A2, »i+1 2 A1, t h e n a g a in
jIij ¸ p + 2 .

Case 1. p = 1 .
Case 1.1. jAij ¸ 1 ( i = 1 ; 2 ) .
It fo llo ws t h a t a m o n g I1; I2; :::; Is t h e r e a r e jMj + 2 s e g m e n t s o f le n g t h a t le a s t p + 2 .

Ob s e r vin g a ls o t h a t e a c h o f t h e r e m a in in g s ¡ ( jMj + 2 ) s e g m e n t s h a s a le n g t h a t le a s t 2 , we
h a ve

c ¸ ( p + 2 ) ( jMj + 2 ) + 2 ( s ¡ jMj ¡ 2 )
= 3 ( jMj + 2 ) + 2 ( jA1j + jA2j ¡ 2 ) = 2 jA1j + 2 jA2j + 3 jMj + 2 :

S in c e jA1j = d( x ) ¡ jMj ¡ 1 a n d jA2j = d( y ) ¡ jMj ¡ 1 , we h a ve

c ¸ 2 d ( x) + 2 d( y ) ¡ jMj ¡ 2 ¸ 3 ± + d ( x) ¡ jMj ¡ 2 :

R e c a llin g t h a t d( x ) = jMj + jA1j + 1 , we g e t

c ¸ 3 ± + jA1j ¡ 1 = 3 ± + ¾1 ¡ 1 :

A n a lo g o u s ly, c ¸ 3 ± + ¾2 ¡ 1 . S o ,

c ¸ 3 ± + m a xf¾1; ¾2g ¡ 1 ¸ 3 ±:

Case 1.2. E it h e r jA1j ¸ 1 ; jA2j = 0 o r jA1j = 0 ; jA2j ¸ 1 .
A s s u m e w.l.o .g . t h a t jA1j ¸ 1 a n d jA2j = 0 , i.e . jNC ( y ) j = jMj ¸ 2 a n d s = jA1j + jMj.

H e n c e , a m o n g I1; I2; :::; Is t h e r e a r e jMj + 1 s e g m e n t s o f le n g t h a t le a s t p + 2 = 3 . Ta kin g
in t o a c c o u n t t h a t jMj + 1 = d( y ) a n d e a c h o f t h e r e m a in in g s ¡ ( jMj + 1 ) s e g m e n t s h a s a
le n g t h a t le a s t 2 , we g e t

c ¸ 3 ( jMj + 1 ) + 2 ( s ¡ jMj ¡ 1 ) = 3 d( y ) + 2 ( jA1j ¡ 1 )

¸ 3 ± + jA1j ¡ 1 = 3 ± + m a xf¾1; ¾2g ¡ 1 ¸ 3 ±:
Case 2. p ¸ 2 .
Case 2.1. jAij ¸ 1 ( i = 1 ; 2 ) .
It fo llo ws t h a t a m o n g I1; I2; :::; Is t h e r e a r e jMj + 2 s e g m e n t s o f le n g t h a t le a s t p + 2 .

Fu r t h e r , s in c e e a c h o f t h e r e m a in in g s ¡ ( jMj + 2 ) s e g m e n t s h a s a le n g t h a t le a s t 2 , we g e t

c ¸ ( p + 2 ) ( jMj + 2 ) + 2 ( s ¡ jMj ¡ 2 )



Zh. Nikoghosyan 1 9

= ( p ¡ 2 ) jMj + ( 2 p + 4 jMj + 4 ) + 2 ( jA1j + jA2j ¡ 2 )
¸ 2 jA1j + 2 jA2j + 4 jMj + 2 p:

Ob s e r vin g a ls o t h a t

jA1j + jMj + p ¸ d ( x) ; jA2j + jMj + p ¸ d( y ) ;

we h a ve

2 jA1j + 2 jA2j + 4 jMj + 2 p
¸ 2 d( x ) + 2 d( y ) ¡ 2 p ¸ 4 ± ¡ 2 p;

im p lyin g t h a t c ¸ 4 ± ¡ 2 p.

Case 2.2. E it h e r jA1j ¸ 1 ; jA2j = 0 o r jA1j = 0 ; jA2j ¸ 1 .
A s s u m e w.l.o .g . t h a t jA1j ¸ 1 a n d jA2j = 0 , t h a t is jNC ( y ) j = jMj ¸ 2 a n d s = jA1j+jMj.

It fo llo ws t h a t a m o n g I1; I2; :::; Is t h e r e a r e jMj+1 s e g m e n t s o f le n g t h a t le a s t p+2 . Ob s e r vin g
a ls o t h a t jMj + p ¸ d( y ) ¸ ±, i.e ., 2 p + 4 jMj ¸ 4 ± ¡ 2 p, we g e t

c ¸ ( p + 2 ) ( jMj + 1 ) ¸ ( p ¡ 2 ) ( jMj ¡ 1 ) + 2 p + 4 jMj

¸ 2 p + 4 jMj ¸ 4 ± ¡ 2 p:

P r oof of Lemma 2. L e t »1; »2; :::; »s b e t h e e le m e n t s o f NC ( x ) o c c u r r in g o n
¡!
C in a c o n -

s e c u t ive o r d e r . P u t Ii = »i
¡!
C »i+1 ( i = 1 ; 2 ; :::; s) , wh e r e »s+1 = »1: To p r o ve ( a1 ) , le t

L 2 (̈ If ; Ig ) . Fu r t h e r , le t L = z
¡!
L w wit h z 2 V ( I¤f ) a n d w 2 V ( I¤g ) . P u t

j»f
¡!
C zj = d1; jz

¡!
C »f+1j = d2; j»g

¡!
C wj = d3; jw

¡!
C »g+1j = d4;

C0 = »f x
¡!
P y»g

á
C z

¡!
L w

¡!
C »f :

Cle a r ly,

jC0j = jCj ¡ d1 ¡ d3 + jLj + jP j + 2 :
S in c e C is e xt r e m e , we h a ve jCj ¸ jC0j, im p lyin g t h a t d1 + d3 ¸ p + jLj + 2 . B y a s ym m e t r ic
a r g u m e n t , d2 + d4 ¸ p + jLj + 2 . H e n c e

jIf j + jIgj =
4X

i=1

di ¸ 2 p + 2 jLj + 4 :

Th e p r o o f o f ( a1 ) is c o m p le t e . To p r o ve ( a 2 ) a n d ( a 3 ) , le t (̈ If ; Ig ) µ E ( G) a n d
j (̈ If ; Ig ) j = " fo r s o m e " 2 f 1 ; 2 ; 3 g.

Case 1. " = 1 .
L e t L 2 (̈ If ; Ig ) , wh e r e jLj = 1 . B y ( a 1 ) ,

jIf j + jIgj ¸ 2 p + 2 jLj + 4 = 2 p + 6 :

Case 2. " = 2 .



2 0 A Sharp Improvement of a Theorem of Bauer and Schmeichel

It fo llo ws t h a t (̈ If ; Ig ) c o n s is t s o f t wo e d g e s e1; e2. P u t e1 = z1w1 a n d e2 = z2w2, wh e r e
fz1; z2g µ V ( I¤f ) a n d fw1; w2g µ V ( I¤g ) .

Case 2.1. z1 6= z2 a n d w1 6= w2.
A s s u m e w.l.o .g . t h a t z1 a n d z2 o c c u r in t h is o r d e r o n If .

Case 2.1.1. w2 a n d w1 o c c u r in t h is o r d e r o n Ig.
P u t

j»f
¡!
C z1j = d1; jz1

¡!
C z2j = d2; jz2

¡!
C »f +1j = d3;

j»g
¡!
C w2j = d4; jw2

¡!
C w1j = d5; jw1

¡!
C »g+1j = d6;

C0 = »f
¡!
C z1w1

á
C w2z2

¡!
C »gx

¡!
P y»g+1

¡!
C »f :

Cle a r ly,

jC0j = jCj ¡ d2 ¡ d4 ¡ d6 + jfe1gj + jfe2gj + jP j + 2
= jCj ¡ d2 ¡ d4 ¡ d6 + p + 4 :

S in c e C is e xt r e m e , we h a ve jCj ¸ jC0j, im p lyin g t h a t d2 + d4 + d6 ¸ p + 4 . B y a s ym m e t r ic
a r g u m e n t , d1 + d3 + d5 ¸ p + 4 . H e n c e

jIfj + jIgj =
6X

i=1

di ¸ 2 p + 8 :

Case 2.1.2. w1 a n d w2 o c c u r in t h is o r d e r o n Ig.
P u t t in g

C0 = »f
¡!
C z1w1

¡!
C w2z2

¡!
C »gx

¡!
P y»g+1

¡!
C »f ;

we c a n a r g u e a s in Ca s e 2 .1 .1 .

Case 2.2. E it h e r z1 = z2, w1 6= w2 o r z1 6= z2, w1 = w2.
A s s u m e w.l.o .g . t h a t z1 6= z2, w1 = w2 a n d z1; z2 o c c u r in t h is o r d e r o n If . P u t

j»f
¡!
C z1j = d1; jz1

¡!
C z2j = d2; jz2

¡!
C »f +1j = d3;

j»g
¡!
C w1j = d4; jw1

¡!
C »g+1j = d5;

C0 = »f x
¡!
P y»g

á
C z1w1

¡!
C »f ;

C00 = »f
¡!
C z2w1

á
C »f+1x

¡!
P y»g+1

¡!
C »f :

Cle a r ly,

jC0j = jCj ¡ d1 ¡ d4 + jfe1gj + jP j + 2 = jCj ¡ d1 ¡ d4 + p + 3 ;

jC00j = jCj ¡ d3 ¡ d5 + jfe2gj + jP j + 2 = jCj ¡ d3 ¡ d5 + p + 3 :
S in c e C is e xt r e m e , jCj ¸ jC0j a n d jCj ¸ jC00j, im p lyin g t h a t

d1 + d4 ¸ p + 3 ; d3 + d5 ¸ p + 3 :



Zh. Nikoghosyan 2 1

H e n c e ,

jIf j + jIgj =
5X

i=1

di ¸ d1 + d3 + d4 + d5 + 1 ¸ 2 p + 7 :

Case 3. " = 3 .
It fo llo ws t h a t (̈ If ; Ig ) c o n s is t s o f t h r e e e d g e s e1; e2; e3. L e t ei = ziwi ( i = 1 ; 2 ; 3 ) ,

wh e r e fz1; z2; z3g µ V ( I¤f ) a n d fw1; w2; w3g µ V ( I¤g ) . If t h e r e a r e t wo in d e p e n d e n t e d g e s
a m o n g e1; e2; e3, t h e n we c a n a r g u e a s in Ca s e 2 .1 . Ot h e r wis e , we c a n a s s u m e w.l.o .g . t h a t
w1 = w2 = w3 a n d z1; z2; z3 o c c u r in t h is o r d e r o n If . P u t

j»f
¡!
C z1j = d1; jz1

¡!
C z2j = d2; jz2

¡!
C z3j = d3;

jz3
¡!
C »f+1j = d4; j»g

¡!
C w1j = d5; jw1

¡!
C »g+1j = d6;

C0 = »f x
¡!
P y»g

á
C z1w1

¡!
C »f ;

C00 = »f
¡!
C z3w1

á
C »f+1x

¡!
P y»g+1

¡!
C »f :

Cle a r ly,
jC0j = jCj ¡ d1 ¡ d5 + jfe1gj + p + 2 ;
jC00j = jCj ¡ d4 ¡ d6 + jfe3gj + p + 2 :

S in c e C is e xt r e m e , we h a ve jCj ¸ jC0j a n d jCj ¸ jC00j, im p lyin g t h a t

d1 + d5 ¸ p + 3 ; d4 + d6 ¸ p + 3 :

H e n c e ,

jIf j + jIgj =
6X

i=1

di ¸ d1 + d4 + d5 + d6 + 2 ¸ 2 p + 8 :

P r oof of T heor em 1. L e t G b e a 1 -t o u g h g r a p h . If c ¸ 2 ± + 4 , t h e n we a r e d o n e . H e n c e ,
we c a n a s s u m e t h a t

c · 2 ± + 3 : ( 1 )
L e t C b e a lo n g e s t c yc le in G a n d P = x1

¡!
P x2 a lo n g e s t p a t h in GnC. P u t jP j =

jV ( P ) j ¡ 1 = p. If jV ( P ) j = 0 , t h e n C is a H a m ilt o n c yc le a n d we a r e d o n e . L e t jV ( P ) j ¸ 1 ,
t h a t is p ¸ 0 . P u t X = NC ( x1 ) [ NC ( x2 ) a n d le t »1; :::; »s b e t h e e le m e n t s o f X o c c u r r in g o n
C in a c o n s e c u t ive o r d e r . P u t

Ii = »i
¡!
C »i+1; I

¤
i = »

+
i

¡!
C »¡i+1 ( i = 1 ; :::; s) ;

wh e r e »s+1 = »1: S in c e G is a 1 -t o u g h g r a p h , we h a ve ± ¸ 2 .

Case 1. p · ± ¡ 2 .
It fo llo ws t h a t s ¸ jNC ( xi ) j ¸ ± ¡ p ¸ 2 ( i = 1 ; 2 ) . A s s u m e ¯ r s t t h a t NC ( x1 ) 6= NC ( x2 ) ,

im p lyin g t h a t p ¸ 1 . If p ¸ 2 , t h e n b y L e m m a 1 , c ¸ 4 ± ¡ 2 p ¸ 2 ± + 4 , c o n t r a d ic t in g
( 1 ) . H e n c e p = 1 , wh ic h yie ld s ± ¸ p + 2 = 3 . B y L e m m a 1 , c ¸ 3 ± ¸ 9 . If ± ¸ 4 , t h e n
c ¸ 3 ± ¸ 2 ± + 4 , c o n t r a d ic t in g ( 1 ) . L e t ± = 3 . N e xt , we c a n s u p p o s e t h a t c = 9 , s in c e
o t h e r wis e c ¸ 1 0 = 3 ± + 1 = 2 ± + 4 , c o n t r a d ic t in g ( 1 ) . Fu r t h e r , we c a n s u p p o s e t h a t s ¸ 3 ,
s in c e NC ( x1 ) = NC ( x2 ) wh e n s = 2 , c o n t r a d ic t in g t h e h yp o t h e s is . Fin a lly, we c a n s u p p o s e



2 2 A Sharp Improvement of a Theorem of Bauer and Schmeichel

t h a t s = 3 , s in c e c le a r ly c ¸ 1 0 wh e n s ¸ 4 , a c o n t r a d ic t io n . Th u s , jI1j = jI2j = jI3j = 3 a n d
it is n o t h a r d t o s e e t h a t Gnf»1; »2; »3g h a s a t le a s t fo u r c o m p o n e n t s , c o n t r a d ic t in g ¿ ¸ 1 .

N o w a s s u m e t h a t NC ( x1 ) = NC ( x2 ) . S in c e C is e xt r e m e , we h a ve

jIij ¸ j»ix1
¡!
P x2»i+1j ¸ p + 2 ( i = 1 ; :::; s) :

Case 1.1. s ¸ ± ¡ p + 1 .
Cle a r ly,

c =
sX

i=1

jIij ¸ s( p + 2 )

¸ ( ± ¡ p + 1 ) ( p + 2 ) = ( ± ¡ p ¡ 2 ) p + 2 ± + p + 2 : ( 2 )
If p ¸ 2 , t h e n b y ( 2 ) , c ¸ 2 ± + 4 , c o n t r a d ic t in g ( 1 ) . L e t p · 1 .

Case 1.1.1. p = 0 .

If (̈ I1; :::; Is ) = ;, t h e n Gnf»1; :::; »sg h a s a t le a s t s + 1 c o m p o n e n t s , c o n t r a d ic t in g t h e
fa c t t h a t ¿ ¸ 1 . Ot h e r wis e (̈ Ia; Ib ) 6= ; fo r s o m e d is t in c t a; b 2 f 1 ; :::; sg. L e t L 2 (̈ Ia; Ib ) .
B y L e m m a 2 ( a 1 ) ,

jIaj + jIbj ¸ 2 p + 2 jLj + 4 ¸ 6 :

R e c a llin g a ls o t h a t s ¸ ± ¡ p + 1 = ± + 1 , we g e t

c =
sX

i=1

jIij ¸ jIaj + jIbj + 2 ( s ¡ 2 ) = 2 s + 2 ¸ 2 ± + 4 ;

c o n t r a d ic t in g ( 1 ) .

Case 1.1.2. p = 1 .

B y ( 2 ) , c ¸ 3 ±. W e c a n s u p p o s e t h a t ± · 3 , s in c e c ¸ 3 ± ¸ 2 ± + 4 wh e n ± ¸ 4 ,
c o n t r a d ic t in g ( 1 ) . On t h e o t h e r h a n d , b y t h e h yp o t h e s is , ± ¸ p + 2 = 3 , im p lyin g t h a t
± = 3 . B y t h e h yp o t h e s is , s ¸ ± ¡ p + 1 = 3 . N e xt , we c a n s u p p o s e t h a t s = 3 , s in c e
c ¸ s( p + 2 ) ¸ 1 2 = 2 ± + 6 wh e n s ¸ 4 , c o n t r a d ic t in g ( 1 ) . Fu r t h e r , if (̈ I1; I2; I3 ) = ;, t h e n
Gnf»1; »2; »3g h a s a t le a s t fo u r c o m p o n e n t s , c o n t r a d ic t in g ¿ ¸ 1 . Ot h e r wis e (̈ Ia; Ib ) 6= ; fo r
s o m e d is t in c t a; b 2 f1 ; 2 ; 3 g, s a y a = 1 a n d b = 2 . L e t L 2 (̈ I1; I2 ) . B y L e m m a 2 ( a 1 ) ,

jI1j + jI2j ¸ 2 p + 2 jLj + 4 = 8 ;

wh ic h yie ld s c ¸ jI1j + jI2j + jI3j ¸ 1 1 = 2 ± + 5 , c o n t r a d ic t in g ( 1 ) .

Case 1.2. s = ± ¡ p.
It fo llo ws t h a t x1x2 2 E. Th e n x1x2

á
P x+1 is a n o t h e r lo n g e s t p a t h in GnC. W e c a n

s u p p o s e t h a t NC ( x1 ) = NC ( x
+
1 ) , s in c e o t h e r wis e we c a n a r g u e a s in Ca s e 1 . B y t h e s a m e

r e a s o n ,

NC ( x1 ) = NC ( x
+
1 ) = NC ( x

+2
1 ) = ::: = NC ( x2 ) :

S in c e C is e xt r e m e , we h a ve jIij ¸ j»ix1
¡!
P x2»i+1j = p + 2 ( i = 1 ; :::; s) . If (̈ I1; :::; Is ) = ;,

t h e n Gnf»1; :::; »sg h a s a t le a s t s + 1 c o m p o n e n t s , c o n t r a d ic t in g ¿ ¸ 1 . Ot h e r wis e (̈ Ia; Ib ) 6=



Zh. Nikoghosyan 2 3

; fo r s o m e d is t in c t a; b 2 f 1 ; :::; sg. L e t L 2 (̈ Ia; Ib ) wit h L = z1
¡!
L z2, wh e r e z1 2 V ( I¤a )

a n d z2 2 V ( I¤b ) . B y L e m m a 2 ( a 1 ) , jIaj + jIbj ¸ 2 p + 6 . H e n c e

c =
sX

i=1

jIij ¸ jIaj + jIbj + ( s ¡ 2 ) ( p + 2 ) ¸ s( p + 2 ) + 2

= ( ± ¡ p) ( p + 2 ) + 2 = 2 ± + 2 + p ( ± ¡ p ¡ 2 ) : ( 3 )
Claim 1. ( a1 ) 2 p + 6 · jIaj + jIbj · 2 p + 7 a n d jIij · p + 5 ( i = 1 ; :::; s) .
( a 2 ) If jIaj + jIbj = 2 p + 7 , t h e n jIij = p + 2 fo r e a c h i 2 f 1 ; :::; sgnfa; bg.
( a 3 ) If jIaj + jIbj = 2 p + 6 , t h e n jIf j · p + 3 fo r s o m e f 2 f1 ; :::; sgnfa; bg a n d jIij = p + 2

fo r e a c h i 2 f 1 ; :::; sgnfa; b; fg.
( a 4 ) If jIfj = p + 5 fo r s o m e f 2 fa; bg, t h e n jIij = p + 2 fo r e a c h i 2 f1 ; :::; sgnffg.
( a 5 ) Fo r e a c h d is t in c t f; g; h 2 f 1 ; :::; sg, jIf j + jIgj + jIhj · 3 p + 9 .
( a 6 ) (̈ I1; :::; Is ) µ E.
P r oof. If jIf j ¸ p + 6 fo r s o m e f 2 f1 ; :::; sg, t h e n

c =
sX

i=1

jIij ¸ jIf j + ( s ¡ 1 ) ( p + 2 ) ¸ s( p + 2 ) + 4

= 2 ± + 4 + p ( ± ¡ p ¡ 2 ) ¸ 2 ± + 4 ;
c o n t r a d ic t in g ( 1 ) . N e xt , if jIaj + jIbj ¸ 2 p + 8 , t h e n

c ¸ jIaj + jIbj + ( s ¡ 2 ) ( p + 2 ) ¸ s( p + 2 ) + 4 ¸ 2 ± + 4 ;

a g a in c o n t r a d ic t in g ( 1 ) . H e n c e ( a1 ) h o ld s . S t a t e m e n t s ( a2 ) ¡ ( a 4 ) c a n b e p r o ve d b y a s im ila r
wa y. To p r o ve ( a 5 ) , a s s u m e t h e c o n t r a r y, t h a t is jIf j + jIgj + jIhj ¸ 3 p + 1 0 fo r s o m e d is t in c t
f; g; h 2 f1 ; :::; sg. Th e n

c =
sX

i=1

jIij ¸ jIf j + jIgj + jIhj + ( s ¡ 3 ) ( p + 2 )

¸ 3 ( p + 2 ) + 4 + ( s ¡ 3 ) ( p + 2 ) = 2 ± + 4 + p( s ¡ 2 ) ¸ 2 ± + 4 ;
c o n t r a d ic t in g ( 1 ) . S t a t e m e n t ( a6 ) fo llo ws fr o m L e m m a 2 ( a 1 ) a n d Cla im 1 ( a 1 ) . Cla im 1 is
p r o ve d .

Claim 2. p + 3 · d1 · p + 4 a n d p + 3 · d2 · p + 4 , wh e r e

d1 = j»a
¡!
C z1j + j»b

¡!
C z2j; d2 = jz1

¡!
C »a+1j + jz2

¡!
C »b+1j:

P r oof. P u t
Q = »ax1

¡!
P x2»b

á
C z1z2

¡!
C »a:

Cle a r ly, jQj = jCj¡d1+p+3 . S in c e C is e xt r e m e , we h a ve jCj ¸ jQj, im p lyin g t h a t d1 ¸ p+3 .
B y a s ym m e t r ic a r g u m e n t , d2 ¸ p + 3 . B y Cla im 1 ( a 1 ) , jIaj + jIbj = d1 + d2 · 2 p + 7 . If
d1 ¸ p + 5 , t h e n 2 p + 7 ¸ d1 + d2 ¸ p + 5 + d2, im p lyin g t h a t d2 · p + 2 , a c o n t r a d ic t io n .
H e n c e , d1 · p + 4 . B y a s ym m e t r ic a r g u m e n t , d2 · p + 4 . Cla im 2 is p r o ve d .

Claim 3. If v1 2 V ( »+a
¡!
C z¡1 ) a n d v2 2 V ( z+1

¡!
C »¡a+1 ) , t h e n v1v2 62 E.



2 4 A Sharp Improvement of a Theorem of Bauer and Schmeichel

P r oof. A s s u m e t h e c o n t r a r y, t h a t is v1v2 2 E. P u t

Q = »a
¡!
C v1v2

á
C z1z2

á
C »a+1x1

¡!
P x2»b+1

¡!
C »a;

j»a
¡!
C v1j = d1; jv1

¡!
C z1j = d2; jz1

¡!
C v2j = d3;

jv2
¡!
C »a+1j = d4; j»b

¡!
C z2j = d5; jz2

¡!
C »b+1j = d6:

Cle a r ly, jQj = jCj ¡ d2 ¡ d4 ¡ d6 + p + 4 . S in c e C is e xt r e m e , we h a ve jQj · jCj, im p lyin g
t h a t d2 + d4 + d6 ¸ p + 4 . B y a s ym m e t r ic a r g u m e n t , d1 + d3 + d5 ¸ p + 4 . B y s u m m in g , we
g e t

6X

i=1

di = jIaj + jIbj ¸ 2 p + 8 ;

c o n t r a d ic t in g Cla im 1 ( a 1 ) . Th u s , v1v2 62 E. Cla im 3 is p r o ve d .

Claim 4. L e t »f ; »g; »h o c c u r o n
¡!
C in a c o n s e c u t ive o r d e r fo r s o m e f; g; h 2 f 1 ; :::; sg

a n d w1w2 2 E fo r s o m e w1 2 V ( I¤f ) a n d w2 2 V ( I¤g ) . If N ( w3 ) \ f»f+1; »gg 6= ; fo r s o m e
w3 2 V ( I¤h ) , t h e n

jw1
¡!
C »f +1j + j»g

¡!
C w2j + j»h

¡!
C w3j ¸ p + 4 :

Fu r t h e r , if N ( w4 ) \ f»f +1; »gg 6= ; fo r s o m e w4 2 V ( I¤h¡1 ) , t h e n

jw1
¡!
C »f +1j + j»g

¡!
C w2j + jw4

¡!
C »hj ¸ p + 4 :

P r oof. A s s u m e ¯ r s t t h a t w3»f+1 2 E. P u t

Q = »f
¡!
C w1w2

¡!
C »hx1

¡!
P x2»g

á
C »f +1w3»f :

Cle a r ly,

jQj = jCj ¡ jw1
¡!
C »f +1j ¡ j»g

¡!
C w2j ¡ j»h

¡!
C w3j + p + 4 :

S in c e jQj · jCj, t h e d e s ir e d r e s u lt h o ld s im m e d ia t e ly. If w4»f +1 2 E, t h e n we c a n u s e t h e
fo llo win g c yc le

Q0 = »f
¡!
C w1w2

¡!
C w4»f +1

¡!
C »gx2

á
P x1»h

¡!
C »f

in s t e a d o f Q. B y a s ym m e t r ic a r g u m e n t , t h e d e s ir e d r e s u lt h o ld s wh e n e it h e r w3»g 2 E o r
w4»g 2 E. Cla im 4 is p r o ve d .

Claim 5. E ve r y t wo in t e r m e d ia t e in d e p e n d e n t e d g e s e1; e2 in (̈ I1; :::; Is ) h a ve a c r o s s in g
wit h e1; e2 2 (̈ If ; Ig; Ih ) fo r s o m e d is t in c t f; g; h 2 f 1 ; :::; sg.

P r oof. L e t e1 = w1w2 a n d e2 = w3w4. W e d is t in g u is h t h r e e d i®e r e n t c a s e s . Fir s t ,
if e1; e2 2 (̈ If ; Ig ) fo r s o m e d is t in c t f; g, t h e n b y L e m m a 2 ( a 3 ) , jIf j + jIgj ¸ 2 p + 8 ,
c o n t r a d ic t in g Cla im 1 ( a 1 ) . N e xt , if e1 2 (̈ If ; Ig ) a n d e2 2 (̈ Ih; Ir ) fo r s o m e d is t in c t
f; g; h; r, t h e n b y L e m m a 2 ( a 1 ) , jIfj + jIgj ¸ 2 p + 6 a n d jIhj + jIrj ¸ 2 p + 6 , im p lyin g t h a t

c ¸ jIf j + jIgj + jIhj + jIrj + ( s ¡ 4 ) ( p + 2 ) = 4 p + 1 2 + ( s ¡ 4 ) ( p + 2 )

= s( p + 2 ) + 4 = 2 ± + 4 + p( ± ¡ p ¡ 2 ) ¸ 2 ± + 4 ;
wh ic h a g a in c o n t r a d ic t s ( 1 ) . Fin a lly, le t e1 2 (̈ If ; Ig ) a n d e2 2 (̈ If ; Ih ) fo r s o m e d is t in c t
f; g; h. A s s u m e w.l.o .g . t h a t »f ; »g; »h o c c u r o n

¡!
C in a c o n s e c u t ive o r d e r a n d w1; w3 2 V ( I¤f ) ,



Zh. Nikoghosyan 2 5

w2 2 V ( I¤g ) , w4 2 V ( I¤h ) . W e c a n a s s u m e a ls o t h a t w3 a n d w1 o c c u r o n If in a c o n s e c u t ive
o r d e r , s in c e o t h e r wis e e1 a n d e2 h a ve a c r o s s in g a n d we a r e d o n e . P u t

Q = »f
¡!
C w3w4

á
C w2w1

¡!
C »gx2

á
P x1»h+1

¡!
C »f ;

j»f
¡!
C w3j = d1; jw3

¡!
C w1j = d2; jw1

¡!
C »f+1j = d3;

j»g
¡!
C w2j = d4; jw2

¡!
C »g+1j = d5; j»h

¡!
C w4j = d6; jw4

¡!
C »h+1j = d7:

Cle a r ly, jQj = jCj¡d2 ¡d4 ¡d7 +p + 4 . S in c e C is e xt r e m e , we h a ve jQj · jCj, im p lyin g t h a t
d2 + d4 + d7 ¸ p + 4 . On t h e o t h e r h a n d , b y L e m m a 2 , d3 + d5 ¸ p + 3 a n d d1 + d6 ¸ p + 3 .
B y s u m m in g , we g e t

P7
i=1 di = jIf j + jIgj + jIhj ¸ 3 p + 1 0 . Th e n

jCj ¸ jIf j + jIgj + jIhj + ( s ¡ 3 ) ( p + 2 ) = s( p + 2 ) + 4 ¸ 2 ± + 4 ;

c o n t r a d ic t in g ( 1 ) . Cla im 5 is p r o ve d .

Claim 6. If ¹( )̈ = 1 , t h e n s · 3 a n d e it h e r »+a »¡b+1 2 E wit h »a = »b+1 o r »¡a+1»+b 2 E
wit h »a+1 = »b. If ¹ ( )̈ = 1 a n d s = 3 , t h e n jI1j = jI2j = jI3j = p + 3 .

P r oof. S in c e ¹( )̈ = 1 , e it h e r o n e o f t h e ve r t ic e s z1; z2, s a y z1, is a c o m m o n ve r t e x fo r a ll
e d g e s in (̈ I1; :::; Is ) o r z1z3; z2z3 2 (̈ I1; :::; Is ) fo r s o m e z3 2 V ( I¤f ) a n d f 2 f 1 ; :::; sgnfa; bg.

Case a1. z1 is a c o m m o n ve r t e x fo r a ll e d g e s in (̈ I1; :::; Is ) .
If z1 62 f»+a ; »¡a+1g, t h e n b y Cla im 3 , Gnf»1; :::; »s; z1g h a s a t le a s t s + 2 c o m p o n e n t s ,

c o n t r a d ic t in g ¿ ¸ 1 . L e t z1 2 f»+a ; »¡a+1g, s a y z1 = »+a .

Case a1.1. z1»
¡
b+1 62 E.

It fo llo ws t h a t z2 6= »¡b+1. B y Cla im 2 , j»b
¡!
C z2j ¸ p + 2 .

Case a1.1.1. z1»
¡2
b+1 62 E.

It fo llo ws t h a t jIbj ¸ p + 5 . B y Cla im 1 ( a 1 ) , jIaj = p + 2 . Mo r e o ve r , we h a ve jIbj = p + 5 ,
j»b

¡!
C z2j = p + 2 , z2 = »¡3b+1 a n d N ( z1 ) \ V ( I¤b ) = fz2g. B y Cla im 1 ( a 4 ) , jIij = p + 2 fo r

e a c h i 2 f 1 ; :::; sgnfbg. N e xt , b y L e m m a 2 ( a 1 ) , (̈ Ia; Ii ) = ; fo r e a c h i 2 f 1 ; :::; sgnfa; bg.
Th u s , if z1y 2 (̈ I1; :::; Is ) , t h e n y = z2, im p lyin g t h a t (̈ I1; :::; Is ) = fz1z2g. B e s id e s , s in c e
j»b

¡!
C z2j = p + 2 ¸ 2 , we h a ve z2 62 f»+b ; »¡b+1g. Th e r e fo r e , b y Cla im 3 , Gnf»1; :::; »s; z2g h a s

a t le a s t s + 2 c o m p o n e n t s , c o n t r a d ic t in g ¿ ¸ 1 .

Case a1.1.2. z1»
¡2
b+1 2 E.

It fo llo ws t h a t jIbj ¸ p + 4 . A s s u m e ¯ r s t t h a t jIbj = p + 5 . If z1»¡3b+1 62 E, t h e n c le a r ly
z2 = »

¡2
b+1 a n d we c a n a r g u e a s in Ca s e a 1 .1 .1 . Ot h e r wis e t h e fo llo win g c yc le

»ax1
¡!
P x2»a+1

¡!
C »¡3b+1z1»

¡2
b+1

¡!
C »a

is lo n g e r t h a n C, a c o n t r a d ic t io n .

N o w a s s u m e t h a t jIbj = p + 4 , t h a t is j»b
¡!
C »¡2b+1j = p + 2 . If z1y 2 E fo r s o m e

y 2 V ( »b
¡!
C »¡3b+1 ) , t h e n b y Cla im 2 , j»b

¡!
C yj ¸ p+2 , im p lyin g t h a t jIbj ¸ p+5 , a c o n t r a d ic t io n .

H e n c e , if z1y 2 (̈ Ia; Ib ) , t h e n c le a r ly y = »¡2b+1. In p a r t ic u la r , we h a ve z2 = »¡2b+1. Fu r t h e r ,
if z1y 2 (̈ Ia; If ) fo r s o m e f 2 f 1 ; :::; sgnfbg, t h e n b y L e m m a 2 ( a 1 ) , jIaj + jIfj ¸ 2 p + 6 ,



2 6 A Sharp Improvement of a Theorem of Bauer and Schmeichel

t h a t is jIaj + jIbj + jIf j ¸ 3 p + 1 0 , c o n t r a d ic t in g Cla im 1 ( a 5 ) . Th u s , z2 is a c o m m o n ve r t e x
fo r a ll e d g e s in (̈ I1; :::; Is ) . B y Cla im 3 , Gnf»1; :::; »s; z2g h a s a t le a s t s + 2 c o m p o n e n t s ,
c o n t r a d ic t in g ¿ ¸ 1 .

Case a1.2. »+a »
¡
b+1 2 E.

B y Cla im 2 , j»+a
¡!
C »a+1j ¸ p + 2 a n d j»b

¡!
C »¡b+1j ¸ p + 2 . If j»+a

¡!
C »a+1j ¸ p + 3 a n d

j»b
¡!
C »¡b+1j ¸ p + 3 , t h e n jIaj + jIbj ¸ 2 p + 8 , c o n t r a d ic t in g Cla im 1 ( a 1 ) . H e n c e , we c a n

a s s u m e w.l.o .g . t h a t j»b
¡!
C »¡b+1j = p + 2 , t h a t is jIbj = p + 3 a n d jIaj ¸ p + 3 . Fu r t h e r , we

h a ve »+b »a; »
+
b »b+1 62 E ( b y Cla im 4 ) a n d »+b »+a 62 E ( b y Cla im 2 ) .

Case a1.2.1. N ( »+b ) 6µ V ( C ) .
L e t Q = »+b

¡!
Q v b e a lo n g e s t p a t h in G wit h V ( Q ) \V ( C ) = f»+b g. S in c e C is e xt r e m e , we

h a ve V ( Q ) \V ( P ) = ;. N e xt , s in c e P is a lo n g e s t p a t h in GnC, we h a ve jQj · p+1 . Fu r t h e r ,
r e c a llin g t h a t »+b »a; »

+
b »b+1; »

+
b »

+
a 62 E ( s e e Ca s e a 1 .2 ) , we c o n c lu d e t h a t v»a; v»b+1; v»+a 62 E,

a s we ll. If vy 62 E fo r e a c h y 2 ( »+2b
¡!
C »¡b+1 ) , t h e n c le a r ly

N ( v ) µ ( V ( Q ) [ f»1; :::; »sg ) nf»a; »b+1»+a g;

t h a t is d( v ) · jQj + s ¡ 2 · p + s ¡ 1 = ± ¡ 1 , a c o n t r a d ic t io n . N o w le t vy 2 E fo r s o m e
y 2 V ( »+2b

¡!
C »¡b+1 ) . A s s u m e t h a t y is c h o s e n s o a s t o m in im iz e j»+b

¡!
C yj. S in c e C is e xt r e m e ,

we h a ve j»+b
¡!
C yj ¸ jQj + 1 . Fu r t h e r , s in c e

jN ( v ) \ V ( y¡!C »¡b+1 ) j ¸ ± ¡ ( s ¡ 2 ) ¡ jQj;

we h a ve
j»+b

¡!
C »¡b+1j ¸ jQj + 1 + 2 ( ± ¡ s + 1 ¡ jQj )

= 2 ± ¡ jQj ¡ 2 s + 3 ¸ 2 ± ¡ p ¡ 2 s + 2 = p + 2 :
B u t t h e n jIbj ¸ p + 4 , a c o n t r a d ic t io n .

Case a1.2.2. N ( »+b ) µ V ( C ) .
S in c e ¹ ( )̈ = 1 a n d »+b »

+
a 62 E, we h a ve

N ( »+b ) µ V ( »+2b
¡!
C »¡b+1 ) [ f»1; :::; »sgnf»a; »b+1g:

If »a 6= »b+1, t h e n d( »+b ) · p + s ¡ 1 = ± ¡ 1 , a c o n t r a d ic t io n . H e n c e »a = »b+1.

Case a1.2.2.1. jIfj = p + 2 fo r s o m e f 2 f 1 ; :::; sgnfa; bg.
If N ( »+f ) µ V ( C ) , t h e n a s in d ic a t e d a b o ve ,

d( »+f ) · s ¡ 1 + j»+f
¡!
C »¡f+1j = p + s ¡ 1 = ± ¡ 1 ;

a c o n t r a d ic t io n . If N ( »+f ) 6µ V ( C ) , t h e n we c a n a r g u e a s in Ca s e a 1 .2 .1 .

Case a1.2.2.2. jIij ¸ p + 3 fo r e a c h i 2 f 1 ; :::; sgnfa; bg.
If s ¸ 4 , t h e n

jCj =
sX

i=1

jIij ¸ s( p + 3 ) = ( ± ¡ p ) ( p + 3 )



Zh. Nikoghosyan 2 7

= 2 ± + 2 p + 4 + ( ± ¡ p ¡ 4 ) ( p + 1 ) ¸ 2 ± + 4 ;
c o n t r a d ic t in g ( 1 ) . H e n c e , s · 3 . Mo r e o ve r , if s = 3 , t h e n b y Cla im 1 ( a 5 ) , jI1j = jI2j = jI3j =
p + 3 .

Case a2. z1z3; z2z3 2 (̈ I1; :::; Is ) , wh e r e z3 2 V ( I¤f ) a n d f 2 f 1 ; :::; sgnfa; bg.
A s s u m e w.l.o .g . t h a t »a; »b; »f o c c u r o n

¡!
C in a c o n s e c u t ive o r d e r . P u t

j»a
¡!
C z1j = d1; jz1

¡!
C »a+1j = d2; j»b

¡!
C z2j = d3;

jz2
¡!
C »b+1j = d4; j»f

¡!
C z3j = d5; jz3

¡!
C »f +1j = d6:

B y Cla im 2 ,

d1 + d3 ¸ p + 3 ; d1 + d5 ¸ p + 3 ; d2 + d4 ¸ p + 3 ;
d2 + d6 ¸ p + 3 ; d3 + d5 ¸ p + 3 ; d4 + d6 ¸ p + 3 :

S u m m in g u p , we g e t

2
6X

i=1

di = 2 ( jIaj + jIbj + jIfj ) ¸ 6 ( p + 3 ) :

On t h e o t h e r h a n d , b y Cla im 1 ( a 5 ) , jIaj + jIbj + jIf j · 3 ( p + 3 ) , im p lyin g t h a t d1 = d2 =
::: = d6 = ( p + 3 ) = 2 a n d p is o d d . H e n c e di ¸ 2 a n d u s in g Cla im 3 , we c a n s t a t e t h a t
Gnf»1; :::; »s; z1; z2g h a s a t le a s t s + 3 c o m p o n e n t s , c o n t r a d ic t in g ¿ ¸ 1 . Cla im 6 is p r o ve d .

Claim 7. E it h e r ¹ ( )̈ = 1 o r ¹ ( )̈ = 3 .
P r oof. Th e p r o o f is b y c o n t r a d ic t io n . If ¹( )̈ = 0 , t h e n Gnf»1; :::; »sg h a s a t le a s t s + 1

c o m p o n e n t s , c o n t r a d ic t in g ¿ ¸ 1 . L e t ¹( )̈ ¸ 1 .

Case a1. ¹ = 2 .
B y Cla im 5 , (̈ I1; :::; Is ) c o n s is t s o f t wo c r o s s in g in t e r m e d ia t e in d e p e n d e n t e d g e s w1w2 2

(̈ If ; Ig ) a n d w3w4 2 (̈ If ; Ih ) fo r s o m e d is t in c t f; g; h. A s s u m e t h a t b o t h »f ; »g ; »h a n d
w1; w3; w2; w4 o c c u r o n

¡!
C in a c o n s e c u t ive o r d e r . P u t

Q = »f
¡!
C w1w2

¡!
C w4w3

¡!
C »gx2

á
P x1»h+1

¡!
C »f ;

j»f
¡!
C w1j = d1; jw1

¡!
C w3j = d2; jw3

¡!
C »f+1j = d3;

j»g
¡!
C w2j = d4; jw2

¡!
C »g+1j = d5; j»h

¡!
C w4j = d6; jw4

¡!
C »h+1j = d7:

Cle a r ly, jQj = jCj ¡ d2 ¡ d4 ¡ d7 + p + 4 . S in c e jQj · jCj, we h a ve d2 + d4 + d7 ¸ p + 4 . If
d3 + d6 ¸ p + 3 a n d d1 + d5 ¸ p + 3 , t h e n

P7
i=1 di = jIf j + jIgj + jIhj ¸ 3 p + 1 0 , c o n t r a d ic t in g

Cla im 1 ( a 5 ) . Ot h e r wis e , e it h e r d3 + d6 · p + 2 o r d1 + d5 · p + 2 , s a y d3 + d6 · p + 2 .
Fu r t h e r , if e it h e r d7 = 1 o r »

¡
h+1w3 2 E, t h e n b y Cla im 2 , d3 ¸ p + 2 , t h a t is d3 + d6 ¸ p + 3 ,

a c o n t r a d ic t io n . H e n c e , d7 ¸ 2 a n d »¡h+1w3 62 E. B y Cla im 4 , »¡h+1»f +1; »¡h+1»h 62 E. If
jIhj ¸ p + 4 , t h e n t a kin g in t o a c c o u n t t h a t jIfj + jIgj ¸ 2 p + 6 ( b y Cla im 1 ( a 1 ) ) , we g e t
jIf j + jIgj + jIhj ¸ 3 p + 1 0 , c o n t r a d ic t in g Cla im 1 ( a 5 ) . H e n c e , jIhj · p + 3 . B y a s ym m e t r ic
a r g u m e n t , jIgj · p + 3 .

Case a1.1. N ( »¡h+1 ) µ V ( C ) .



2 8 A Sharp Improvement of a Theorem of Bauer and Schmeichel

If »¡h+1w2 62 E, t h e n r e c a llin g t h a t ¹( )̈ = 2 , we g e t

N ( »¡h+1 ) µ V ( w4
¡!
C »¡2h+1 ) [ f»1; :::; »sgnf»f+1; »hg;

im p lyin g t h a t jN ( »¡h+1 ) j · p + s ¡ 1 = ± ¡ 1 , a c o n t r a d ic t io n . N o w le t »¡h+1w2 2 E. B y Cla im
1 ( a 1 a n d a 5 ) , jIf j = jIgj = jIhj = p + 3 . Mo r e o ve r , b y Cla im 2 , d5 = p + 2 a n d d4 = 1 . Th e n ,
fo r t h e s a m e r e a s o n , d1 = p + 2 , im p lyin g t h a t jIaj ¸ p + 4 , a c o n t r a d ic t io n .

Case a1.2. N ( »¡h+1 ) 6µ V ( C ) .
W e c a n a r g u e a s in t h e p r o o f o f Cla im 6 ( Ca s e a 1 .2 .1 ) .

Case a2. ¹( )̈ ¸ 4 .
B y Cla im 5 , t h e r e a r e a t le a s t fo u r p a ir wis e c r o s s in g in t e r m e d ia t e in d e p e n d e n t e d g e s in

(̈ I1; :::; Is ) , wh ic h is im p o s s ib le . Cla im 7 is p r o ve d .

Claim 8. If ¹ ( )̈ = 1 , t h e n e it h e r n ´ 1 ( mod 3 ) wit h c ¸ 2 ± + 2 o r n ´ 1 ( mod 4 ) wit h
c ¸ 2 ± + 3 o r n ´ 2 ( mod 3 ) wit h c ¸ 2 ± + 3 .

P r oof. B y Cla im 6 , s · 3 a n d e it h e r »+a »¡b+1 2 E o r »¡a+1»+b 2 E, s a y »¡a+1»+b 2 E.

Case a1. s = 2 .
It fo llo ws t h a t ± = p + s = p + 2 . L e t a = 1 a n d b = 2 . B y Cla im 2 , j»1

¡!
C »¡2 j ¸ p + 2

a n d j»+2
¡!
C »1j ¸ p + 2 , im p lyin g t h a t jIij ¸ p + 3 ( i = 1 ; 2 ) .

Case a1.1. jI1j = p + 4 a n d jI2j = p + 3 .
If V ( G ) = V ( C [ P ) , t h e n n = 3 p + 8 = 3 ± + 2 ´ 2 ( mod 3 ) wit h c = 2 p + 7 = 2 ± + 3 , a n d

we a r e d o n e . Ot h e r wis e N ( v1 ) 6µ V ( C [P ) fo r s o m e v1 2 V ( C [P ) . Ob s e r vin g t h a t x1x2 2 E
a n d r e c a llin g t h a t P is a lo n g e s t p a t h in V ( GnC ) , we c o n c lu d e t h a t v1 62 V ( P ) . Ch o o s e a
lo n g e s t p a t h Q = v1

¡!
Q v2 wit h V ( Q ) \ V ( C ) = fv1g. Cle a r ly, 1 · jQj · p + 1 = ± ¡ 1 a n d

N ( v2 ) µ V ( C [ Q) .

Case a1.1.1. v1 2 V ( »+22
¡!
C »¡1 ) .

B y Cla im 1 ( a 6 ) , N ( v2 ) \ V ( I¤1 ) = ;, t h a t is N ( v2 ) µ V ( I1 ) [ V ( Q ) . A s s u m e t h a t
v1 is c h o s e n s o a s t o m in im iz e jv1

¡!
C »1j, im p lyin g t h a t N ( v2 ) \ V ( v1

¡!
C »¡1 ) = ;. Cle a r ly,

jv1
¡!
C »1j · p + 1 . Th e n b y Cla im 4 , v1»2 62 E a n d t h e r e fo r e , v2»2 62 E, a s we ll.

Case a1.1.1.1. v2»1 2 E.
It fo llo ws t h a t N ( v2 ) µ V ( Q ) [ V ( »+2

¡!
C v¡1 ) [ f»1g. S in c e C is e xt r e m e a n d v2»1 2 E, we

h a ve jv1
¡!
C »1j ¸ jQj+1 . If N ( v2 ) µ V ( Q ) [f»1g, t h e n c le a r ly jQj ¸ ±¡ 1 = p+1 a n d t h e r e fo r e ,

jv1
¡!
C »1j ¸ p + 2 . B u t t h e n jI2j ¸ p + 4 , a c o n t r a d ic t io n . H e n c e , N ( v2 ) 6µ V ( Q) [ f»1g, t h a t

is v2y 2 E fo r s o m e y 2 V ( »+2
¡!
C v¡1 ) . A s s u m e t h a t y is c h o s e n s o a s t o m in im iz e jy

¡!
C v1j.

Ob s e r vin g t h a t jy¡!C v1j ¸ jQj + 1 a n d ± = j»+2
¡!
C »1j ¸ 4 , we g e t

j»+2
¡!
C »1j ¸ 2 ( jQj + 1 ) + 2 ( ± ¡ jQj ¡ 2 ) = 2 ± ¡ 2 ¸ ± + 2 = p + 4 ;

a c o n t r a d ic t io n .

Case a1.1.1.2. v2»1 62 E.



Zh. Nikoghosyan 2 9

It fo llo ws t h a t N ( v2 ) µ V ( Q) [ V ( »+2
¡!
C v¡1 ) . If N ( v2 ) µ V ( Q ) , t h e n jQj ¸ ± = p + 2 , a

c o n t r a d ic t io n . Ot h e r wis e v2y 2 E fo r s o m e y 2 V ( »+2
¡!
C v¡1 ) . A s s u m e t h a t y is c h o s e n s o a s

t o m in im iz e jy¡!C v1j. S in c e jy
¡!
C v1j ¸ jQj + 1 , we h a ve

j»+2
¡!
C v1j ¸ jQj + 1 + 2 ( ± ¡ jQj ¡ 1 ) = 2 ± ¡ jQj ¡ 1 ¸ ± = p + 2 :

B u t t h e n jIbj ¸ 4 , a c o n t r a d ic t io n .

Case a1.1.2. v1 2 V ( »+1
¡!
C »¡32 ) .

B y Cla im 1 ( a 6 ) , N ( v2 ) \ V ( I¤2 ) = ;, t h a t is N ( v2 ) µ V ( Q ) [ V ( I1 ) . A s s u m e t h a t
v1 is c h o s e n s o a s t o m in im iz e j»1

¡!
C v1j, im p lyin g t h a t N ( v2 ) \ V ( »+1

¡!
C v¡1 ) = ;. Cle a r ly,

j»1
¡!
C v1j · p + 1 . Th e n b y Cla im 4 , v1»2 62 E a n d t h e r e fo r e , v2»2 62 E.

Case a1.1.2.1. »+2 »
¡2
2 2 E.

B y Cla im 3 , v1»
¡
2 62 E, im p lyin g t h a t v2»¡2 62 E.

Case a1.1.2.1.1. v2»1 2 E.
It fo llo ws t h a t N ( v2 ) µ V ( Q ) [ V ( v1

¡!
C »¡22 ) [ f»1g. S in c e C is e xt r e m e a n d v2»1 2 E, we

h a ve j»1
¡!
C v1j ¸ jQj + 1 . If N ( v2 ) µ V ( Q) [ f»1g, t h e n jQj ¸ ± ¡ 1 = p + 1 a n d t h e r e fo r e ,

j»1
¡!
C v1j ¸ p + 2 . B u t t h e n jI1j ¸ p + 5 , a c o n t r a d ic t io n . H e n c e , N ( v2 ) 6µ V ( Q) [ f»1g, t h a t

is v2y 2 E fo r s o m e y 2 V ( v+1
¡!
C »¡22 ) . A s s u m e t h a t y is c h o s e n s o a s t o m in im iz e jv1

¡!
C yj.

Ob s e r vin g t h a t jv1
¡!
C yj ¸ jQj + 1 a n d ± = j»1

¡!
C »¡22 j ¸ 4 , we g e t

j»1
¡!
C »¡22 j ¸ 2 ( jQj + 1 ) + 2 ( ± ¡ jQj ¡ 2 ) = 2 ± ¡ 2 ¸ ± + 2 = p + 4 ;

a c o n t r a d ic t io n .

Case a1.1.2.1.2. v2»1 62 E.
It fo llo ws t h a t N ( v2 ) µ V ( Q) [ V ( v1

¡!
C »¡22 ) . If N ( v2 ) µ V ( Q ) , t h e n jQj ¸ ± = p + 2 ,

a c o n t r a d ic t io n . Ot h e r wis e v2y 2 E fo r s o m e y 2 V ( v+1
¡!
C »¡22 ) . B y c h o o s in g y s o a s t o

m in im iz e jv1
¡!
C yj, we g e t

jv1
¡!
C »¡22 j ¸ jQj + 1 + 2 ( ± ¡ jQj ¡ 1 ) = 2 ± ¡ jQj ¡ 1 ¸ ± = p + 2 :

Th is yie ld s jIaj ¸ p + 5 , a c o n t r a d ic t io n .

Case a1.1.2.2. »+2 »
¡2
2 62 E.

If v2»1 2 E, t h e n a s in Ca s e a 1 .1 .2 .1 .1 , j»1
¡!
C »¡2 j ¸ p +4 , c o n t r a d ic t in g t h e fa c t t h a t jI1j =

p + 4 . Ot h e r wis e , a s in Ca s e a 1 .1 .2 .1 .2 , jv1
¡!
C »¡2 j ¸ p + 2 . S in c e jI1j = p + 4 , we h a ve v1 = »+1 ,

jQj = ± ¡ 1 = p + 1 a n d v3 = »¡2 . Mo r e o ve r , we h a ve N ( v2 ) = ( V ( Q ) [ f»¡2 g ) nfv2g. Fu r t h e r ,
le t v b e a n a r b it r a r y ve r t e x in V ( Q ) nfv1g. P u t Q0 = v1

¡!
Q v¡v2

á
Q v. S in c e Q0 is a n o t h e r

lo n g e s t p a t h wit h V ( Q0 ) \ V ( C ) = fv1g, we c a n s u p p o s e t h a t N ( v ) = ( V ( Q ) [ f»¡2 g ) nfvg
fo r e a c h v 2 V ( Q) nfv1g. Fu r t h e r m o r e , if »1y 2 E fo r s o m e y 2 V ( »+21

¡!
C »¡22 ) , t h e n

»1x1
¡!
P x2»2»

+
2 »

¡
2 v2

á
Q v1

¡!
C y»1



3 0 A Sharp Improvement of a Theorem of Bauer and Schmeichel

is lo n g e r t h a n C, a c o n t r a d ic t io n . H e n c e , »1y 62 E fo r e a c h y 2 V ( »+21
¡!
C »¡22 ) . A n a lo g o u s ly,

if y»2 2 E fo r s o m e y 2 V ( »+1
¡!
C »¡22 ) , t h e n

»1x1
¡!
P x2»2y

á
C »+1

¡!
Q v2»

¡
2 »

+
2

¡!
C »1

is lo n g e r t h a n C, a c o n t r a d ic t io n . H e n c e , y»2 62 E fo r e a c h y 2 V ( »+1
¡!
C »¡22 ) . B u t t h e n

Gnf»+1 ; »¡2 g h a s a t le a s t t h r e e c o m p o n e n t s , c o n t r a d ic t in g ¿ ¸ 1 .

Case a1.1.3. v1 = »
¡2
2 .

B y Cla im 1 ( a 6 ) , N ( v2 ) µ V ( I1 ) . If v2y 2 E fo r s o m e y 2 V ( »+1
¡!
C v¡1 ) , t h e n we c a n a r g u e

a s in Ca s e a 1 .1 .2 . H e n c e , N ( v2 ) µ V ( Q ) [ f»1; »2g. If v2»2 2 E, t h e n

»1x1
¡!
P x2»2v2

á
Q v1»

¡
2 »

+
2

¡!
C »1

is lo n g e r t h a n C, a c o n t r a d ic t io n . Th e n c le a r ly, v2»1 2 E a n d N ( v2 ) µ V ( Q) [ f»1g.
Fu r t h e r m o r e , we h a ve jQj ¸ ± ¡ 1 , im p lyin g t h a t j»1

¡!
C v1j ¸ jQj + 1 ¸ ±. S in c e j»1

¡!
C v1j = ±,

we h a ve jQj = ± ¡ 1 = p + 1 a n d N ( v2 ) = ( V ( Q ) [ f»1g) nfv2g. Mo r e o ve r , a s in Ca s e 1 .1 .2 .2 ,
we h a ve N ( v ) = ( V ( Q) [ f»1g ) nfvg fo r e a c h v 2 V ( Q ) nfv1g. N o w c o n s id e r a n a r b it r a r y
ve r t e x y 2 V ( »+1

¡!
C »¡32 ) . Cle a r ly, j»1

¡!
C yj · p + 1 . B y Cla im 2 , y»+2 62 E. N e xt , b y Cla im 4 ,

y»2 62 E. Fu r t h e r , if y»¡2 2 E, t h e n

»1x1
¡!
P »2»2»

+
2 »

¡
2 y

¡!
C »¡22

¡!
Q v2»1

is lo n g e r t h a n C, a c o n t r a d ic t io n . Fin a lly, s in c e ¹ ( )̈ = 1 , we h a ve yv 62 E fo r e a c h
v 2 V ( »+22

¡!
C »¡1 ) . B u t t h e n Gnf»1; »¡22 g h a s a t le a s t t h r e e c o m p o n e n t s , c o n t r a d ic t in g ¿ ¸ 1 .

Case a1.1.4. v1 = »1.

If v2v3 2 E fo r s o m e v3 2 V ( »+22
¡!
C »¡1 ) [ V ( »+1

¡!
C »¡22 ) , t h e n we c a n a r g u e a s in Ca s e s

a 1 .1 .1 -a 1 .1 .3 . Ot h e r wis e v2v3 2 E fo r s o m e v3 2 f»¡2 ; »+2 ; »2g. If v3 2 f»2; »+2 g, t h e n we c a n
s h o w, a s in Ca s e a 1 .1 .3 , t h a t Gnf»1; v3g h a s a t le a s t t h r e e c o m p o n e n t s , c o n t r a d ic t in g ¿ ¸ 1 .
N o w le t v3 = »

¡
2 . Co n s id e r a n a r b it r a r y ve r t e x v 2 V ( Q) nfv1g. S in c e C is e xt r e m e , we

h a ve N ( v ) \ f»2; »+2 g = ;. N e xt , if vy 2 E fo r s o m e y 2 V ( C ) nf»1; »2; »¡2 ; »+2 g, t h e n we c a n
a r g u e a s in Ca s e s a 1 .1 .1 -a 1 .1 .3 . Th u s , we c a n a s s u m e t h a t N ( v ) µ V ( Q) [ f»¡2 g, im p lyin g
t h a t jQj ¸ ± ¡ 1 = p + 1 . L e t w 2 V ( »+1

¡!
C »¡32 ) . S in c e j»1

¡!
C wj · p + 1 , we h a ve w»+2 62 E

( b y Cla im 2 ) a n d w»2 62 E ( b y Cla im 4 ) . R e c a llin g a ls o t h a t ¹( )̈ = 1 , we c o n c lu d e t h a t
N ( v ) µ V ( »1

¡!
C »¡2 ) . If »

¡2
2 »2; »

¡2
2 »

+
2 62 E, t h e n c le a r ly Gnf»1; »¡2 g h a s a t le a s t t h r e e c o m p o -

n e n t s , c o n t r a d ic t in g ¿ ¸ 1 . H e n c e , e it h e r »¡22 »2 2 E o r »¡22 »+2 2 E.

Case a1.1.4.1. »¡22 »2 2 E.
If »¡22 »

+
2 62 E, t h e n Gnf»1; »2; »¡2 g h a s a t le a s t fo u r c o m p o n e n t s , c o n t r a d ic t in g ¿ ¸ 1 .

H e n c e , »¡22 »
+
2 2 E, t h a t is h»2; »¡2 ; »¡22 ; »+2 i is a c o m p le t e g r a p h . If V ( G) = V ( C [ P [ Q) ,

t h e n n = 4 ± + 1 ´ 1 ( mod 4 ) wit h c = 2 ± + 3 , a n d we a r e d o n e . Ot h e r wis e , a s in p r e vio u s
c a s e s , we c a n s h o w t h a t ¿ < 1 , a c o n t r a d ic t io n .

Case a1.1.4.2. »¡22 »
+
2 2 E.

If »¡22 »2 62 E, t h e n Gnf»1; »¡2 ; »+2 g h a s a t le a s t fo u r c o m p o n e n t s , c o n t r a d ic t in g ¿ ¸ 1 .
Ot h e r wis e h»2; »¡2 ; »¡22 ; »+2 i is a c o m p le t e g r a p h a n d we c a n a r g u e a s in Ca s e a 1 .1 .4 .1 .



Zh. Nikoghosyan 3 1

Case a1.1.5. v1 2 f»2; »¡2 ; »+2 g.
S in c e C is e xt r e m e , we h a ve v2 62 f»2; »¡2 ; »+2 g a n d t h e r e fo r e , we c a n a r g u e a s in Ca s e s

a 1 .1 .1 -1 .1 .4 .

Case a1.2. jI1j = jI2j = p + 3 .
W e c a n s h o w t h a t n = 3 ± + 1 ´ 1 ( mod 3 ) wit h c = 2 ± + 2 , b y a r g u in g a s in Ca s e a 1 .1 .

Case a2. s = 3 .
B y Cla im 6 , jI1j = jI2j = jI3j = p + 3 = ± a n d »¡2 »+2 2 E. If ± ¸ 4 , t h e n c = 3 ± ¸ 2 ± + 4 ,

c o n t r a d ic t in g ( 1 ) . H e n c e ± = 3 a n d t h e r e fo r e , p = 0 . P u t

C = »1w1w2»2w3w4»3w5w6»1;

wh e r e w2w3 2 E. U s in g Cla im s 2 -5 , we c a n s h o w t h a t

NC ( w1 ) = fw2; »1; »3g; NC ( w6 ) = fw5; »1; »3g:

A n a lo g o u s r e la t io n s h o ld fo r w4; w5. If V ( GnC ) = fx1g, t h e n n = 1 0 ´ 1 ( mod 3 ) wit h
c = 9 = 2 ± + 3 > 2 ± + 2 , a n d we a r e d o n e . Ot h e r wis e N ( y ) = fv1; v2; v3g fo r s o m e
y 2 V ( GnC ) nfx1g wit h N ( y ) µ V ( C ) . S in c e C is e xt r e m e , it is n o t h a r d t o s e e t h a t e it h e r
N ( y ) = fw2; »1; »3g o r N ( y ) = fw3; »1; »3g o r N ( y ) = f»1; »2; »3g. B u t t h e n GnN ( y ) h a s a t
le a s t fo u r c o m p o n e n t s , c o n t r a d ic t in g ¿ ¸ 1 . Cla im 8 is p r o ve d .

Claim 9. If ¹ = 3 , t h e n G is t h e P e t e r s e n g r a p h , t h a t is n = 1 0 ´ 1 ( mod 3 ) wit h
c ¸ 2 ± + 2 .

P r oof. B y Cla im 5 , (̈ I1; :::; Is ) c o n t a in s t h r e e p a ir wis e c r o s s in g in t e r m e d ia t e in d e p e n -
d e n t e d g e s e1; e2; e3. L e t e1 = w1w2, e2 = w3w4 a n d e3 = w5w6. If w1; w3; w5 2 V ( I¤f )
fo r s o m e f 2 f 1 ; :::; sg, t h e n we c a n a r g u e a s in p r o o f o f Cla im 7 . Ot h e r wis e we c a n a s -
s u m e w.l.o .g . t h a t w1; w3 2 V ( I¤f ) , w2; w5 2 V ( I¤g ) a n d w4; w6 2 V ( I¤h ) fo r s o m e d is t in c t
f; g; h 2 f 1 ; :::; sg, wh e r e b o t h »f ; »g; »h a n d w1; w3; w5; w2; w4; w6 o c c u r o n

¡!
C in a c o n s e c -

u t ive o r d e r . B y Cla im 1 ( a 1 a n d a 5 ) , jIf j = jIgj = jIhj = p + 3 a n d jIij = p + 2 fo r e a c h
i 2 f1 ; :::; sgnff; g; hg. P u t

j»f
¡!
C w1j = d1; jw1

¡!
C w3j = d2; jw3

¡!
C »f+1j = d3;

j»g
¡!
C w5j = d4; jw5

¡!
C w2j = d5; jw2

¡!
C »g+1j = d6;

j»h
¡!
C w4j = d7; jw4

¡!
C w6j = d8; jw6

¡!
C »h+1j = d9:

If d3 + d7 ¸ p + 3 , d1 + d6 ¸ p + 3 a n d d4 + d9 ¸ p + 3 , t h e n c le a r ly jIfj + jIgj + jIhj ¸ 3 p + 1 2 ,
a c o n t r a d ic t io n . Ot h e r wis e we c a n a s s u m e w.l.o .g . t h a t d3 + d7 · p + 2 . Fu r t h e r , if e it h e r
d1 ¸ 2 o r d9 ¸ 2 , t h e n we c a n a r g u e a s in t h e p r o o f o f Cla im 7 ( Ca s e a 1 .1 ) . H e n c e , we c a n
a s s u m e t h a t d1 = d9 = 1 . B y Cla im 2 , d4 = d6 = 1 . Fo r t h e s a m e r e a s o n , u s in g t h e fa c t t h a t
d1 = d6 = 1 , we g e t d3 = d7 = 1 .

Case a1. E it h e r »h+1 6= »f o r »f +1 6= »g o r »g+1 6= »h.
A s s u m e w.l.o .g . t h a t »h+1 6= »f , im p lyin g t h a t jIf ¡1j = p + 2 . B y Cla im 5 , »¡f y 62 E

fo r e a c h y 2 V ( I¤i ) a n d i 2 f 1 ; :::; sgnff ¡ 1 g. Mo r e o ve r , b y Cla im 4 , »¡f y 62 E fo r e a c h
y 2 f»f +1; »hg. If N ( »¡f ) µ V ( C ) , t h e n d( »¡f ) · ± ¡ 1 , a c o n t r a d ic t io n . Ot h e r wis e we c a n



3 2 A Sharp Improvement of a Theorem of Bauer and Schmeichel

a r g u e a s in t h e p r o o f o f Cla im 6 ( Ca s e a 1 .2 .1 ) .

Case a2. »h+1 = »f , »f +1 = »g, »g+1 = »h.
It fo llo ws t h a t s = 3 . A s s u m e w.l.o .g . t h a t f = 1 , g = 2 a n d h = 3 .

Case a2.1. E it h e r d2 ¸ 2 o r d5 ¸ 2 o r d8 ¸ 2 .
A s s u m e w.l.o .g . t h a t d2 ¸ 2 , t h a t is w+1 6= w3. If p = 0 , t h e n jI1j = 3 , im p lyin g t h a t

d2 = 1 , a c o n t r a d ic t io n . L e t p ¸ 1 . B y Cla im 4 , w+1 »2; w+1 »3 62 E. If N ( w+1 ) µ V ( C ) , t h e n
b y Cla im 4 , N ( w+1 ) µ V ( w+21

¡!
C w3 ) [ f»1g. S in c e jI1j = p + 3 , we h a ve jw+1

¡!
C w3j · p. B u t

t h e n d( w+1 ) · p + 1 = ± ¡ 2 , a c o n t r a d ic t io n . If N ( w+1 ) 6µ V ( C ) , t h e n we c a n a r g u e a s in t h e
p r o o f o f Cla im 6 ( Ca s e a 1 .2 .1 ) .

Case a2.2. d2 = d5 = d8 = 1 .
It fo llo ws t h a t jIij = 3 ( i = 1 ; 2 ; 3 ) , t h a t is p = 0 , ± = 3 a n d c = 9 . Cle a r ly hV ( C ) [ fx1gi

is t h e P e t e r s e n g r a p h . If V ( GnC ) 6= fx1g, t h e n it is n o t h a r d t o s e e t h a t c ¸ 1 0 , a c o n t r a -
d ic t io n . Ot h e r wis e , n = 1 0 ´ 1 ( mod 3 ) wit h c = 9 = 2 ± + 3 > 2 ± + 2 . Cla im 9 is p r o ve d .

Th u s , t h e r e s u lt h o ld s fr o m Cla im s 7 ,8 ,9 .

Case 2. p = ± ¡ 1 .
Cle a r ly, jNC ( xi ) j ¸ 1 ( i = 1 ; 2 ) .

Case 2.1. x1y1; x2y2 2 E fo r s o m e d is t in c t y1; y2 2 V ( C ) .
W e d is t in g u is h t h r e e m a in s u b c a s e s .

Case 2.1.1. Th e r e e xis t s a p a t h Q = z
¡!
Q y wit h z 2 V ( P ) , y 2 V ( C ) nfy1; y2g a n d

V ( Q ) \ V ( C [ P ) = fz; yg.
A s s u m e w.l.o .g . t h a t y 2 V ( y+1

¡!
C y¡2 ) . S in c e C is e xt r e m e , we h a ve

jy1
¡!
C yj ¸ jx1

¡!
P zj + 2 ; jy¡!C y2j ¸ jz

¡!
P x2j + 2 ; jy2

¡!
C y1j ¸ ± + 1 :

S u m m in g u p , we g e t jCj ¸ 2 ± + 4 , c o n t r a d ic t in g ( 1 ) .

Case 2.1.2. Th e r e e xis t s a p a t h Q = z
¡!
Q y wit h z 2 V ( y+1

¡!
C y¡2 ) , y 2 V ( y+2

¡!
C y¡1 ) a n d

V ( Q ) \ V ( C [ P ) = fz; yg.
B y Cla im 1 ( a 1 ) , jCj ¸ 2 p + 6 = 2 ± + 4 , c o n t r a d ic t in g ( 1 ) .

Case 2.1.3. Gnfy1; y2g h a s a t le a s t t h r e e c o m p o n e n t s .
It fo llo ws t h a t ¿ < 1 , c o n t r a d ic t in g t h e h yp o t h e s is .

Case 2.2. NC ( x1 ) = NC ( x2 ) = fyg fo r s o m e y 2 V ( C ) .
It fo llo ws t h a t

N ( x1 ) = ( V ( P ) [ fyg ) nfx1g; N ( x2 ) = ( V ( P ) [ fyg ) nfx2g:

Mo r e o ve r , x1
¡!
P v¡x2

á
P v is a lo n g e s t p a t h in GnC fo r e a c h v 2 V ( x+1

¡!
P x2 ) . S in c e G is 2 -

c o n n e c t e d , we h a ve wz 2 E fo r s o m e w 2 V ( P ) a n d z 2 V ( C ) nfyg. If w = x1, t h e n u s in g t h e



Zh. Nikoghosyan 3 3

p a t h zx1
¡!
P x2y, we c a n a r g u e a s in Ca s e 2 .1 . Ot h e r wis e we c a n u s e t h e p a t h yx1

¡!
P w¡x2

á
P wz.

Case 3. p ¸ ±.
Case 3.1. x1y1; x2y2 2 E fo r s o m e d is t in c t y1; y2 2 V ( C ) .
Cle a r ly, jy1

¡!
C y2j ¸ ± +2 a n d jy2

¡!
C y1j ¸ ± +2 , wh ic h yie ld s jCj ¸ 2 ±+4 , c o n t r a d ic t in g ( 1 ) .

Case 3.2. NC ( x1 ) = NC ( x2 ) = fyg fo r s o m e y 2 V ( C ) .
L e t y1; y2; :::; yt b e t h e e le m e n t s o f N

+
P ( x2 ) o c c u r r in g o n

¡!
P in a c o n s e c u t ive o r d e r . P u t

H = hV ( y¡1
¡!
P x2 ) i a n d

Pi = x1
¡!
P y¡i x2

á
P yi ( i = 1 ; :::; t ) :

S in c e Pi is a lo n g e s t p a t h in GnC fo r e a c h i 2 f 1 ; :::; tg, we c a n a s s u m e w.l.o .g . t h a t P is
c h o s e n s o a s t o m a xim iz e jV ( H ) j. If yiz 2 E fo r s o m e i 2 f1 ; :::; tg a n d z 2 V ( C ) nfyg,
t h e n we c a n a r g u e a s in Ca s e 3 .1 . Ot h e r wis e N ( yi ) µ V ( H ) [ fyg ( i = 1 ; :::; t) , t h a t is
jNH ( yi ) j ¸ ± ¡ 1 ( i = 1 ; :::; t) . B y L e m m a 3 , fo r e a c h d is t in c t u; v 2 V ( H ) , t h e r e is a p a t h
in H o f le n g t h a t le a s t ± ¡ 1 , c o n n e c t in g u a n d v. S in c e G is 2 -c o n n e c t e d , H a n d C a r e
c o n n e c t e d b y t wo ve r t e x d is jo in t p a t h s . Th is m e a n s t h a t t h e r e is a p a t h Q = y1

¡!
Q y2 o f

le n g t h a t le a s t ± + 1 wit h V ( Q ) \ V ( C ) = fy1; y2g. Fu r t h e r , we c a n a r g u e a s in Ca s e 2 .1 .

Case 3.3. E it h e r NC ( x1 ) = ; o r NC ( x2 ) = ;.
A s s u m e w.l.o .g . t h a t NC ( x1 ) = ;. B y a r g u in g a s in Ca s e 3 .2 , we c a n ¯ n d a p a t h

Q = y1
¡!
Q y2 o f le n g t h a t le a s t ± + 2 wit h V ( Q ) \ V ( C ) = fy1; y2g, a n d t h e r e s u lt fo llo ws

im m e d ia t e ly. Th e o r e m 1 is p r o ve d .

Refer ences

[1 ] D . B a u e r a n d E . S c h m e ic h e l, L o n g c yc le s in t o u g h g r a p h s , 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 .

[2 ] 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 .

[3 ] V . Ch v¶a t a l, \ To u g h g r a p h s a n d h a m ilt o n ia n c ir c u it s , D iscrete M ath., vo l. 5 , p p . 2 1 5 -2 2 8
1 9 7 3 .

[4 ] 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 .

[5 ] 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, Vorgetr. auf dem. int. K olloq., Ob e r h o f
( D D R ) , p p . 2 7 5 -2 8 6 , 1 9 7 7 .

Submitted 25.07.2018, accepted 20.11.2018.



3 4 A Sharp Improvement of a Theorem of Bauer and Schmeichel

´³áõ»ñÇ ¨ ÞÙ³ÛË»ÉÇ Ã»áñ»ÙÇ É³í³óáõÙ

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

²Ù÷á÷áõÙ

¸Çóáõù G-Ý n ·³·³Ã ¨ ± Ýí³½³·áõÛÝ ³ëïÇ×³Ý áõÝ»óáÕ ·ñ³ý ¿: ¶ñ³ýÇ
³Ù»Ý³»ñϳñ óÇÏÉÇ c »ñϳñáõÃÛ³Ý ³é³çÇÝ áã å³ñ½áõÝ³Ï ·Ý³Ñ³ï³Ï³ÝÁ ëï³ó»É ¿
¸Çñ³ÏÁ (1952). (i) Î³Ù³Û³Ï³Ý 2-ϳå³Ïóí³Í ·ñ³ýáõÙ, c ¸ m in fn; 2 ±g: ²Ûë ³ñ¹ÛáõÝùÁ
1986Ã-ÇÝ ´³áõ»ñÁ ¨ ÞÙ³ÛË»ÉÁ ɳí³óñ»óÇÝ 1-Ïáßï ·ñ³ýÝ»ñÇ Ñ³Ù³ñ. (ii) γٳ۳ϳÝ
1-Ïáßï ·ñ³ýáõÙ, c ¸ m in fn; 2 ±+2 g: êï³óí³Í »ñÏáõ ·Ý³Ñ³ï³Ï³ÝÝ»ñÝ ¿É ѳë³Ý»ÉÇ »Ý
n å³ñ³Ù»ïñÇ áñáß³ÏÇ ³ñÅ»ùÝ»ñÇ Ñ³Ù³ñ: Ü»ñϳ ³ß˳ï³ÝùáõÙ µ»ñíáõÙ ¿ ´³áõ»ñÇ
¨ ÞÙ³ÛË»ÉÇ ·Ý³Ñ³ï³Ï³ÝÇ ÙÇ É³í³óáõÙ, áñÁ ѳë³Ý»ÉÇ ¿ n å³ñ³Ù»ïñÇ ó³Ýϳó³Í
³ñÅ»ùÇ ¹»åùáõÙ:

Óëó÷øåíèå Òåîðåìû Áàóåðà è Øìåéõåëÿ
Æ. Íèêîãîñÿàí

Àííîòàöèÿ

Ïóñòü G ÿâëÿåòñÿ n âåðøèííûì ãðàôîì ñ ìèíèìàëüíîé ñòåïåíüþ ±. Â 1952ã.
Äèðàê ïîëó÷èë ïåðâóþ íåòðèâèàëüíóþ îöåíêó äëÿ äëèíû c äëèííåéøåãî öèêëà
ãðàôà G: (i) Â ëþáîì 2-ñâÿçíîì ãðàôå, c ¸ m in fn; 2 ±g. Ýòó îöåíêó â 1986ã. Áàóåð
è Øìåéõåëü óëó÷øèëè äëÿ 1-æåñòêèõ ãðàôîâ: (ii) Â ëþáîì 1-æåñòêîì ãðàôå,
c ¸ m in fn; 2 ± + 2 g. Ïîëó÷åííûå îöåíêè äîñòèãàåìû äëÿ îïðåäåëåííûõ çíà÷åíèé
ïàðàìåòðà n. Â íàñòîÿùåé ðàáîòå ïðåäëàãàåòñÿ óëó÷øåíèå îöåíêè Áàóåðà è
Øìåéõåëüÿ, êîòîðîå íåóëó÷øàåìà äëÿ âñåõ çíà÷åíèé ïàðàìåòðà n.