The question is as follows:

Are some good necessary and/or sufficient conditions known for when can $K_{m,n}$ be factorized into Hamiltonian paths?

In other words when can we have an edge disjoint union of Hamiltonian paths equaling the graph $K_{m,n}$.

The analogous solution for the problem for Hamiltonian cycles is well known (such graphs are characterized by $m=n=2k>1$). I searched the internet for a solution for the analogous path problem to no avail. I suspect that it is not known.


Suppose without loss of generality that $m \geq n$. Then either $m = n$ or $m = n + 1$.

If $m = n$, then each Hamiltonian path in $K_{m,m}$ has $2m-1$ edges. If there are $h$ paths, then $h(2m-1) = m^2$, which is impossible, since $2m-1$ has prime factors distinct from those of $m$ while $m^2$ does not.

If $m = n+1$, then each Hamiltonian path in $K_{n+1,n}$ has $2n$ edges. If there are $h$ paths, then $h(2n) = n(n+1)$, so $h = \frac{n+1}{2}$.

Hence we must have $n+1$ even, and indeed, all graphs $K_{2k,2k-1}$ can be decomposed into Hamiltonian paths. To see this, consider adding a vertex to the smaller side; then there is a decomposition into Hamiltonian cycles; removing the extra vertex leaves a decomposition of our original graph into Hamiltonian paths.

  • $\begingroup$ Thank you. I understand your answer. Could you give a reference for it as well or this is your own solution? $\endgroup$ – Shahab Feb 22 '16 at 3:13
  • $\begingroup$ @Shahab: It's my own solution. $\endgroup$ – Nick Matteo Feb 22 '16 at 3:20
  • $\begingroup$ May I cite it in your name as given on your website? $\endgroup$ – Shahab Feb 22 '16 at 3:26
  • $\begingroup$ @Shahab: Sure! (Or feel free to use the result without citing me.) $\endgroup$ – Nick Matteo Feb 22 '16 at 3:52

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.