Edges of the complete graph on $2n$ vertices can be colored with $2n-1$ colors such that only edges of different colors intersect.


*Can this always be done such that for every pair of different colors the set of edges of these two colors form a unique cycle?*


Reformulation: Are there $2n-1$ fixed-point-free involutions in the symmetric group $S\_{2n}$ such that the product of two (different) such involutions has always two cycles of length $n$?


(I suspect that the answer is well-known to specialists : This seems a fairly natural question.)


The answer is YES if $2n-1$ is a prime number. Indeed, dropping the condition that any maximal set of edges of two colors defines a hamiltonian cycle, there is an easy solution due to Soifer, see <https://en.wikipedia.org/wiki/Edge_coloring> which can be described as follows : Consider the set $S=\lbrace 0,1,\ldots,2n-2,\infty\rbrace$. For $a$ in $\lbrace 0,\ldots,2n-2\rbrace$ consider the
fixed point-free involution $\sigma\_a$ defined by $x\longmapsto 2a-x$ if $x\not\in \lbrace a,\infty\rbrace$ extended by $\sigma\_a(a)=\infty$, $\sigma\_a(\infty)=a$. A symmetry argument shows that it is enough to prove the claim for all pairs of colors $\lbrace \sigma\_0,\sigma\_a\rbrace$ for finite non-zero $a$. The composition of these two involutions is then essentially addition (or subtraction) of $2a$ modulo $2n-1$. We get therefore Hamiltonian cycles for all choices of $a$ if $2n-1$ is prime. We have however a problem if $a$ divides $2n-1$.



Hamiltonian edge colouring of complete graphs with even numbers of vertices
This is called a "perfect 1-factorisation". Existence is incompletely determined.


<https://core.ac.uk/download/pdf/82799957.pdf> is an older source.


<https://math.stackexchange.com/questions/3455298/perfect-1-factorization-of-k-2n> contains some more recent refs. Searching on the name will find many more.


