# Hardness of finding exactly two Hamiltonian cycles in a graph

$$\newcommand{\nuSwap}{\nu\textsf{-swap}}$$

Two Hamiltonian cycles are different if and only if there is at least one edge they do not share.

Let $$L$$ consist of all graphs with exactly two Hamiltonian cycles. What complexity class does it belong to?

Let us construct an NTM $$M$$ that decides $$L$$ in polynomial time.

Take an NTM $$M_1$$ that recognizes the existence of a Hamiltonian cycle in polynomial time and run it on $$G$$. If $$M_1$$ rejects $$G$$, reject, otherwise use $$M_1$$ to construct the cycle $$P_1$$. Now for each edge $$e_i \in P_1$$ run $$M_1$$ on $$G_i = (V, E \setminus \{ e_i \})$$. If $$M_1$$ never accepts, reject, otherwise find another Hamiltonian cycle $$P_2$$ using $$M_1$$ on any $$i$$ such that $$M_1$$ accepts $$G_i$$. Repeat the same process again but now try every $$e_i \in P_1$$, $$e_j \in P_2$$ on $$G_{ij} = (V, E \setminus \{ e_i, e_j \})$$. If the third Hamiltonian cycle is found, reject, otherwise accept.

Now we can also make $$M'$$ that decides $$\overline{L}$$ in polynomial time. We use $$M_1$$ to see if there is a Hamiltonian cycle - if not, accept, otherwise construct it and use the same process as before to find a second Hamiltonian cycle. If it is not found, then accept, otherwise try to find a third hamiltonian cycle by deleting each pair like before. If the third Hamiltonian cycle was not found, then reject, otherwise accept.

Both $$M$$ and $$M'$$ seem to run in polynomial time as they only use $$M_1$$ but there must be a mistake as this would prove that $$\mathcal{NP} = co \textsf{ -} \mathcal{NP}$$.

Where is my reasoning wrong and how to decide which complexity class does $$L$$ belong to?

Your $$M_1$$ is not a polynomial time NTM unless $$\mathsf{NP} = \mathsf{coNP}$$, I think. In the last step (checking that $$G_{ij}$$ contains no HC), you essentially want to decide the complement of HC, which is $$\mathsf{coNP}$$-complete. This is a bit of a tricky thing about nondeterministic computation: you cannot simply invert answers like you can with deterministic computation.
As for the complexity of your problem: Note that it is the intersection of a $$\mathsf{NP}$$-language (are there at least 2 different HCs) and a $$\mathsf{coNP}$$-language (does any triple of HCs contain the same HC twice?) and hence in $$\mathsf{DP} \subseteq \Delta_2^p$$. I don't see an easy way to convincingly argue that it's not contained in some lower class.