JOURNAL OF COMBINATORIAL THEORY, Series B 4, 177-186 (1988)
Hamilton Cycles in Regular 2-Connected Graphs
J. A. BONDY
University of Waterloo, University Avenue, Waterloo,
Ontario. Canada N2L 3GI
AND
M. KOUIDER
UniversitP de Paris-&d, Paris, France
Communicated by the Editors
Received February 25, 1986.
We give a simpler proof of the theorem due to B. Jackson and Y. Zhu, Z. Liu,
and Z. Yu that, except for the Petersen graph, every 2-connected k-regular graph
on at most 3k + 1 vertices is hamiltonian. 0 1988 Academic Press, Inc.
1. INTRODUCTION
In 121, Jackson proved that every 2-connected k-regular graph on at
most 3k vertices is hamiltonian. This result was later extended by Zhu et al.
C41 as
THEOREM. Every 2-connected k-regulfu graph on at most 3k + 1 vertices
is hamiltonian, except for the Petersen graph.
The purpose of this paper is to present a simpler proof of this theorem.
2. PROOF OF THEOREM
Let G be a 2-connected k-regular graph with vertex set V, where
1VI = n < 3k + 1. We suppose that G is not hamiltonian, an’d denote by C a
longest cycle in G such that G - C has the minimum possible number of
components and, subject to this requirement, a smallest possible com-
ponent W. Note that 1V(C)1 3 2k, by a theorem of Dirac [l], and so
1V( W)l d k + 1. We fix an orientation of C, and for c E V(C), denote by c+
177
0095-8956/88 $3.00
Copyright 0 1988 by Academic Press, Inc.
All rights ol reproduction in any form reserved.
178 BONDY AND KOUIDER
its successor on C, and by c- its predecessor on C. More generally, for
UC V(C), we set
u+ = (c+ I c E U}, U-=(cclCEU}.
There are two main cases to be considered.
Case 1. 1V( W)l = 1.
We set YO= V(W)= (a), and, for ia 1, define
Xj=N(Yj-,)
Yj= {a>u {CE V(C)/C-EX~ and c’EX~}.
Then
x, E x, c ...) Y, s Y, c ...
Following Jackson, we now set
x= u x,, Y=U Y,
*
x = 1x1, ,=I;,
z+ =X'\Y, z- =x-\Y
z=z+ uz-.
Thus
X=N(Y) (1)
and
IZf I = IZ-1 =x-y+ 1. (2)
Moreover, by [3, Lemma 12.31, XG V(C), and X does not contain two
consecutive vertices of C. The subgraph C- X consists of isolated vertices
(the elements of Y’(a}) and segments of C having initial vertex in Z+ and
terminal vertex in Z-. We denote these segments (taken in order around
Cl by Co, C,,..., C,-, and the initial and terminal vertices of Ci by pi and
qi, respectively. We set
si = V( C,), si= IsA, O<i<x-y
s=usi
R=T/?(SuXuY), r=IRl.
HAMILTON CYCLES 179
Thus, by (2h
c (si- l)= ISI - IZ+I =(n-~-x--)-(x-y+ l)=n--r-2x- l.(3)
We shall need the following result of Jackson [2, p. 301:
LEMMA 1. (a) Z+ and Z- are both stable sets.
(b) If (u, 0) eZ+ x Z-, then there are no two consecutive vertices in
the segment {v++, v+++ ,..., u--}, one a neighbour of u and the other a
neighbour of v.
(c) If (u, v) E (Z’)’ or (Z-)’ then there is no vertex c in the segment
{u++, u+++,..., IF} such that u is a neighbour of c and v a neighbour of CC.
(d) Each vertex of R is joined to at most one vertex of Z+ and at most
one vertex of Z-.
Let A, BE V. We denote by &(A, B) the number of edges of G with one
end in A and the other in B; the edges with both ends in A n B are counted
twice.
We first derive a lower bound for E(Z, X). By [2, Lemma 21,
'({Pj, qj}, si) <Sip 1, j# i. (4)
Also
&( { Pi, 4i), si) G 2(si- l). (5)
Therefore, by (3)
&(Z,S)=CCE({4i,4jj,sj)~C(X-Y+2)(sj-1)=(x-y+2)C(sj-1)
i j I
=(x-y+*)(n-r-2x11). (6)
BY (1)
E(Z, Y) = 0. (7)
By Lemma l(d),
E(Z, R) 6 2r. (8)
Finally, since G is k-regular,
E(Z, v) = 24X-y + 1). (9)
180 BONDY AND KOUIDER
From (6)-(9),
4-T X) = E(Z, V) - E(Z, R) - E(Z, S) = &(Z, Y)
324x-y+l)-2r-(x-y+2)(n-r-2x-1)
=W-.v)+r(x-.v)+(x-y+2)((3k+ 1 -n)+2(x-k)). (10)
Next, we obtain an upper bound for E(S, X). Since G is k-regular,
E( V, X) = kx.
By (l), and since G is k-regular,
E( Y, X) = ky.
Also,
E(R, X) 3 0
and
&(X, X) 2 0.
From (ll)-( 14),
E(S,X)=&(V,X)-&(R,X)--(X,X)-&(Y,X)dkx-ky=k(x-y). (15)
Now, combining (10) and (15), we obtain
k(x-y)+r(x--y)+(x-y+2)((3k+l-n)+2(x-k))
< 4-C X) < E(S, X) d k(x - y), (16)
whence
r(~--y)+(x-y+2)((3k+1-n)+2(x-k))~0. (17)
But, by (15),
k(x-.v)>e(S, X)>,E(~, X)> /zI =x-y+ 1
and so x>y. Since r>O, n<3k+ 1 and x>k, we deduce from (17) that
Y=O, n=3k+ 1, x=k, from (16) that
E(Z, X) = &(S, X) (18)
HAMILTON CYCLES 181
and from (4) and (5) that
4{Pi, 4i), sj,=sj- 1 if j#i (19)
&( { pi, qi}, sj) = 2(si - l). (20)
Suppose that there exists i such that si > 3. Let u E Si\Z. By (20) u+ is
joined to pi. Therefore, by Lemma l(c), u cannot be joined to a vertex of
Z’\{pi}. Similarly u cannot be joined to a vertex of Zp\{qi}. By (18),
every neighbour of u lies in the set
Thus
d(u)< IS\(Zu {u})l+ I{49 4’11=y<x=k
a contradiction. Therefore si = 2 for every i.
Since ICI =y1--Y- 1=3k,
y= 1.
BY (19)>
&((Pi, qi}> {Pj, qj))= l if i#j.
It follows that pi is joined to a vertex qj for some j# i (otherwise
d(qi) > k + 1) and, similarly, that qi is joined to some vertex pI for 1# i.
Using Lemma l(b) we deduce that pi is joined to qi+ i, and qi is joined
to pip 1 (indices taken modulo k). Thus we have the situation depicted in
Fig. 1. The cycle C’ =q1x2p2q2 “.x0 ax,q,p,q, has length 3k. So, on
replacing (C, a) by (C’,p,) in the above arguments, we deduce that p1 is
joined to every qj except qo. Similarly q, is joined to every pj except p2.
Thus, if k>4, p1 is joined to q3 and q1 is joined to p3. This contradicts
Lemma l(b). Therefore k = 3 and G is the Petersen graph.
FIGURE 1
182 BONDYAND KOUIDER
CASE 2. Iv(w)1 32.
The following two lemmas will be needed. We say that a path P is
strongly joined to a cycle C if the ends of P are connected by disjoint paths
to distinct vertices of C.
LEMMA 2. Let G be a 2-connected graph with 6 3 k 3 3, let C be a cycle
in G, and let W be a component of G - C such that 2 6 1V( W)l <k + 1. Then
there is a longest path P in W which is strongly joined to C.
ProoJ Let Q = wowI ... w, be a longest path in W, chosen so that
d,(w,) + d,(w,) is as large as possible.
If d,(w,)=O, then, since 6a.k and IV(W)l<k+l, IV(Q)I=k+l and
w,, is joined to every other vertex of Q. For 1 < i < 1- 1, consider the path
By the choice of Q, d,( wi) = 0. Since this is true for each i, 1 d i 6 1- 1, w(
is a cut vertex of G. But this contradicts the hypothesis that G is 2-connec-
ted. Hence d&w,,) > 0 and, similarly, d&w,) > 0.
If w,, and wI are joined to distinct vertices of C, we may take P = Q.
Thus we may assume that w,, and w, are joined to one and the same vertex
u of c.
We claim that 1V(Q)1 = I V( W)l. If not, then, since 6 > k, w0 is joined to
all k- 1 other vertices of Q, and there is exactly one vertex
w E V( W)\V(Q). Since G is connected, w is joined to some vertex WOEV(Q).
But then the path
contradicts the choice of Q as a longest path in W.
Since G is 2-connected, there is an edge wiu, with v E V(C)\(u). If
wOwi+i E E, we may take
Thus we may assume that wow;+ I $ E and, similarly, that wi- 1w,$ E. Since
6>k, this implies that IV(W)I=k+l, Q=w,,wl...wk, w0 is joined to
every other vertex of Q but wit,, and wI is joined to every other vertex of
Q but wiP r. Furthermore, for each j, j # i, wj is either joined to no vertex of
C or to just the vertex U. Since k 3 3, either wiel #w. or wi+ l #wk. Since
d,(wi_ 1) d 1 and ~~~~I wk $ E, lzii- 1wi+ 1E E. We now take
Remark. Lemma 2 is sufficient for our purposes here. However, a
HAMILTON CYCLES 183
stronger assertion would be needed to handle 2-connected k-regular graphs
on 3k + 2 or more vertices. The following lemma, which we state without
proof, is of interest in this regard. An example shows that the upper bound
imposed on ( V( W)( is best possible.
LEMMA 2’. Let G be a 2-connected graph with 6 b k, let C be a cycle in
G, W a component of G - C such that 2 d (V( W)l d 2k - 2, and P a path in
W strongly joined to C, and as long as possible subject to this requirement.
Then P is a maximal path in W.
LEMMA 3. Let C be a cycle, and let X” and Xb be two nonempty subsets
of V(C) such that
(i) d&x, y)>sfor (x, ~)E(JF)~, a=a, 6,
(ii) d,(x,y)atfor (x,y)~XaxX~,
where s < t. Then
where xab = IX” n Xbl and, for a=a,b,x”=IX”I-xub, 6”=1 if x”#O,
6”=0 y-xX=0.
Proof of Lemma 3. We fix an orientation of C and consider, for each
vertex in X” u Xb, the length of the segment of C between this vertex and
the next vertex in x” u Xb.
Each vertex in X” n Xb is followed by a segment of length at least t.
Moreover, for a = a, b, if xa # 0, at least one vertex of X*\(P n Xb) is
followed by a segment of length at least t. Finally, each other element of
X” u Xb is followed by a segment of length at least s. Therefore
IV(C)J 3 t(X”b+P+~b)+S(Xa+Xb-~u-c3b)
=s(x”+Xb)+tX=b+(t-s)(6”+6b). n
We now proceed with the proof of Case 2. Let P be a path in W strongly
joined to C, and as long as possible subject to this requirelment, and let p
be the length of P. Denote by a and b the origin and terminus of P, respec-
tively, and set
X”= N(a) n V(C), Xb = N(b) n V(C).
Since C is a longest cycle in G,
d,b, Y 12 2 for (x, y)~ (Xa)2 or (Xb)’
We apply Lemma 3 with s = 2, t = p + 2.
184 BONDY AND KOUIDER
If x0, Xb > 1,
I V(C)1 3 2(xU + x”) + (p + 2) XUb+ 2p 3 2(x” + xab) + (x” + XUb) + Xb + 2p
22(k-p)+(k-p)+ 1+2p=3k-p+ 1.
Thus
I~(G)l3lV(C)I+IV(W)1~(3k-p+l)+(p+1)=3k+2,
a contradiction.
If x”> 1, xb=O or xnfO, xb> 1, then xab>l and
IV(C)1 32(x”+x”)+(p+2)X”b+p3(p+2)(X”b+ 1).
Since I V( W)l < k + 1, p < k. If p = k, then
IV(C)1 >2(k+2)
and
IV(G)1 3 I J”(C)1 + I V( W)l 3 (2k + 4) + (k + 1) = 3k + 5.
If p 6 k - 1, then
t~(C)I3(p+2)(k-p+1)=3k-p+l+(p-l)(k-p-1)>3k-p+1
and
I~(G)/3l~(C)l+IV(W)l>(3k-p+1)+(p+l)=3k+2.
In either case, we have a contradiction.
If xn=xb=O, then ~“~22 and
I V(C)/ > (p + 2) XUb.
Ifp=k-1 or k, then
IV(C)1 32(k+ 1)
and
iV(G)/31V(C)I+(V(W)I3(2k+2)+k=3k+2.
Ifp<k-2, then
I v(C)1 2 (k-p)(p + 2) + Wb - (k -p)Np + 2)
= 3k - 3p + (p - l)(k -p) + (xnb - (k -p))(p -t- 2)
a 3k -p - 2 + (xab - (k-p))(p + 2).
HAMILTON CYCLES 185
Thus
I VG)I 2 IUC)1 + I VW
23k+l+(IV(W)I-(p+2))+(xUb-(k-p))(p+2).
Since IV(G)1 d3k+l and IL’(W)I >p+ 1, we deduce that
IUW e+2
and
X ab=k-p.
Because I I’( W)( 6p + 2 < k, every vertex of W is joined to at least one ver-
tex of C. Because A,(a) = d,(b) = k - xub =p, a and b are joined to each
other and to every other vertex of P. Suppose that there exists
XE V( W)\V(P). Then W contains an (x, a)- or (x, b)-path of length p + 1.
Because xab = k -p 3 2, this path is strongly joined to C. But this con-
tradicts the choice of P. Therefore no such vertex x exists, and
V(W) = V(P). Now, for each vertex y of P, there is a (y, b)-path of length p
in W that is strongly joined to C. It follows that Wz KP+ i and that each
vertex of W is joined to each vertex of Xub.
Suppose that d&x, y) =p + 2 for some (x, y) E (X0”)*. Then the cycle
C’=xaPbyy+ ..-x
is a longest cycle of G. Moreover, G - C’ has the same number of com-
ponents as G - C, and the component w’ of G - C’ whose vertices are the
internal vertices of the (x, y)-segment of C has the same order as W,
namely p + 1. Applying the above analysis of W to W’, we deduce that
wEKp+l. Also, each vertex of IV’ must be joined to each vertex of Xub.
Otherwise, since G is k-regular, some vertex of IV would be joined to a
vertex z’ E V(C)\ V( IV’), z’ $ Pb. Then, denoting by x’ and y’ the first ver-
tices of Xub preceding and following z‘ on C, respectively, we deduce from
the fact that C is a longest cycle in G that d&x’, y’) 3 2p + 4. But now
iv(C)ia(k-p-1)(~+2)+(2~+4)
=3k+2+(k-p-l)(p-l)-(p+l)
and so
Iv(G)1 = IV(C)1 + IV(W)1 >3k+2+(k-p-l)(p-1)>3k+2,
a contradiction.
186 BONDY AND KOUIDER
If there are m pairs (x, y)~ (Xab)2 such that d,(x, y) =p+ 2, then the
degree of any vertex z E X”’ satisfies
4~)3~~(~)+~dz)3(p+l)+m(p+1)+2-m=mp+p+3.
Since d(z) = k, we deduce that
k>mp+p+3.
But now
iv(c)1 >(k-p)(p+3)-m=3k+(k-p-3)p-m>3k+m(p2-1)>3k
and
This final contradiction establishes the theorem. 1
ACKNOWLEDGMENTS
We wish to thank Fan Genghua for suggesting the use of Lemma 2 in place of our original
Lemma 2’. This research was funded in part by NSERC Operating Grant A7331.
REFERENCES
1. G. A. DIRAC, Some theorems on abstract graphs, Proc. London Math. Sot. 2 (1952), 69-81.
2. B. JACKSON,Hamilton cycles in regular 2-connected graphs, J. Combin. Theory Ser. B 29
(1980) 2746.
3. D. R. WOODALL, Sufficient conditions for circuits in graphs, Proc. London Muth. Sot. (3)
24 (1972), 739-755.
4. ZHU YONGJIN,LIU ZHENHONG,AND Yu ZHENGGUANG,An improvement of Jackson’s result
on Hamilton cycles in 2-connected regular graphs, in “Cycles in Graphs” (B. R. Alspach
and C. D. Godsil, Eds.), Ann. Discrete Math. No. 27, pp. 237-247, 1985.
