Let λKn denote the complete graph of order n and multiplicity λ.
We prove Tarsi’s conjecture [M. Tarsi, Decomposition of a complete
multigraph into simple paths: Nonbalanced handcuffed designs,
J. Combin. Theory Ser. A 34 (1983) 60–70] that for any positive
integers n, λ and t, and any sequence m1,m2, . . . ,mt of positive
integers, it is possible to pack t pairwise edge-disjoint paths of
lengths m1,m2, . . . ,mt in λKn if and only if mi ≤ n - 1 for i = 1, 2, ..., t and m1 + m2 + ⋯ + mt ≤ λ ( (n(n−1)) / 2 ).
© 2009 Elsevier Inc.