Thomasonʹs algorithm for finding a second hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczykʹs graphs Original Research Article

A corollary of Smithʹs Theorem says that if a cubic graph has a hamiltonian circuit through edge e, then there is a second hamiltonian circuit through e. Tutteʹs proof is beautiful but non-constructive. Thomason gave a simple and elegant algorithm to find the second hamiltonian circuit. Krawczyk found a family of graphs on which Thomasonʹs algorithm is exponential. I will give a proof that Thomasonʹs algorithm is exponential on a family of cubic planar graphs, which is a variant of Krawczykʹs family.