Applying a proof of tverberg to complete bipartite decompositions of digraphs and multigraphs

Graham and Pollak 2] proved that n – 1 is the minimum number of edge-disjoint complete bipartite subgraphs into which the edges of K_n decompose. Tverberg 6], using a linear algebraic technique, was the first to give a simple proof of this result. We apply Tverberg's technique to obtain results for two related decomposition problems, in which we wish to partition the arcs/edges of complete digraphs/multigraphs into a minimum number of arc/edge-disjoint complete bipartite subgraphs of appropriate natures. We obtain exact results for the digraph problem, which was posed by Lundgren and Maybee 4]. We also obtain exact results for the decomposition of complete multigraphs with exactly two edges connecting every pair of distinct vertices.