[Math] How many Hamiltonian cycles are there in a complete graph that must contain certain edges

graph theoryhamiltonian-path

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.

Best Answer

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

Related Solutions

[Math] Number of Hamiltonian Paths on a (in)complete graph

This looks a lot like the way you determine the chromatic polynomial, but in a some sense "reversed": you know the values of your most "complicated" graphs instead of iterating until you have reached the simplest ones.

Consider one edge $e$, then the number of hamiltonian cycles in $G$ equals the number of cycles in $G-e$ (those that do NOT use the edge) plus the number of cycles in $G/e$ (those that DO use the edge).

This can be transformed into a recursive algorithm: you know the values for the complete graphs, and all other intermediate values you require are the result of removing a smaller list of edges from a smaller complete graph.

However this will not perform at all on anything but the smallest examples and it certainly will not give you anything like a closed formula for the number of hamiltonian cycles. I am not at all sure if this is an acceptable solution.

EDITED AFTER REQUEST FOR DETAILS:

Consider next pseudocode.

int function h(int n, List l)
{
  if (l is empty) { return number of hamilton cycles in K_n }
  create new list lNew;
  return h(n, l minus last element) - h(n - 1, lNew);
}

This function $h$ calculates the number of hamiltonian cycles in $K_n$ when the edges of the list $l$ are missing. You use the recurrence $h(G-e)=h(G)-h(G/e)$, so you repeatedly put one edge back into the graph until you have put back everything. You have to decide on how to represent the edges on the list. One option is to represent each edge on $l$ simply as a pair of numbers in the range $1..n$. The only tricky part is the creation of the list $lNew$. You cannot just copy its elements from the list $l$, since they refer to edges of a $K_{n-1}$ after the recursion, so depending on the edge you are removing you need to manipulate the list elements.

I have no clue how this will perform with the numbers you mention. The most important thing will be that the list of edges is not too long, since that will determine the depth of the recursion. Be sure to use some kind of 'big integer' arithmetic or find other ways to avoid large numbers.

[Math] Number of Hamiltonian Cycles in Kn,n

Pick any vertex, for simplicity let’s call it $l_1$. It doesn’t matter which vertex we pick since each Hamiltonian cycle is indifferent to the order of its vertices. $l_1$ has $n$ choices for a $r_i$ vertex to connect to next. This $r_i$ vertex has $n-1$ choices for a vertex $l_i$ to connect to next. Continuing in this fashion we see there are $$n!(n-1)! \text{ Oriented Hamiltonian cycles}$$ We need to divide by two because we don’t care which direction we take to travel a Hamiltonian cycle. $$\frac{1}{2}n!(n-1)!\text{ Hamiltonian cycles}$$

Then the number of these Hamiltonian cycles that also contain both those edges is given by $$\frac{1}{2}n!(n-1)!\frac{1}{{n\choose 2}}$$ $$(n-1)!(n-2)!$$ because $r_1$ has to choose $2$ out of $n$ vertices to connect to, but it must connect to $l_1$ and $l_2$ in order to include those edges.

For the second question first consider the graph $K_{n-2,n-2}$ with left and right vertices $\{l_3,...,l_n\}$ and $\{r_3,...,r_n\}$. This graph has $\frac{1}{2}(n-2)!(n-3)!$ Hamiltonian cycles. If we wanted to insert the edge $\{l_2,r_2\}$ into any of these cycles to get a new one, there are $2(n-2)$ edges to do so. If we wanted to in turn insert the edge $\{l_1,r_1\}$ into this cycle to get a new one, there would be $2(n-2)+1=2n-3$ edges to insert this new one in because we just added an edge. Thus, there are $$2(n-2)!(n-2)!(2n-3)$$ Hamiltonian cycles of $K_{n,n}$ that include those two edges.

Best Answer

Related Solutions

[Math] Number of Hamiltonian Paths on a (in)complete graph

[Math] Number of Hamiltonian Cycles in Kn,n

Related Question