6
$\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$
0

1 Answer 1

5
$\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$
1
  • $\begingroup$ Can you do the same, but where you only want the paths to differ on at least one edge? $\endgroup$
    – apkg
    Nov 4, 2019 at 13:56

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