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

Question

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...

Answer 1

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 \}$.

Answer 2

Q(a)-Q(c) is correct, and Q(d) can be seen as {1,2}{2,3}{3,4} - {2,3} which is 2(n-2)!-(n-3)! (e) can brake into (12)(34)(56)789 and applying counting,answer=(n)!(n-k-1)!/(2n) (f)Obviously Answer=1/2(n-1)!-(n-3)!