Can an Euler path of a complete directed graph be partitioned into Hamilton paths

graph theory

A complete directed graph with n nodes has n(n-1) edges. Since each node has in-degree = out-degree = (n-1) and the graph is strongly connected, there must exist an Euler path. Since there are n nodes, a Hamilton path must have length (n-1). Now, the question is: For which values of n can this Euler path of length n(n-1) be partitioned into n distinct Hamilton paths of length (n-1)?

This obviously works for n = 2: The Euler path of length 2(2-1) = 2 is "0 -> 1 -> 0", and it can be partitioned into 2 Hamilton paths of length (2-1) = 1: "0 -> 1" and "1 -> 0".

I didn't find any combination that works for n = 3 or n = 4.

Does there even exist a larger n for which this works? I am completely stuck, since I relied on brute force so far. Is there a smart criterion or algorithm for this?

EDIT:
A "partitioning" in this context means that each Hamiltonian path consists of consecutive edges of the Euler path, such that each edge of the Euler path is contained in exactly one Hamiltonian path, and all the Hamiltonian paths can be appended to each other in such a way that the result is the original Euler path.

Best Answer

I am completely stuck, since I relied on brute force so far. Is there a smart criterion or algorithm for this?

There's brute force and brute force.

There's an obvious bijection between Hamiltonian paths and permutations of the vertices.

Without loss of generality, the first Hamiltonian path can correspond to the identity permutation.

Then a simple search, where we merely track the unvisited vertices in the current Hamiltonian path and the edges which have already been used, quickly (in a matter of a few seconds) finds solutions for $n \in \{2,6,7,8,9\}$:

0, 1, 0

0, 1, 2, 3, 4, 5, 0, 2, 1, 4, 3, 0, 4, 1, 5, 2, 4, 0, 3, 5, 1, 3, 2, 0, 5, 4, 2, 5, 3, 1, 0

0, 1, 2, 3, 4, 5, 6, 0, 2, 1, 3, 5, 4, 0, 3, 1, 6, 2, 5, 0, 4, 3, 2, 6, 1, 5, 3, 0, 6, 4, 2, 0, 5, 1, 4, 6, 3, 6, 5, 2, 4, 1, 0

0, 1, 2, 3, 4, 5, 6, 7, 0, 2, 1, 3, 5, 4, 6, 0, 3, 1, 4, 2, 7, 5, 0, 4, 1, 6, 3, 7, 2, 0, 5, 3, 6, 1, 7, 4, 3, 0, 6, 2, 5, 7, 1, 5, 2, 6, 4, 0, 7, 3, 2, 4, 7, 6, 5, 1, 0

0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 2, 1, 3, 5, 4, 7, 6, 0, 3, 1, 4, 2, 5, 8, 7, 0, 4, 1, 5, 2, 6, 8, 3, 0, 5, 1, 7, 2, 8, 6, 4, 0, 6, 1, 8, 5, 7, 3, 2, 4, 6, 3, 8, 1, 0, 7, 5, 0, 8, 4, 3, 6, 2, 7, 1, 6, 5, 3, 7, 4, 8, 2, 0

and excludes solutions for $n \in \{3,4,5\}$. My program is still searching for $n=10$ after 5 minutes.

Related Question