How many Hamiltonian cycles are there in a complete graph that must contain certain edges?

Question

Consider a complete graph $G$ that has $n \geq 4$ vertices.

Each vertex in this graph is indexed $[n]=\{1,2,3, \dots n\}$

In this context, a Hamiltonian cycle is defined solely by the collection of edges it contains. We don't need to consider the cycle's orientation or starting point.

Question: How many Hamiltonian cycles in graph $G$ contain both the edges $\{1,2\}$ and $\{3,4\}$?

---

For the sake of this exercise, let's pretend we have a complete graph made of 5 vertices.

Index: $[n] = {1,2,3,4,5}$

Since the graph must contain edges $\{1,2\}$ and $\{3,4\}$, I treat them as individual vertices. Which means I only have three vertices:

$\{1,2\}, \{3,4\}, 5$

If I'm correct, this graph should have 4 Hamiltonian cycles. However, I can't get this number no matter how I try.

• $3! = 6$ (Wrong)
• $3!/2n = 1$ (Wrong)

I've been told that the edges $\{1,2\}$ and $\{3,4\}$ are directional but I'm not sure how to account for this level of complexity.

Answer 1

The question can be interpreted as asking how many ways there are to construct a Hamiltonian cycle under these constraints. Since we know $\{1,2\}$ must be in the cycle, it seems reasonable to assume that we start at vertex $1$ and the first edge traversed is $\{1,2\}$. From here, the rest of the cycle is given by a permutation of the remaining vertices $\{3,4, \dots, n\}$ under the constraint that 3 and 4 have to be consecutive. Similar to your idea of treating $\{3,4\}$ as a single vertex, we can permute these $n-3$ objects ($n$ vertices, minus the two we already used and treating 3 and 4 as a single unit) in $(n-3)!$ ways. Then there are 2 orientations for the $\{3,4\}$ edge, so we multiply to get a total of $2(n-3)!$ Hamiltonian cycles.

In your example, we do indeed get $2(5-3)! = 4$ such Hamiltonian cycles.

As a side note, you can generalize this result. If the $k$ "fixed edges" comprise $p$ vertex-disjoint paths, then the number of Hamiltonian cycles should be $2^{p-1}(n-k-1)!$. There's $p-1$ paths to orient, $n - k - p$ vertices which are still on their own, and $p-1$ paths to place as a single unit somewhere in the permutation (so we permute $n-k-1$ objects in this step).