Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Let $K_n$ be the complete undirected graph on $n$ vertices. Can you partition the edges of $K_n$ into $n-1$ paths of lengths $1,2,\ldots,n-1$ such that the edge-sets of the paths are pairwise disjoint?
I believe the statement to be true, but I cannot prove it. It also possible that this is an open problem.
For odd $n \geq 5$, we can decompose $K_n$ into $(n-1)/2$ edge-disjoint $n$-cycles. These can be broken into paths of lengths $1,2,\ldots,n-1$ (break the first one into path lengths $1$ and $n-1$, the second one into $2$ and $n-2$, and so on). (This is called the Walecki decomposition.)
By deleting a vertex from the Walecki decomposition for $K_{n+1}$, we find: for even $n \geq 4$, we can decompose $K_n$ into $n/2$ edge-disjoint $(n-1)$-paths. These can be broken into paths of lengths $1,2,\ldots,n-1$ (leave one alone, break one into path lengths $1$ and $n-2$, the second one into $2$ and $n-3$, and so on).
