In a complete graph with $n$ vertices there are $\frac{n−1}{2}$ edge-disjoint
Hamiltonian cycles if $n$ is an odd number and $n\ge 3$. What if $n$ is an even number?
[Math] Number of edge disjoint Hamiltonian cycles in a complete graph with even number of vertices.
graph theoryhamiltonian-path
Related Solutions
An example of the prism over the Petersen graph decomposing into Hamilton cycles:
A non-example (just to show that it's not always possible):
Here the green edges are a Hamilton cycle, whereas the black edges are not.
These were found via a computer search.
This looks a lot like the way you determine the chromatic polynomial, but in a some sense "reversed": you know the values of your most "complicated" graphs instead of iterating until you have reached the simplest ones.
Consider one edge $e$, then the number of hamiltonian cycles in $G$ equals the number of cycles in $G-e$ (those that do NOT use the edge) plus the number of cycles in $G/e$ (those that DO use the edge).
This can be transformed into a recursive algorithm: you know the values for the complete graphs, and all other intermediate values you require are the result of removing a smaller list of edges from a smaller complete graph.
However this will not perform at all on anything but the smallest examples and it certainly will not give you anything like a closed formula for the number of hamiltonian cycles. I am not at all sure if this is an acceptable solution.
EDITED AFTER REQUEST FOR DETAILS:
Consider next pseudocode.
int function h(int n, List l)
{
if (l is empty) { return number of hamilton cycles in K_n }
create new list lNew;
return h(n, l minus last element) - h(n - 1, lNew);
}
This function $h$ calculates the number of hamiltonian cycles in $K_n$ when the edges of the list $l$ are missing. You use the recurrence $h(G-e)=h(G)-h(G/e)$, so you repeatedly put one edge back into the graph until you have put back everything. You have to decide on how to represent the edges on the list. One option is to represent each edge on $l$ simply as a pair of numbers in the range $1..n$. The only tricky part is the creation of the list $lNew$. You cannot just copy its elements from the list $l$, since they refer to edges of a $K_{n-1}$ after the recursion, so depending on the edge you are removing you need to manipulate the list elements.
I have no clue how this will perform with the numbers you mention. The most important thing will be that the list of edges is not too long, since that will determine the depth of the recursion. Be sure to use some kind of 'big integer' arithmetic or find other ways to avoid large numbers.
Best Answer
Since each Hamiltonian takes away two edges per vertex, an obvious upper bound for the even case is $\frac n2-1$. For the lower bound, use the following construction: If $n=2m+2$, let the vertices be $0,1,2,\ldots,n-2,n-1$. For $d=1,2,\ldots m$, we have a Hamiltonian cycle of all points except $n-1$ by making steps of length $d$ (i.e. there is an edge between $a$ and $a\pm d\bmod {n-1}$. To turn these into Hamiltonians for the full graph, note that for $k=0, 1, \ldots, m-1$ the edge $k\to 2m-k$ belongs to one of thes Hamiltonians, namely the one with step size $d=2k+1$ or $d=2m-2k$, whichever is $\le m$. Replacing this edge with $k\to n-1\to 2m-k$ we get a Hamiltonian cycle for the larger graoh, and all these are edge-disjoint.