Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 4 (2011) 125–139
Gray code numbers for graphs∗
Kelly Choo , Gary MacGillivray †
Mathematics and Statistics, University of Victoria
P.O. Box 3060 STN CSC Victoria, B.C., Canada V8W 3R4
Received 2 August 2010, accepted 25 October 2010, published online 28 March 2011
Abstract
A graph H has a Gray code of k-colourings if it is possible to list all of its k-colourings
in such a way that consecutive elements in the list differ in the colour of exactly one vertex.
We prove that for any graph H , there is a least integer k0(H) such that H has a Gray
code of k-colourings whenever k ≥ k0(H). We then determine k0(H) whenever H is a
complete graph, tree, or cycle.
Keywords: Graph colouring, cyclic Gray code.
Math. Subj. Class.: 05C15, 05A05
1 Introduction
The term combinatorial Gray code refers to a list of combinatorial objects so that each
object is listed exactly once, and consecutive objects in the list differ in some prespecified,
small way. According to Savage [13], this term was introduced in 1980 as a generalization
of minimal change listings. The precise definition of minimal change depends on what is
being listed but, informally, the idea is that consecutive objects in the list differ from each
other as little as possible. For example, the Binary Reflected Gray Code (BRGC) is a listing
of all 2n binary strings of length n in which consecutive strings differ from one another at
exactly one position.
A combinatorial Gray code corresponds to a Hamilton path or cycle in the graph where
the vertices are the objects, and two vertices are joined by an edge if the objects differ in the
prespecified way. The graph has a Hamilton path if and only if a combinatorial Gray code
exists. If the graph has a Hamilton cycle, then there is a listing in which the first and last
objects in the list also differ in the prespecified way, and the corresponding combinatorial
Gray code is said to be cyclic.
∗In remembrance of Graph Colour Mike Albertson and his good taste in mathematics, books and sports.
†The author gratefully acknowledges the support of the Natural Science and Engineering Research Council of
Canada.
E-mail addresses: chook@math.uvic.ca (Kelly Choo), gmacgill@math.uvic.ca (Gary MacGillivray)
Copyright c© 2011 DMFA Slovenije
126 Ars Math. Contemp. 4 (2011) 125–139
A survey of results concerning combinatorial Gray codes can be found in Savage [13].
A significant amount of research described there occurred following Herb Wilf’s invited
address Generalized Gray Codes at the 1988 SIAM Conference on Discrete Mathematics
in San Francisco. The results and open problems he described appear in his SIAM mono-
graph [16].
A combinatorial family which has not yet been explored in terms of Gray codes is the
set of proper k-colourings of a graph. Let H be a graph. We regard two k-colourings f1
and f2 of H as being different if there is a vertex x ∈ V (H) such that f1(x) 6= f2(x). The
following is one of the most important definitions in the paper. A (cyclic) Gray code of
k-colourings for H is a listing of all of the distinct k-colourings of H so that consecutive
colourings in the list, including the last and first, differ in the colour of exactly one vertex.
Unless otherwise stated, the Gray codes of k-colourings in this paper are cyclic and we will
therefore drop the adjective “cyclic”.
The problem of recolouring a graph so that the colour of precisely one vertex is changed
at each step has been considered in the literature [2, 3, 4, 5, 7, 9, 10]. These results will be
briefly surveyed in the next section.
We conclude this section with a brief summary of the remainder of the paper. Section
two provides an introduction to some concepts in graph theory and combinatorial Gray
codes that are directly related to this work. In section three we introduce C-graphs, a class
of graphs that arise frequently in our work, and determine some sufficient conditions for
C-graphs to be Hamiltonian. These graphs appear in the proof of the existence theorem:
For any graph H , there is a least integer k0(H) such that there exists a Gray code for k-
colourings of H for all integers k ≥ k0(H). The remainder of the paper is devoted to
determining k0(H) for complete graphs, trees, and cycles. This is done in sections four
through six, respectively.
2 Preliminaries
This section summarises results that will be used concerning vertex colourings, Hamil-
ton paths and cycles, and combinatorial Gray codes. Our terminology is consistent with
Bondy and Murty [1]. Throughout this section, let H be a graph with vertex set V (H) =
{v1, v2, . . . , vn} and edge set E(H) = {e1, e2, . . . , em}.
A proper k-colouring ofH is a function f : V (H)→ {1, 2, . . . , k} such that whenever
vertex x is adjacent to vertex y, f(x) 6= f(y). Since we only consider colourings of this
type, for brevity we will drop the adjective “proper” and refer to these as k-colourings. Note
that the function f need not be onto, that is, not every colour must be assigned to some
vertex of H . A graph H is k-colourable if it has a k-colouring. The chromatic number
χ(H) is the minimum k for which H has a k-colouring. A graph with chromatic number
equal to k is sometimes called a k-chromatic graph. With respect to the enumeration
v1, v2, . . . , vn of V (H), we will sometimes write a k-colouring of H in one-line notation:
f(v1)f(v2) . . . f(vn).
A Hamilton path in H is a path that contains every vertex of H . Analogously, a Hamil-
ton cycle in H is a cycle that contains every vertex of H . A graph with a Hamilton cycle
is said to be Hamiltonian. Having a Hamilton cycle is a stronger condition than having a
Hamilton path. A graph with a Hamilton path between any two distinct vertices is called
Hamilton connected.
Let H be a graph and let π = x1, x2, . . . , xn be an enumeration of the vertices of H .
K. Choo and G. MacGillivray: Gray code numbers for graphs 127
Let Hi be the subgraph of H induced by {x1, x2, . . . , xi}, for i = 1, 2, . . . , n. Define
Dπ = max1≤i≤n dHi(xi), where the notation dF (v) denotes the degree of the vertex v in
the graph F . The quantity minπDπ + 1 is known as the colouring number of H and is
denoted col(H) [8]. It satisfies the bound χ(H) ≤ col(H) ≤ ∆(H) + 1, where ∆(H)
is the maximum degree of H . We note that other authors whose work is referenced below
define the colouring number in such a way that the “+1” is not included (cf. [4, 7]).
The k-colouring graph of H is defined to be the graph Gk(H) with vertex set the set
of all k-colourings of H , with two k-colourings fi and fj being adjacent in Gk(H) if and
only if fi(x) = fj(x) for all vertices x ∈ V (H) except one. The graph H has a Gray
code for k-colourings if and only if the graph Gk(H) has a Hamilton cycle. The number
of vertices of Gk(H) is the value of the chromatic polynomial of H at k (see [1], Section
8.4).
Connectedness of the k-colouring graph has been fairly extensively studied. It arises
in the study of efficient algorithms for almost-uniform sampling of k-colourings [7, 9, 10].
For k ∈ {2, 3}, the k-colouring graph of a k-chromatic graph is never connected, while for
each k ≥ 4 there are k-chromatic graphs for which Gk is connected, and others for which
it is not connected [4]. The problem of deciding if the 3-colouring graph of a bipartite
graph is not connected is NP-complete, but Polynomial for planar bipartite graphs [5]. On
the other hand, the k-colouring graph of H is connected for all k ≥ col(H) + 1, and this
bound is best possible [3] (also see [7]).
A variation on the problem of deciding whether the k-colouring graph is not connected
is the problem of deciding whether two given k-colourings of the graph H lie in the same
component of Gk(H). The diameter of any component of the 3-colouring graph of a graph
with n vertices is O(n2) [3]. By contrast, for each fixed k ≥ 4, the problem of deciding if
two k-colourings of H lie in the same component of Gk(H) is PSPACE-complete, and the
diameter of a component can be superpolynomial in the number of vertices of H [2].
In order to prove the existence of Gray codes for k-colourings, we sometimes rely on
the existence of Gray codes for other combinatorial families. We next review some results
about the Binary Reflected Gray Code (BRGC) and a particular Gray code of permutations.
The BRGC is a listing of the 2n binary strings of length n so that consecutive strings in
the list, including the last and first, differ in exactly one position. It is defined recursively
by L1 = 0, 1; and for n > 1, Ln = 0 · Ln−1, 1 · Ln−1, where ‘·’ denotes concatenation
and Ln−1 lists the elements of Ln−1 from last to first [13]. Thus, L2 = 00, 01, 11, 10 and
L3 = 000, 001, 011, 010, 110, 111, 101, 100.
The n-cube is the graph Qn whose 2n vertices are the binary strings of length n, with
two binary strings being adjacent if they differ in exactly one position. Since the BRGC is
cyclic, it describes a Hamilton cycle in Qn for all integers n ≥ 2.
In our work on trees (see Theorem 5.2), we will be interested in when Qn has a Hamil-
ton path starting at 00 · · · 0 and ending at 11 · · · 1. The circumstances under which it does
are characterised in the following lemma, which appears as an exercise in [12] (page 185,
#20) and also follows from a result in [14]. We shall include a short proof for completeness.
Lemma 2.1. There exists a Hamilton path from 00 · · · 0 to 11 · · · 1 in Qn if and only if
n ≥ 1 and n is odd.
Proof. (⇒) The graph Qn is bipartite with bipartition (X,Y ), where X is the set of binary
sequences of length n with an even number of ones, and Y is the set of binary sequences
of length n with an odd number of ones. Since |X| = |Y | and 00 · · · 0 ∈ X , a Hamilton
128 Ars Math. Contemp. 4 (2011) 125–139
path ending at 11 · · · 1 is possible only when 11 · · · 1 ∈ Y . Thus, if a Hamilton path with
the specified ends exists, n ≥ 1 and n is odd.
(⇐) Any odd integer n equals 2k+1 for some integer k ≥ 0. The proof is by induction
on k. The statement is clearly true when k = 0. Assume, for some t ≥ 0, that the graph
Q2t+1 has a Hamilton path P from 00 · · · 0 to 11 · · · 1. Without loss of generality, the
second vertex on P is 100 · · · 0. By symmetry, Q2t+1 has a Hamilton cycle that uses the
edge (00 · · · 0)(100 · · · 0), that is, Q2t+1 has a Hamilton path S from 00 · · · 0 to 100 · · · 0.
The desired Hamilton path inQ2t+3 is obtained fromR = P ·00, P ·01, P ·11 by inserting
S · 01 between the first two vertices of R (as before, ‘·’ denotes concatenation and P is
denotes the reverse of the sequence P ). Thus, by induction, if n ≥ 1 is odd, then Qn has a
Hamilton path from 00 · · · 0 to 11 · · · 1.
We now look at a particular Gray code for permutations. Recall that the symmetric
group Sn is the group of all permutations of {1, 2, . . . , n} under the operation of function
composition. When listing all the permutations of an n-set, an obvious choice for a minimal
change condition is that consecutive permutations in the list differ by a transposition (a
permutation that exchanges two elements and leaves all others fixed). Let X be a subset of
the permutations in Sn such that the identity element e /∈ X andX is closed with respect to
inverses (x−1 ∈ X whenever x ∈ X). The Cayley graph with cymbal X on the symmetric
group Sn, denoted Cay(X : Sn), is defined to have vertex set V (Cay(X : Sn)) = {g :
g ∈ Sn} and an edge joining g to g′ if and only if g′ = gx for some x ∈ X . If every
element g ∈ Sn can be written g = g1g2 . . . gj for some elements g1, g2, . . . , gj ∈ X then
X is a generating set of Sn. It is known that Cay(X : Sn) is connected if and only if X
is a generating set. It is an open question as to whether every connected Cayley graph on
Sn is Hamiltonian [6]. This question has been settled by Kompel’makher and Liskovets
in the case where the generating set X is a set of transpositions [11]. Corollary 2.2 below,
due to Slater [15], is a special case of this result. It implies that it is possible to list all
permutations in Sn so that consecutive permutations in the list differ by a transposition of
the number in the first position and a number in some other position.
Corollary 2.2. [15] The Cayley graph Cay({(1, 2), (1, 3), . . . , (1, n)} : Sn) is Hamilto-
nian.
3 C-graphs and the existence theorem
The main result of this section states that for every graph H , there exists a constant k0(H)
such that H has a Gray code of k-colourings for every integer k ≥ k0(H). The proof
of this theorem, and others in this paper, involves a particular family of nicely structured
graphs which we call C-graphs. These are introduced below, and some conditions under
which such graphs are Hamiltonian are developed. Throughout this section subscripts are
to be interpreted modulo N .
A C-graph with vertex partition F0, F1, . . . , FN−1 is a graph G together with a par-
tition F0, F1, . . . , FN−1 of V (G) so that, for i = 0, 1, . . . , N − 1, the subgraph induced
by Fi is a Hamilton connected graph with at least three vertices. The basic structure of a
C-graph, as it is used in Lemma 3.1 and its corollary, is shown in Figure 1.
Lemma 3.1. Let G be a C-graph with vertex partition F0, F1, . . . , FN−1. If, for i =
0, 1, . . . , N − 1, there are vertex disjoint edges xiyi+1 with xi ∈ Fi and yi+1 ∈ Fi+1, then
G is Hamiltonian.
K. Choo and G. MacGillivray: Gray code numbers for graphs 129
Proof. For 0 ≤ i ≤ N − 1 and u,w ∈ Fi, let Pi(u,w) denote a Hamilton path from
u to w in the subgraph of G induced by Fi. Then the concatenation of x0, P1(y1, x1),
P2(y2, x2), . . . , PN−1(yN−1, xN−1), P0(y0, x0) is a Hamilton cycle in G.
We now develop some conditions under which Lemma 3.1 applies. These will be useful
in our subsequent work.
.  .  .
x
F F F FF
N-1N-2210
Figure 1: The basic structure of a C-graph in Lemma 3.1 and Corollary 3.2.
Let G be a graph, and X and Y be disjoint subsets of V (G). We use [X,Y ] to denote
the set of edges with one end in X and the other end in Y .
Corollary 3.2. Let G be a C-graph with vertex partition F0, F1, . . . , FN−1. Suppose that,
for j = 0, 1, . . . , N − 1, the set [Fj , Fj+1] contains at least two vertex disjoint edges. If
there exists i, 0 ≤ i ≤ N − 1, such that some vertex x ∈ Fi has a neighbour in Fi+1 and
[Fi−1, Fi − {x}] (still) contains at least two vertex disjoint edges, then G is Hamiltonian.
Proof. By the symmetry in the definition of C-graphs we may, without loss of generality,
assume that i = 0. For j = 0, 1, . . . , N − 2, define the edges xjyj+1 ∈ [Fj , Fj+1]
inductively as follows. Let x0 = x and y1 be any neighbour of x in F1. The vertex
y1 exists by hypothesis. Suppose x0y1, x1y2, . . . , xj−1yj , (j ≥ 1), have been chosen. It
follows from the hypothesis that the set of edges [Fj−{yj}, Fj+1] is not empty. Let xjyj+1
be any edge in this set, where xj ∈ Fj − {yj} and yj+1 ∈ Fj+1. Finally, it follows from
our hypothesis that the set of edges [FN−1−{yN−1}, F0−{x0}] is not empty. (Remember
that x0 = x.) Let xN−1y0 be any edge in this set, where xN−1 ∈ FN−1 − {yN−1} and
y0 ∈ F0 − {x0}. The result now follows from Lemma 3.1.
Corollary 3.3. Let G be a C-graph with vertex partition F0, F1, . . . , FN−1. Suppose that,
for j = 0, 1, . . . , N − 1, the set [Fj , Fj+1] contains at least two vertex disjoint edges. If
there exists i, 0 ≤ i ≤ N − 1, such that [Fi, Fi+1] contains at least three vertex disjoint
edges, then G is Hamiltonian.
130 Ars Math. Contemp. 4 (2011) 125–139
Proof. By the symmetry in the definition of C-graphs we may, without loss of generality,
assume that i = N − 1. Let x ∈ F0 be any vertex such that there are two vertex disjoint
edges in [F0, F1], one of which is incident with x. Since at most one of the three disjoint
edges in [FN−1, F0] is incident with x, the result follows from Corollary 3.2.
We now prove that every graph has a Gray code of k-colourings when k is sufficiently
large. As a consequence, it becomes of interest to determine the minimum number of
colours necessary for certain graphs to have a Gray code of k-colourings. This is the topic
of the remaining sections of the paper.
Theorem 3.4. Let H be a graph. If k ≥ 2 + col(H), then Gk(H) is Hamiltonian.
Proof. Consider an enumeration σ = v1, v2, . . . , vn of the vertices of H such that Dσ =
minπDπ . Let k ≥ 3 + Dσ = 2 + col(H). We show by induction on i that each graph
Gk(Hi), 1 ≤ i ≤ n, is Hamiltonian.
Since k ≥ 3, the sequence 1, 2, . . . , k, 1 is a Hamilton cycle in Gk(H1). Suppose that
the sequence f0, f1, . . . , fN−1, f0 is a Hamilton cycle in Gk(Hi−1), for some integer i
with 2 ≤ i ≤ n.
Consider Gk(Hi). For j = 0, 1, . . . , N − 1, let Fj be the set of k-colourings of Hi
that agree with fj on V (Hi−1). Since k ≥ 3 + Dσ ≥ 3 + dHi(vi), for each k-colouring
of Hi−1 there are at least three colours that can be assigned to vi in order to extend it to
a k-colouring of Hi. Therefore, each set Fj contains at least three k-colourings of Hi.
Furthermore, by its definition, each set Fj induces a complete subgraph of Gk(Hi). Since
complete graphs with at least three vertices are Hamilton connected and F0, F1, . . . , FN−1
is a partition of the vertex set of Gk(Hi), we have that Gk(Hi) is a C-graph.
Suppose fj and fj+1 differ in the colour assigned to vertex wj . If wj is not adjacent
to vi, then every colour assigned to vi by some colouring in Fj is also assigned to vi by
some colouring in Fj+1. Thus, every vertex in Fj has a neighbour in Fj+1 corresponding
to the k-colouring that agrees with it on vi. Since these edges are vertex disjoint, in this
case [Fj , Fj+1] contains at least three vertex disjoint edges. If wj is adjacent to vi, the
vertex in Fj corresponding to the k-colouring of Hi that assigns colour fj+1(wj) to vi has
no neighbour in Fj+1, but every other vertex in Fj has a neighbour in Fj+1. In this case
[Fj , Fj+1] contains at least two vertex disjoint edges. Thus, if there exists j such that wj is
not adjacent to vi, the graph Gk(Hi) is Hamiltonian by 3.3.
Otherwise, for all j, 0 ≤ j ≤ N−1, wj is adjacent to vi. From the above argument, we
have that [Fj , Fj+1] always contains at least two vertex disjoint edges. Choose a colouring
cN−1 ∈ FN−1 which has a neighbour c0 ∈ F0. There exists a largest integer r ≤ N − 1
such that fr−1 uses colour cN−1(vi) but fr does not. By definition of r, no colouring
in Fr−1 assigns colour cN−1(vi) to vi but, for t = r, r + 1, . . . , N − 1, there exists a
colouring ct ∈ Ft such that ct(vi) = cN−1(vi). Hence, there exists x = cr ∈ Fr which
has a neighbour in Fr+1 but no neighbour in Fr−1. Since [Fr−1, Fr] contains two vertex
disjoint edges, and no edge in [Fr−1, Fr] is incident with x, we have that [Fr−1, Fr −{x}]
(still) contains two vertex disjoint edges. The induction step that Gk(Hi) is Hamiltonian
now follows from 3.2
Corollary 3.5. For any graphH , there exists a least integer k0(H) such thatH has a Gray
code of k-colourings for any integer k ≥ k0(H).
We call the integer k0(H) in Corollary 3.5 the Gray code number of H .
K. Choo and G. MacGillivray: Gray code numbers for graphs 131
4 The Gray code number of complete graphs
For all integers n ≥ 1, the Gray code number k0(Kn) is determined by the following
theorem.
Theorem 4.1. k0(K1) = 3, and k0(Kn) = n+ 1 for n ≥ 2.
Proof. The first statement is easy to see. We prove the second statement.
For n ≥ 2, any two n-colourings of Kn differ in the colour of at least two vertices.
Hence Gn(Kn) has n! > 1 vertices and no edges. Therefore, if Gk(Kn) is Hamiltonian,
then k ≥ n+ 1.
Since col(Kn) = n, by Theorem 3.4 we have k0(Kn) ≤ n + 2. Hence we need only
consider the case k = n + 1. We claim that Gn+1(Kn) is isomorphic to Cay(X : Sn+1),
where X is the generating set of transpositions X = {(1, 2), (1, 3), . . . , (1, n+ 1)}.
Let φ : V (Cay(X : Sn+1)) → V (Gn+1(Kn)) be the isomorphism defined by φ(π) =
π(2)π(3) · · ·π(n + 1), where the right hand side is an (n + 1)-colouring of Kn written
in one-line notation. Then, π1π2 ∈ E(Cay(X : Sn+1)) if and only if π1 and π2 differ
by a transposition in X . The permutations π1 and π2 differ by a transposition involving
1 if and only if φ(π1) and φ(π2) differ in the colour of exactly one vertex, that is, if and
only if φ(π1)φ(π2) ∈ E(Gn+1(Kn)). Hence, by Corollary 2.2, the graph Gn+1(Kn) is
Hamiltonian.
5 Gray code numbers for trees
In this section we determine the Gray code number of any tree. Since, for a tree T ,
col(T ) ≤ 2, we have by Theorem 3.4 that k0(T ) ≤ 4.
Proposition 5.1. If H is a connected bipartite graph, then k0(H) ≥ 3.
Proof. A connected bipartite graph has exactly two 2-colourings, so G2(H) has exactly
two vertices and cannot be Hamiltonian.
Thus, 3 ≤ k0(T ) ≤ 4 for any tree T . It turns out that equality can occur in both the
upper and lower bound.
A complete bipartite graph K1,n is also called a star. For n ≥ 2, the unique vertex v
adjacent to all vertices of the star is called its centre. When n = 1, either vertex can be
chosen to be the centre of the star. A star is called odd or even when its number of vertices,
(n+ 1), is odd or even, respectively.
Theorem 5.2. Let T be a star with n+ 1 ≥ 2 vertices. Then G3(T ) is Hamiltonian if and
only if T is even.
Proof. Let the vertex set of the star K1,n be {v0, v1, v2, . . . , vn}, where v0 is the centre.
(⇐) When n = 1, K1,1 is just K2 and G3(K2) is Hamiltonian by Theorem 4.1.
Suppose n ≥ 3 is odd. By Lemma 2.1, the set of all 2n sequences of length n with
entries from {a, b} can be listed starting with aa · · · a and ending with bb · · · b. Let P (a, b)
denote any such listing (an acyclic Gray code). Then, a Hamilton cycle in G3(T ) is 1 ·
P (2, 3), 2 · P (3, 1), 3 · P (1, 2), where ‘·’ denotes concatenation.
(⇒) Now suppose n ≥ 2 and f0, f1, . . . fN−1, f0 is a Hamilton cycle in G3(T ). Note
that two colourings can differ in the colour assigned to v0 only if the remaining vertices
are all coloured with the third colour. Thus all 2n colourings of T in which v0 is coloured
132 Ars Math. Contemp. 4 (2011) 125–139
1 appear consecutively on the cycle, say with f0 = 1222 · · · 2 at one end of the segment
and f2n−1 = 1333 · · · 3 at the other. Consider each of the colourings in the sequence
f0, f1, . . . , f2n−1 restricted to V (T ) − {v0} = {v1, v2, . . . , vn}. If all 2’s are replaced by
0’s and all 3’s are replaced by 1’s, then the resulting sequence describes a Hamilton path in
Qn starting at 00 · · · 0 and ending at 11 · · · 1. Hence, by Lemma 2.1, n is odd.
We now show in several steps that G3(T ) is Hamiltonian in all remaining cases. An
odd flare is a tree obtained from an even star with at least four vertices and centre v by a
single subdivision of an edge. That is, it is obtained by deleting an edge vw, adding a new
vertex z, and adding the edges vz and zw. The vertex v is (still) called the centre of the
odd flare.
Lemma 5.3. Let T be a tree with n ≥ 6 vertices. If T is neither a star nor an odd flare,
then there exist leaves v and w such that d(v, w) ≥ 3 and T − {v, w} is not an odd star.
Proof. Let P = x0x1 . . . xp be a longest path in T . Since P is a longest path, x0 and xp
are leaves of T .
Suppose first that n is even. Since T is not a star, p ≥ 3. Let v = x0 and w = xp. Then
the distance d(v, w) ≥ 3 and T − {v, w} is not an odd star (since n is even).
Now suppose that n is odd. If p ≥ 5, the result follows on letting v = x0 and w = xp.
Suppose that p = 4, so that P = x0x1x2x3x4. If the degree d(x1) > 2 or d(x3) > 2 then
the result follows as above with v = x0 and w = x4. Otherwise, since n ≥ 6, it must be
that d(x2) > 2. Let Q = x2y1y2 . . . yq be a longest path starting at x2 that contains no
other vertex of P . As above, since Q is a longest path, the vertex yq is a leaf of T . The
result follows by letting v = x0 and w = yq .
Finally, suppose that n is odd and p = 3, so that P = x0x1x2x3. Since T is not an
odd flare and n ≥ 6 is odd, there exist at least three other vertices, of which at least one is
adjacent to x1 and at least one is adjacent to x2. Let v = x0 and w = x3. Then d(v, w) ≥ 3
and T − {v, w} is not an odd star.
Theorem 5.4. If T is an odd flare, then G3(T ) is Hamiltonian.
Proof. The proof is by induction on t, where |V (T )| = 2t + 1, t ≥ 2. We prove the
stronger statement that there is a Hamilton cycle in which any colour assigned to the centre
of the flare remains constant for an even number of consecutive 3-colourings (vertices of
G3(T )). This stronger statement is true for the Gray code of 3-colourings for the unique
odd flare with five vertices shown in Figure 2. Suppose it holds for all odd flares on 2t− 1
vertices for some t ≥ 3, and let T be an odd flare on 2t+ 1 vertices.
Let c be the centre of the odd flare T , and v and w be leaves adjacent to c. Then the tree
T ′ = T −{v, w} is an odd flare with 2t− 1 vertices and the same centre. By the induction
hypothesis, G3(T ′) has a Hamilton cycle C = f0, f1, . . . , fN−1, f0 in which any colour
assigned to c remains constant for an even number of consecutive 3-colourings. For the
remainder of this proof, subscripts are to be interpreted modulo N .
For i = 0, 1, . . . , N − 1, let Fi be the set of 3-colourings of T that agree with fi on
V (T ′). Since v andw are leaves, each set Fi contains four 3-colourings of T . Two different
vertices c1, c2 ∈ V (G3(T )) belonging to Fi are adjacent if and only if c1(v) = c2(v)
or c1(w) = c2(w). Thus, the subgraph of G3(T ) induced by Fi is a 4-cycle. Denote
this 4-cycle by xi,1, xi,2, xi,3, xi,4, xi,1 where the colourings xi,1 and xi,3 are such that
xi,1(v) = xi,1(w) and xi,3(v) = xi,3(w).
K. Choo and G. MacGillivray: Gray code numbers for graphs 133
12223 23332 21331 13331 32221 31212
12323 23312 21131 13321 31221 31112
12321 23313 21132 13323 31223 31113
12331 23113 21112 13223 31213 31123
12332 21113 23112 13221 32213 31121
12232 21313 23132 13231 32113 32121
13232 21312 23131 12231 32112 32123
13332 21332 23331 12221 32212 32223
Figure 2: A Gray code of 3-colourings for a flare with five vertices.
Suppose fi(c) = fi+1(c). Then every colouring in Fi has a neighbour in Fi+1, namely
the colouring that agrees with it on v and w. Thus, in this case, [Fi, Fi+1] consists of four
vertex disjoint edges.
Suppose fi(c) 6= fi+1(c). Let α = {1, 2, 3} − {fi(c), fi+1(c)}. Then the colouring in
Fi that assigns α to both v and w has a neighbour in Fi+1, as above, and no other colouring
in Fi has a neighbour in Fi+1.
The colourings fj , for which fj(c) 6= fj+1(c), partition C into paths, each having an
even number of 3-colourings of T ′. For each such path fi, fi+1, . . . , fi+2q−1, letHi,i+2q−1
be the subgraph of G3(T ) induced by Fi ∪ Fi+1 ∪ · · · ∪ Fi+2q−1, and call Hi,i+2q−1 a
segment. Note that the positive integer q may differ between segments.
It is enough to prove that for any vertices a ∈ {xi,1, xi,3}, b ∈ {xi+2q−1,1, xi+2q−1,3}
the graph Hi,i+2q−1 has a Hamilton path starting at a and ending at b. By choosing a
and b to have neighbours in Fi−1 and Fi+2q , respectively, we can obtain a Hamilton cycle
in G3(T ) by concatenating the Hamilton paths through the segments that arise from the
partition of C. Without loss of generality assume i = 1, so that H1,2q is the subgraph of
G3(T ) induced by F1 ∪ F2 ∪ · · · ∪ F2q . By the argument above, for r = 1, 2, . . . , 2q we
have [Fr, Fr+1] = {xr,1xr+1,1, xr,2xr+1,2, xr,3xr+1,3, xr,4xr+1,4}. Let Pr(w, z) denote a
Hamilton path from w to z in the 4-cycle induced by Fr. A Hamilton path in H1,2q starting
at a and ending at b is P1(a, x1,2), P2(x2,2, x2,1), P3(x3,1, x3,2), . . . , P2q(x2q,2, b).
Since the number of vertices in each segment is a multiple of four in the Hamilton cycle
constructed above, the number of consecutive 3-colourings in which any colour assigned
to the centre of the flare remains constant is a multiple of four. The result now follows by
induction.
Theorem 5.5. Let T be a tree which is not an odd star. Then G3(T ) is Hamiltonian.
Proof. The proof is by induction on n = |V (T )|. Suppose n ≤ 5. If T is a star with an
even number of vertices, then G3(T ) is Hamiltonian by Theorem 5.2. If T is an odd flare,
134 Ars Math. Contemp. 4 (2011) 125–139
then G3(T ) is Hamiltonian by Theorem 5.4. Otherwise, T is isomorphic to P4 or P5. Gray
codes for 3-colourings of these trees are shown in Figure 3.
Suppose for some n ≥ 6 that if T ′ is a tree on n − 1 or fewer vertices which is not an
odd star, thenG3(T ′) is Hamiltonian. Let T be a tree on n vertices which is not an odd star.
If T is an odd flare or a star with an even number of vertices, then the result follows from
Theorem 5.4 or Theorem 5.2, respectively. Otherwise, by Lemma 5.3, there exist leaves v
and w such that d(v, w) ≥ 3 and T ′ = T − {v, w} is not an odd star. By the induction
hypothesis, G3(T ′) has a Hamilton cycle f0, f1, . . . , fN−1, f0. For the remainder of the
proof, subscripts are to be interpreted modulo N .
For i = 0, 1, . . . , N − 1, let Fi be the set of 3-colourings of T that agree with fi on
V (T ′). Since v andw are leaves, each set Fi contains four 3-colourings of T . Two different
vertices c1, c2 ∈ V (G3(T )) belonging to Fi are adjacent if and only if c1(v) = c2(v) or
c1(w) = c2(w). Thus, the subgraph of G3(T ) induced by Fi is a 4-cycle.
Let a and b be the unique neighbours of v and w in T , respectively. Then a 6= b
since d(v, w) ≥ 3. If fi(a) = fi+1(a) and fi(b) = fi+1(b), then every colouring in Fi
has a neighbour in Fi+1, namely the colouring that agrees with it on v and w. Thus, in
this case, [Fi, Fi+1] consists of four vertex disjoint edges. Suppose fi(a) = fi+1(a) and
fi(b) 6= fi+1(b). Let α = {1, 2, 3} − {fi(b), fi+1(b)}. Then the two colourings in Fi that
assign α to w each have a neighbour in Fi+1, as above. Futhermore, the subgraph induced
by these four vertices is a 4-cycle. The case where fi(a) 6= fi+1(a) and fi(b) = fi+1(b)
is similar and also leads to two vertex disjoint edges that join adjacent vertices in Fi to
adjacent vertices of Fi+1.
We claim that if [Fi−1, Fi] and [Fi, Fi+1] each consist of two vertex disjoint edges,
then these edges are incident with at least three vertices of Fi. By the argument above,
{fi−1(a), fi−1(b)} 6={fi(a), fi(b)}, and {fi(a), fi(b)} 6={fi+1(a), fi+1(b)}. The colour-
ings fi−1, fi and fi+1 can not assign three different colours to a, otherwise one of these
colourings assigns the same colour to a as to one of its neighbours. Similarly, these
colourings can not assign three different colours to b. Since fi−1 6= fi+1, it follows that
fi−1(a) 6= fi+1(a) and fi−1(b) 6= fi+1(b). Without loss of generality fi−1(a) 6= fi(a)
and fi(b) 6= fi+1(b). The two edges in [Fi−1, Fi] are incident with colourings in Fi
that assign the unique colour α ∈ {1, 2, 3} − {fi−1(a), fi(a)} to v. Similarly, the two
edges in [Fi, Fi+1] are incident with vertices in Fi that assign the unique colour β ∈
{1, 2, 3} − {fi(b), fi+1(b)} to w. Since only one colouring in Fi assigns α to v and β
to w, the proof of the claim is complete.
It may be assumed without loss of generality that |[F0, F1]| = 2. We now define vertices
si, s
′
i, ti, t
′
i ∈ Fi which will be used to construct a Hamilton cycle in G3(T ). The vertices
s0, s
′
0, t0, t
′
0, s1, t1 are defined first.
• The vertices s′0, t′0, s1 and t1 are chosen so that [F0, F1] = {s′0s1, t′0t1}. (The vertex
s1 is adjacent to t1 because G3(T ) contains the 4-cycle s′0s1t1t
′
0s
′
0.)
• The vertices s0 and t0 are chosen so that the 4-cycle s0, s′0, t′0, t0, s0 is the subgraph
of G3(T ) induced by F0.
Note that s′0t
′
0, s0t0 ∈ E(G3(T )).
Suppose that the vertices si, s′i, ti, t
′
i ∈ Fi have been defined for all 0 ≤ i < k, that sk
and tk have also been defined, and further, that
• {s′k−1sk, t′k−1tk} ⊆ [Fk−1Fk];
K. Choo and G. MacGillivray: Gray code numbers for graphs 135
P4 P5
2121 3232 1313 12123 31212 21213 32121 32132 31232
2123 3231 1312 12323 31312 21313 32321 12132 21232
3123 1231 2312 12313 21312 21323 12321 13132 23232
3121 1232 2313 12312 21212 21321 12121 13232 23132
3131 1212 2323 32312 23212 31321 13121 13231 23131
2131 3212 1323 32313 13212 31323 13131 23231 23121
2132 3213 1321 31313 13213 32323 12131 21231 23123
3132 1213 2321 31213 23213 32123 32131 31231 13123
Figure 3: Gray codes of 3-colourings for P4 and P5.
• sk is adjacent to tk;
• the vertices s′k and t′k are distinct;
• the vertices sk, s′k, t′k and tk occur in this order along the path of length three from
sk to tk (both sk = s′k and tk = t
′
k are possible); and
• if |[Fk, Fk+1]| = 2, then sk or tk has no neighbours in Fk+1 (or neither do).
There are then three cases to consider.
• k = N − 1.
Define s′N−1 and t
′
N−1 so that the 4-cycle sN−1, s
′
N−1, t
′
N−1, tN−1, sN−1 is the
subgraph of G3(T ) induced by FN−1.
• k < N − 1 and |[Fk, Fk+1]| = 2.
Let R be the unique (sk, tk)-path of length three in the subgraph of G3(T ) induced
by Fk. Define s′k and t
′
k such that [Fk, Fk+1] = {s′ksk+1, t′ktk+1} and s′k precedes
t′k on R.
• k < N − 1 and |[Fk, Fk+1]| = 4.
Let R be the unique (sk, tk)-path of length three in the subgraph of G3(T ) induced
by Fk. Define s′k and t
′
k to be adjacent vertices on R such that s
′
k precedes t
′
k and,
if k < N − 2 and |[Fk+1, Fk+2]| = 2, then the neighbours of s′k and t′k in Fk+1 are
not both incident with an edge in [Fk+1, Fk+2]. (This is always possible as there are
three choices for the pair of vertices s′k and t
′
k.) Then, define sk+1 and tk+1 so that
{s′ksk+1, t′ktk+1} ⊆ [Fk, Fk+1].
For i = 0, 1, . . . , N − 1, we now define paths Pi and Qi in the subgraph of G3(T )
induced by Fi, and then use them to construct a Hamilton cycle in G3(T ). The path Pi is
the unique (si, s′i)-path (perhaps of length zero) that does not include ti. The path Qi is the
unique (t′i, ti)-path (perhaps of length zero) that does not include si. Then, the sequence
P0, P1, . . . , PN−1, QN−1, QN−2, . . . , Q0, s0 is a Hamilton cycle in G3(T ).
The result now follows by induction.
Corollary 5.6. Let T be a tree. If T is an odd star with at least three vertices, then
k0(T ) = 4. Otherwise, k0(T ) = 3.
136 Ars Math. Contemp. 4 (2011) 125–139
6 The Gray code number of cycles
In this section we prove that k0(Cn) = 4 for all integers n ≥ 3. We assume throughout
this section that the n-cycle Cn has vertex set V (Cn) = {v1, v2, . . . , vn} and edge set
E(Cn) = {vivi+1 : 1 ≤ i < n} ∪ {vnv1}.
Theorem 6.1. For any integer n ≥ 3, k0(Cn) ≥ 4.
Proof. For n ≥ 3, the graph G3(Cn) is connected only if n = 4 [4]. It remains to show
that G3(C4) is not Hamiltonian. The 3-colourings 1213 and 1312 both have degree two in
G3(C4). Both of them are adjacent to 1212 and 1313. Since 1212, 1213, 1313, 1312, 1212
is not a Hamilton cycle, the graph G3(C4) is not Hamiltonian.
X1: 21231 31231 31232 31212 31312 32312 12312 12313 12323 12123
13123 23123 23121 23131 23231
X2: 12132 13132 13232 13212 13213 23213 21213 21313 21323 21321
31321 32321 32121 32131 32132
Figure 4: The two disjoint 15-cycles X1 and X2 that comprise G3(C5).
For any n ≥ 3, the colouring number col(Cn) = 3. Thus, by Theorems 3.4 and 6.1, we
have that 4 ≤ k0(Cn) ≤ 5. Since C3 = K3, we know from Theorem 4.1 that k0(C3) = 4.
We now show that k0(Cn) = 4 for all n ≥ 3.
Theorem 6.2. For any integer n ≥ 3, the graph G4(Cn) is Hamiltonian.
Proof. By Theorem 4.1, we may assume n ≥ 4. In what follows, we use the four colours
a, b, c, d. Let Pn−3 be the path on n − 3 vertices induced by {v1, v2, . . . , vn−3}. By
Corollary 5.6 the graph G4(Pn−3) is Hamiltonian. Let f0, f1, . . . , fN−1, f0 be a Hamilton
cycle in G4(Pn−3). For i = 0, 1, 2, . . . , N − 1, let Fi be the set of 4-colourings of Cn that
agree with fi on V (Pn−3).
Suppose fi(v1) = fi(vn−3). Then fi can be extended to a colouring of Cn in 21 ways,
so |Fi| = 21. The subgraph of G4(Cn) induced by Fi does not depend on the colour
assigned to v1 and vn−3, and is isomorphic to the graph H1 shown in Figure 5. The vertex
labels are the possible colourings of vn−2vn−1vn (in one-line notation) in the case that
fi(v1) = fi(vn−3) = c.
By checking all possibilities, it can be seen that the graph H1 is Hamilton connected.
However, we sketch a proof of this fact. Referring to Figure 5, let A,B, and D be the
subgraphs of H1 induced by the vertices whose labels start with a, b, and d, respectively.
Then A,B and D are isomorphic. Further, there is an automorphism of H1 that send V (A)
to V (B), V (B) to V (D), and V (D) to V (A). By inspection, the graph A has a Hamilton
path joining any pair of different vertices except those labelled {aba, acd} and {ada, acb}.
Thus, the graph B has a Hamilton path joining any pair of different vertices except those
labelled {bdb, bca} and {bab, bcd}, and the graph D has a Hamilton path joining any pair
K. Choo and G. MacGillivray: Gray code numbers for graphs 137
of different vertices except those labelled {dad, dcb} and {dbd, dca}. Hamilton paths in
A,B andD can be concatenated to form Hamilton paths between any given pair of vertices
in H1.
Otherwise, fi(v1) 6= fi(vn−3). In this case, fi can be extended to a colouring of Cn
in 20 ways, so |Fi| = 20. As above, the subgraph of G4(Cn) induced by Fi does not
depend on the colours assigned to v1 and vn−3, and is isomorphic to the graph H2 shown
in Figure 6. The vertex labels are the possible colourings of vn−2vn−1vn (in one-line
notation) in the case that fi(v1) = fi(vn−3) = c.
By checking all possibilities, it can be seen that the graph H2 is Hamilton connected.
However, we sketch a proof of this fact. Referring to Figure 6, letX and Y be the subgraphs
of H2 induced by the vertices labelled {bcb, bcd, bca, acb, acd, aca} and {bdb, cdb, adb,
bda, cda, ada}, respectively. Then the graphs X and Y are isomorphic to the Cartesian
product of K2 and C3, and hence are Hamilton connected. Further, there is an automor-
phism of H2 that sends V (X) to V (Y ), and V (Y ) to V (X). One can use appropriate
Hamilton paths in X and Y as the basic building blocks towards Hamilton paths between
any given two vertices of H2.
Thus, G4(Cn) is a C-graph. We complete the proof by showing that the hypotheses of
Corollary 3.3 are satisfied.
Suppose |Fi| = |Fi+1| (here, and for the remainder of the proof subscripts are to be
interpreted modulo N ). If fi(v1) = fi+1(v1) and fi(vn−3) = fi+1(vn−3), then each
vertex in Fi has a neighbour in Fi+1 corresponding to the 4-colouring in Fi+1 that assigns
the same colours to vn−2, vn−1, and vn. Hence, in this case [Fi, Fi+1] contains at least
20 vertex disjoint edges. If fi and fi+1 differ in colour at one of v1 or vn−3, without
loss of generality say v1, then the 4-colourings in Fi which assign fi+1(v1) to vn have no
neighbours in Fi+1. In this case [Fi, Fi+1] contains 13 vertex disjoint edges.
Suppose |Fi| 6= |Fi+1|. By symmetry we can assume |Fi| = 20 and |Fi+1| = 21.
We may also assume without loss of generality that fi(v1) = fi+1(v1) and fi(vn−3) 6=
fi+1(vn−3). The colouring fi+1 must assign colour fi+1(v1) to vn−3 in order that it assign
the same colour to v1 and vn−3. Since fi+1(v1) = fi(v1), this colour is not assigned to vn
by any 4-colouring in Fi∪Fi+1. In addition, the 4-colourings in Fi which assign the colour
of fi+1(vn−3) to vn−2 have no neighbours in Fi+1. For each of the remaining 4-colourings
in Fi there is a 4-colouring in Fi+1 that assigns the same colours to vn−2, vn−1, and vn.
That is, [Fi, Fi+1] contains 14 vertex disjoint edges.
By Corollary 3.3, the graph G4(Cn) is Hamiltonian.
Corollary 6.3. For all n ≥ 3, we have k0(Cn) = 4.
138 Ars Math. Contemp. 4 (2011) 125–139
aca
aba ada
abd
bab
dab bad
bda
bdb
bca
bcddcb
acbacd
dca
bcbdcd
dba
dbd
dad
adb
Figure 5: H1.
Figure 6: H2.
K. Choo and G. MacGillivray: Gray code numbers for graphs 139
References
[1] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Elsevier Publishing, New
York, 1976.
[2] P. Bonsma, L. Cereceda, J. van den Heuvel and M. Johnson, Finding Paths between Graph
Colourings: Computational Complexity and Possible Distances, Electronic Notes in Discrete
Math. 29 (2007), 463–469.
[3] L. Cereceda, J. van den Heuvel and M. Johnson, Finding Paths Between 3-Colourings, CDAM
Research Report LSE CDAM-2007-31, to appear in J. Graph Theory.
[4] L. Cereceda, J. van den Heuvel and M. Johnson, Connectedness of the graph of vertex colour-
ings, Discrete Math. 308 (2008), 913–919.
[5] L. Cereceda, J. van den Heuvel and M. Johnson, Mixing 3-colourings in bipartite graphs, Eu-
ropean J. Combin 30 (2009), 1593–1606.
[6] S. J. Curran and J. A. Gallian, Hamiltonian cycles and paths in Cayley graphs and digraphs –
A survey, Discrete Math. 156 (1996), 1–18.
[7] M. Dyer, A. D. Flaxman, A. Frieze and E. Vigoda, Randomly coloring sparse random graphs
with fewer colors than the maximum degree, Random Struct. Algor. 29 (2006), 450–465.
[8] T. R. Jensen, B. Toft, Graph Coloring Problems, John Wiley Sons, Inc., New York, 1995.
[9] M. Jerrum, A very simple algorithm for estimating the number of k-colourings of a low-degree
graph, Random Struct. Algor. 7 (1995), 157–165.
[10] M. Jerrum, Counting, Sampling and Integrating: Algorithms and Complexity, Birkhäuser,
Basel, 2003.
[11] V. L. Kompel’makher and V. A. Liskovets, Sequential generation of arrangements by means
of a basis of transpositions, Kibernetica 3 (1975), 17–21, in Russian, English translation in
Cybern. Syst. Anal. 11 (1975), 362–366.
[12] F. Ruskey, Combinatorial Generation, manuscript, version 1h, 1996.
[13] C. Savage, A survey of combinatorial Gray codes, SIAM Review 39 (1997), 605–629.
[14] C. Savage and P. Winkler, Monotone Gray codes and the middle levels problem, J. Combin.
Theory Ser. A 70 (1995), 230–248.
[15] P. J. Slater, Generating all permutations by graphical transpositions, Ars Combin. 5 (1978),
219–225.
[16] H. S. Wilf, Combinatorial Algorithms: An Update, SIAM Philadelphia, 1989.