Packing paths in complete graphs

Let lambda K-n denote the complete graph of order n and multiplicity lambda. 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, lambda and t, and any sequence m(1), m(2), ..., m(t) of positive integers, it is possible to pack t pairwise edge-disjoint paths of lengths m(1), m(2), ..., m(t) in lambda K-n if and only if m(i) <= n - 1 for i = 1, 2, ..., t and m(1) + m(2) + ... + m(t) <= lambda n(n - 1)/2. (C) 2009 Elsevier Inc. All rights reserved.