# How many Hamiltonian cycles are there in a complete graph if we discount the cycle's orientation or starting point?

Consider a complete graph G with n vertices.

Each vertex is indexed by [n] = {1,2,3...n} where n >= 4.

In this case, a Hamiltonian cycle is determined only by the collection of edges it contains, and we do not need to consider its orientation or starting point.

Question:

1. How many Hamiltonian cycles are there in G?
2. How many Hamiltonian cycles in G contains the edge {1,2}?
3. How many Hamiltonian cycles in G contains the edge {1,2} and {2,3}?
4. How many Hamiltonian cycles in G contains the edge {1,2} and {3,4}?
5. Suppose that M is a set of k <= (n/2) edges, in which no two edges in M share a vertex. How many Hamiltonian cycles contain all edges in M? Give answer in terms of k and n
6. How many Hamiltonian cycles in G do not contain the edge {1,2}, {2,3} and {3,4}?

The question really clusters into two parts.

PART 1: How do I discount "orientation" and "starting point"?

This has to do with 1, 2, 3, 4, and 6.

I can calculate the combinations of edges there can be, but that's not what they're asking. They only want the combinations that form a Hamiltonian cycle.

Additionally, I don't see how you can just know whether a Hamiltonian cycle has crossed through a certain edge.

The more I think about it, the more I feel this is about combinatorial numbers as opposed to graph theory. Are they trying to trick me?

PART 2: How many cycles contain a set of edges that do not share a vertex.

This has to do with question 5, specifically.

My first response is "none..."?

If the graph is a complete graph, then all edges share a vertex at some point right? In that case, M seems to be an empty set and there are no Hamiltonian cycles that cover it. But that doesn't feel right at all...

Hint: if we do consider starting point and orientation, then the number of Hamiltonian cycles is the number of ways that we can order $$[n]$$, i.e. the number of permutations. If you know the order in which to visit the vertices, this tells you exactly the cycle. Each cycle is then counted $$n$$ times for each possible starting point, and twice for each direction around the cycle.
Hint for part 2: A cycle can contain $$\{ 1,2 \}$$ and $$\{ 3,4 \}$$ if it (for example) also contains edge $$\{ 2,3 \}$$.