Smith's theorem states that in a cubic graph the number of Hamiltonian cycl
es containing a given edge is even. Thomason's proof of this theorem yields
an algorithm that given one Hamiltonian cycle in such a graph, computes an
other one. We prove an exponential lower bound on the number of steps of Th
omason's algorithm. (C) 1999 Academic Press.