Hamilton path decompositions of complete multipartite graphs.

Abstract We prove that a complete multipartite graph K with n > 1 vertices and m edges can be decomposed into edge-disjoint Hamilton paths if and only if m n − 1 is an integer and the maximum degree of K is at most 2 m n − 1. [ABSTRACT FROM AUTHOR]