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
