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.



Existence of a 2-labelled Hamiltonian Path decomposition of $K_{2n}$
I think I have a proof that such a labelling cannot exist if $n$ is even.


Suppose we have a labelling $\ell : V(K\_m) \to \{ a, b \}$ and a decomposition of $K\_{m}$ into a family $\mathcal{P}$ of Hamiltonian paths. It is clear by counting edges that $p := |\mathcal{P}| = m/2$, so in particular $m$ must be even. Every path $P = v\_1 \ldots v\_m$ in $K = K\_{m}$ has a *trace* $\ell(v\_1) \ldots \ell(v\_m) \in \{ a, b \}^m$. We assume that every path in $\mathcal{P}$ has the same trace, which we denote by $T$. 


Let $A$ be the set of all vertices that receive label $a$ and $B$ the set of those that receive label $b$. Suppose that neither $A$ nor $B$ is empty.
Counting the edges incident to a fixed vertex, it is easy to see that every vertex is the end vertex of precisely one $P \in \mathcal{P}$. In particular, every $P \in \mathcal{P}$ has one end in $A$ and the other in $B$ and $|A| = |B| = p$ (without loss of generality, all paths start in $A$ and end in $B$).


**Edited with a simplification:**


Every $P \in \mathcal{P}$ has the same number 
$$
e\_A := | \{ 1 \leq i < n : T\_i = T\_{i+1} = a \} |
$$ 
of edges within $A$. Then, since every edge of $K[A]$ lies in precisely one $P \in \mathcal{P}$, we get
$$
p(p-1)/2 = |E(K[A])| = pe\_A
$$
or $e\_A = (p-1)/2$, from which it follows that $p$ must be odd.


