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: What is the complexity of finding a third Hamilton Cycle? 


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