On the decomposition of Kn into complete m-partite graphs

Graham and Pollak [3] proved that n ?1 is the minimum number of edge-disjoint complete bipartite subgraphs into which the edges of K_n can be decomposed. Using a linear algebraic technique, Tverberg [2] gives a different proof of that result. We apply his technique to show that for “almost all n,” ? (n + m ?3)/(m ?1) ? is the minimum number of edge-disjoint complete m-partite subgraphs in a decomposition of K_n.