Existence of a 2-labelled Hamiltonian Path decomposition of $K_{2n}$

Question

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.

Answer 1

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.