# 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 identi ed 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

## 1 Answer

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