Hardness of finding exactly two Hamiltonian cycles in a graph

Question

$\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?

Answer 1

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.