Decomposition of the completer-graph into completer-partiter-graphs

Forn ≥ r ≥ 1, letf r (n) denote the minimum numberq, such that it is possible to partition all edges of the completer-graph onn vertices intoq completer-partiter-graphs. Graham and Pollak showed thatf 2(n) =n − 1. Here we observe thatf 3(n) =n − 2 and show that for every fixedr ≥ 2, there are positive constantsc 1(r) andc 2(r) such thatc 1(r) ≤f r (n)⋅n −[r/2] ≤n 2(r) for alln ≥ r. This solves a problem of Aharoni and Linial. The proof uses some simple ideas of linear algebra.