0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.