How to decompose edges of $K_n$ into Hamiltonian paths?

Question

Let $K_n$ be a complete graph with n vertices, where n is even

Show that $K_n$ can be decomposed into $\frac{(n-1)}{2}$ disjointed Hamiltonian paths on edges

My idea was to use Menger's theorem that says:

Let $G$ be a connected graph and let $u$ and $v$ be vertices of $G$. Then the number of $uv$-disjoint paths per edge is equal to the minimum number of edges on a $(u, v)$ -separator

Since we are working with a complete graph the minimum number of edges that there will be in a $(u, v)$ - separator will be $n-1$, so we will have $n-1$ internally disjoint paths in edges. However, I don't know how to continue

Answer 1

We can decompose the set of edges of $K_n$ into ($n/2$ edge-disjoint) paths provided $n+1$ is prime. For this it suffices to decompose the set of edges of $K_{n+1}$ into Hamiltonian cycles, then fix a vertex $v$ of $K_{n+1}$ and remove it from each of cycles of the decomposition. This results a decomposition of the set of edges of $K_{n+1}$ without $v$ into Hamiltonian paths.

We can construct a required decomposition of $K_{n+1}$ identifying its set of vertices with a field $\Bbb Z_{n+1}=\Bbb Z/(n+1)\Bbb Z$. To each integer $i$ from $1$ to $n/2$ corresponds a Hamiltonian cycle in $K_{n+1}$, whose edges are $\{j,k\}\subset\Bbb Z_{n+1}$ such that $j-k=\pm i\pmod {n+1}$.

Answer 2

There is a standard construction for decomposing $K_{2k}$ into $k$ Hamiltonian paths. It is illustrated below:

Formally, if the vertices are numbered $0, 1, \dots, 2k-1$ modulo $2k$ (which we visualize by arranging them in a circle, as I did above) then the $i^{\text{th}}$ Hamiltonian path is $$ (i, i+1, i-1, i+2, i-2, i+3, i-3, \dots, i + (k-1), i - (k-1), i+k). $$ Some checking needs to be done to verify that every edge is used exactly once.

This construction can be extended to decomposing $K_{2k+1}$ into $k$ Hamiltonian cycles. If the extra vertex of $K_{2k+1}$ not appearing in $K_{2k}$ is called $x$, then each of the Hamiltonian paths in $K_{2k}$ is extended to a Hamiltonian cycle in $K_{2k+1}$ by joining both endpoints to $x$. (Note that each vertex in $K_{2k}$ is the endpoint of exactly one Hamiltonian path in the decomposition.)