According to Smith Theorem:  if a cubic graph has a hamilton circuit then it must have a second one. SMITH : Given a Hamilton circuit in a 3-regular graph, find a second Hamilton circuit. It is known that SMITH is in PPA, but it is unknown whether is it PPA-complete. 

More details of this problem can be found here: https://kintali.wordpress.com/tag/ppa-completeness/

According to Tutte[1]: Every edge of a cubic graph lies on an even number of Hamilton cycles.Consequently a cubic hamiltonian graph has at least three Hamilton cycles.


My question: Given one Hamilton Cycle, what is the complexity of finding a third Hamilton Cycle in cubic graph? 

For the problem that given one Hamilton Cycle in a cubic graph, to find the second one, Thomason[2] gave an exponential time algorithm, which can be converted into a PPA-membership proof of SMITH. How about if given one Hamilton Cycle in a cubic graph, to find the THIRD one? If we still use the algorithm of Thomason, it is no better than exponential time, and it is at least in PPA. But can we do better? 


[1] W.T. Tutte, On Hamiltonian circuits, J. London Math. Soc., 21 (1946), 98–101.

[2] A. G. Thomason, Hamiltonian cycles and uniquely edge colourable graphs, Ann. Discrete. Math. 3 (1978), 259-268.