0
$\begingroup$

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}$

enter image description here

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.

$\endgroup$
  • $\begingroup$ Clearly it depends on which edges must be included. As such, there is no generic universal answer to your question. $\endgroup$ – David G. Stork Nov 30 '18 at 6:28
  • $\begingroup$ @DavidG.Stork Actually, I think you can do slightly better. It should be possible to determine the answer based only on the number of disjoint paths formed by the fixed edges. Since the question explicitly fixes edges $\{1,2\}$ and $\{3,4\}$ it is indeed well-posed. $\endgroup$ – platty Nov 30 '18 at 6:31
  • $\begingroup$ Imagine $n$ is large and you choose your $n$ edges that themselves form a Hamiltonian path. Then the number of such paths is $1$. Suppose instead that you choose $n$ "random" edges. Clearly there will be more than one Hamiltonian paths through that set. So which answer is "right"? $\endgroup$ – David G. Stork Nov 30 '18 at 6:34
  • $\begingroup$ @platty I think so too. Since it is a complete graph it shouldn't matter which vertex gets which index. All we know is that {1,2} and {3,4} are edges that don't share the same vertex. $\endgroup$ – potatoguy Nov 30 '18 at 6:35
  • $\begingroup$ @DavidG.Stork That's not relevant to the question asked though, which is "Question: How many Hamiltonian cycles can there be if the graph must contain the edges $\{1,2\}$ and $\{3,4\}$?" $\endgroup$ – platty Nov 30 '18 at 6:36
2
$\begingroup$

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

$\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.