5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.)

enter image description here

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).

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.