# Decomposing $K_v - K_u$ into Hamilton paths where $v = u^2 - u + 1$.

A decomposition of a graph $G$ into subgraphs $H$ is a collection of graphs all isomorphic to $H$ which are edge-disjoint in $G$ and together cover all the edges of $G$.

Let $u \geq 1$ and $v = u^2 - u + 1$.

I wish to show that there is a decomposition of $K_v - K_u$ into Hamilton paths.

As $v = u(u-1) + 1$ is odd, it is well-known that $K_v$ decomposes into Hamilton cycles.

Given a Hamilton cycle decomposition of $K_v$ it is sufficient to find a subset $U$ of $V$ containing $u$ vertices, such that one edge from every Hamilton cycle is contained in $U$. Is it always possible to find such a subset $U$? If not, may we find a Hamilton path decomposition of $K_v - K_u$ another way?

The following appears as a corollary in A. J. W. Hilton's paper "Hamiltonian Decompositions of Complete Graphs."

For $1 \leq r \leq n$, any proper edge colouring of $K_r$ can be extended to a Hamiltonian decomposition of $K_{2n + 1}$.

Taking $r = u$ and $n = u(u-1)/2$, the result follows.