# Complete graph $K_n$ with $n$ edges in a Hamiltonian cycle removed

Let $$K_n$$ be the complete (undirected) graph on $$n$$ vertices. We know that there are $$\frac{(n-1)!}{2}$$ Hamiltonian cycles in $$K_n$$. Now fix a Hamiltonian cycle and remove all the edges in it from $$K_n$$. How many Hamiltonian cycles are left?

I've been trying my hand at this problem for a while but I'm stuck on how to proceed. There seems to be a brute force principle of inclusion-exclusion approach by first counting how many Hamiltonian cycles pass through a given subset of edges in the removed cycle, but there are just too many cases to consider.

Is there a sleeker method to approach this problem? Perhaps something involving generating functions, if the answer doesn't have a nice simplified closed form?

• oeis.org/A002816 Always good to enumerate the first few cases. Commented Feb 16, 2023 at 0:44
• @EdPegg Thanks! So I guess an exact formula is hopeless...? I'm also still interested in the possibility of a generating function Commented Feb 16, 2023 at 0:50
• The oeis page links to a report in which an exact formula is given. The quantity is called $q_n$ in the report. Commented Feb 16, 2023 at 2:42

For completeness I will post the exact formula, given in page 6 of this report as $$q_n$$, as informed by Gerry in the comments.
$$q_n = \frac{(n-1)!}{2}+ \left( \sum_{1 \leq k < n} (-1)^k \sum_{1 \leq j \leq k} {k-1 \choose j-1} {n-k \choose j} \frac{n-k}{j} \frac{(n-k-1)!}{2} 2^j \right) +(-1)^n$$