Path-factorizations of complete bipartite multigraphs

There are simple arithmetic conditions necessary for the complete bipartite graph K m , n to have a complete factorization by subgraphs that are made up of disjoint copies of P k , the path on k vertices. Using a difficult construction, Du and Wang showed that these conditions are also sufficient, but left open the corresponding conjecture for complete multigraphs λ K m , n . In this paper we reformulate the problem to make it more tractable in individual cases. Using this new approach we prove the multigraph conjecture; our proof yields a much simpler proof for the original case λ = 1 .