Smith's theorem states that in a cubic graph the number of Hamiltonian cycles containing a given edge is even. Thomason's proof of this theorem yields an algorithm that given one Hamiltonian cycle in such a graph, com- putes another one. We prove an exponential lower bound on the number of steps of Thomason's algorithm.
展开▼
