# 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?

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

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