4
$\begingroup$

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.

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ I would try an induction approach. Have you tried that? $\endgroup$ – hardmath Feb 17 '16 at 21:13
  • $\begingroup$ 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$. $\endgroup$ – Mike Pierce Feb 18 '16 at 19:22
1
$\begingroup$

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.

| cite | improve this answer | | | | |
$\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.