Number of Hamiltonian cycles in complete graph Kn with constraints

Question

I am currently working on a exercice which aims to count the number of hamiltonian cycles in a complete graph. Since it is a completely new topic to me, I struggle to think about how to solve the problem. I understand how to count the number of Hamiltonian cycles in a complete graph Kn but my main problem is: what if we have constraints on some particular edges that the Hamiltonian must contain? Here is the exercice with which I'm struggling with

---

Suppose Kn is a complete graph whose vertices are indexed by [n] = {1,2,3,...,n} where n >= 4. In this question, a cycle is identied solely by the collection of edges it contains; there is no particular orientation or starting point associated with a cycle. (Give your answers in terms of n for the following questions.

(a) How many Hamiltonian cycles are there in Kn?

-> My answer : (n-1)!/2. In fact, there is no particular orientation or stationg point, so we can avoid counting the starting point (thus we have n-1)

(b) How many Hamiltonian cycles in Kn contain the edge {1,2}?

-> My answer : since I consider the edge {1,2} as a vertex, the number of HC should be (n-2)!/2

(c) How many Hamiltonian cycles in Kn contain both the edges{1,2} and {2,3}?

-> My Answer : Same reflexion as above, there are (n-3)!/2 hamiltonian cycles

(d) How many Hamiltonian cycles in Kn contain both the edges {1,2} and {3,4}?

-> My question : should I consider {1,2} and {3,4} as proper vertices also?

(e) Suppose that M is a set of k <= n 2 edges in Kn with the property that no two edges in M share a vertex. How many Hamiltonian cycles in Kn contain all the edges in M? Give your answer in terms of n and k.

-> Note : Do you have any hint?

(f) How many Hamiltonian cycles in Kn do not contain any edge from {1,2}, {2,3} and {3,4}?

-> Note : Do you have any hint?

---

Thanks by advance for your help

Answer 1

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)!

Answer 2

There are $\frac{n!}{2n} = \frac12 (n-1)!$ Hamiltonian cycles in $K_n$.

There are many ways to obtain this count, but a generally useful way of thinking is that:

1. For each of the $n!$ permutations of the $n$ vertices, we can get a Hamiltonian cycle by visiting the vertices in order of the permutation, then returning to the start.
2. Each cycle can be obtained from $2n$ different permutations: we can choose $n$ different starting points and $2$ different directions around the cycle.

Actually, $(n-2)!$ of these cycles contain the edge $\{1,2\}$.

We can solve this by contracting edge $\{1,2\}$ to a single vertex, but we must be careful. The result is $K_{n-1}$ with $n-1$ vertices named $\{1,2\}, 3, 4, \dots, n$, but any Hamiltonian cycle in $K_{n-1}$ gives us two cycles in $K_n$. If the cycle in $K_{n-1}$ goes from $v$ to $\{1,2\}$ to $w$, then in $K_n$ it could go from $v$ to $1$ to $2$ to $w$ or from $v$ to $2$ to $1$ to $w$.

Another approach: by deleting edge $\{1,2\}$, we obtain a Hamiltonian path starting at $1$ and ending at $2$, and there are $(n-2)!$ ways to arrange the vertices between them.

Yet a third way: if each of the $\frac12(n-1)!$ Hamiltonian cycles contains $n$ edges, and each of the $\binom n2$ edges of $K_n$ is in $x$ cycles, then $\binom n2 \cdot x = \frac12(n-1)! \cdot n$, because these count the same quantity in two ways: the number of edge-cycle pairs where the edge is on the cycle. Now, solve for $x$.

Similarly, $(n-3)!$ cycles contain both $\{1,2\}$ and $\{2,3\}$.

We can solve this either by contracting $\{1,2,3\}$ to a single vertex (as above), or by counting paths that start at $1$, end at $3$, and visit vertices $4, \dots, n$ in one of $(n-3)!$ orders.

Meanwhile, $2(n-3)!$ cycles contain both $\{1,2\}$ and $\{3,4\}$.

Here, if we contract both edges to vertices, we get $K_{n-2}$ with its $\frac12(n-3)!$ cycles, and each cycle can be expanded to $2^2$ different cycles in $K_n$ (because for each edge, we have two ways to order its endpoints).

This can also be solved using a different method from above. There are $3\binom n4$ unordered pairs of edges $\{a,b\}, \{c,d\}$ where all four endpoints are distinct. Say that each such pair lies on $y$ cycles. Meanwhile, there are $\frac12(n-1)!$ cycles, and from each cycle, we can choose $\frac12 n(n-3)$ unordered pairs of edges with no shared endpoints. Therefore $$ 3\binom n4 \cdot y = \frac12(n-1)! \cdot \frac12 n(n-3) \implies y = 2(n-3)!. $$

There are $2^{k-1}(n-k-1)!$ cycles containing any $k$-edge matching.

This is a generalization of previous parts of the question.

We can contract each edge of the matching to a vertex, leaving us with $K_{n-k}$. This has $\frac12(n-k-1)!$ Hamiltonian cycles. Each cycle can be expanded to a Hamiltonian cycle in $K_n$ in $2^k$ different ways.

To count cycles with none of the edges $\{1,2\}, \{2,3\}, \{3,4\}$, use PIE.

The previous steps have given us almost everything we need to use the principle of inclusion-exclusion:

1. Start with the $\frac12(n-1)!$ cycles we have in total.
2. Subtract $(n-2)!$ for cycles containing $\{1,2\}$, subtract $(n-2)!$ for cycles containing $\{2,3\}$, and subtract $(n-2)!$ for cycles containing $\{3,4\}$.
3. Add back in $(n-3)!$ for cycles containing $\{1,2\}$ and $\{2,3\}$, add $(n-3)!$ for cycles containing $\{2,3\}$ and $\{3,4\}$, and add $2(n-3)!$ for cycles containing $\{1,2\}$ and $\{3,4\}$.
4. By the vertex contraction method, there are $(n-4)!$ cycles containing all three edges, which we subtract.

The final answer we get is $\frac12(n-1)! - 3(n-2)! + 4(n-3)! - (n-4)!$, which doesn't particularly simplify.