I am trying to see if, for the complete graph $K_{2n}$, there exists a labelling of the vertices with two labels $a$ and $b$ (each used exactly $n$ times), such that we can decompose the graph into $n$ hamiltonian paths that have the same labelling.

For example, if I take n=3, I numerate my vertices from $1$ to $6$, and associate respectively the labels $a$,$b$,$b$,$a$,$a$,$b$. Then, I take the three following paths :

$1-2-3-4-5-6$

$4-6-2-5-1-3$

$5-3-6-1-4-2$

The three paths have the same labelling and they are edge disjoint so it works.

I was able to prove the existence for $n$ odd, using Walecki's construction. For $n$ even, I know Walecki's construction does not work as the labels of the two extremities of the paths have to be different, but as I understand it is not the only construction I can use, so it does not necessarily mean that the labelling does not exist. I am leaning towards the idea that it does not exist, with the example $n=2$, but I don't see any theoretical argument to prove that. Would some of you have any ideas ? Thank you in advance.

1more comment