Partición de las aristas del grafo completo en caminos de distinta longitud

Question

Dejemos que $K_n$ sea el grafo completo no dirigido en $n$ vértices. ¿Puedes dividir las aristas de $K_n$ en $n-1$ trayectorias de longitudes $1,2,\ldots,n-1$ ¿que los conjuntos de aristas de los caminos sean disjuntos por pares?

Creo que la afirmación es cierta, pero no puedo probarla. También es posible que sea un problema abierto.

Answer 1

Para impar $n \geq 5$ podemos descomponer $K_n$ en $(n-1)/2$ borde-desunido $n$ -ciclos. Estos se pueden dividir en trayectorias de longitudes $1,2,\ldots,n-1$ (rompa el primero en longitudes de camino $1$ y $n-1$ El segundo en $2$ y $n-2$ y así sucesivamente). (Esto se llama la descomposición de Walecki).

Al eliminar un vértice de la descomposición de Walecki para $K_{n+1}$ encontramos: para incluso $n \geq 4$ podemos descomponer $K_n$ en $n/2$ borde-desunido $(n-1)$ -trayectorias. Estos pueden dividirse en caminos de longitudes $1,2,\ldots,n-1$ (dejar uno solo, romper uno en longitudes de camino $1$ y $n-2$ El segundo en $2$ y $n-3$ etc.).