# Complete Graphs as Unions of Paths

Show that for $n \geq 2$ the complete graph $K_n$ is the union of paths of distinct lengths.

I have been stuck on this problem for the past couple of days now and would really like to see a solution/proof.

What I have tried so far is the following:

We know that the size of the set of edges $E(K_n)$ is $|E(k_n)| = {n \choose 2} = \frac{n!}{2!(n-2)!} = \frac{n(n-1)}{2} = \displaystyle \sum_{i=1}^{n-1} i$.

From here, I considered $K_{n+1}$ and the respective size of the edge set which came out to $\frac{n(n+1)}{2}$. If I understand correctly, then we need to somehow choose a partition of $K_n$, so maybe separating the vertex set into two different sets might help, but I am not even sure if this is the right way to go about it.

Many thanks in advance for your time. Any help is greatly appreciated.

• I would try an induction approach. Have you tried that? – hardmath Feb 17 '16 at 21:13
• Do the paths need to be disjoint? Otherwise we could just take a single path with length sufficiently larger than $(n)(n-1)/2$ and wrap it over itself until you cover all of $K_n$. – Mike Pierce Feb 18 '16 at 19:22

If $n=2k+1$, the graph is the disjoint union of $k$ Hamiltonian-cycles and from there you know what to do. If $n=2k$, use the previous construction for $n-1$ with the additional constraint that exactly two paths start at each vertex but one, and then extend each path with an extra edge.