Number of Hamiltonian cycles in complete graph Kn with constraints 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
 A: 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:

*

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

*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:

*

*Start with the $\frac12(n-1)!$ cycles we have in total.

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

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

*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.
A: 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)! 
