Multicolored forests in bipartite decompositions of graphs

We show that in any edge-coloring of the complete graph Kn on n vertices, such that each color class forms a complete bipartite graph, there is a spanning tree of Kn, no two of whose edges have the same color. This strengthens a theorem of Graham and Pollak and verifies a conjecture of de Caen. More generally we show that in any edge-coloring of a graph G with p positive and q negative eigenvalues, such that each color class forms a complete bipartite graph, there is a forest of at least max{p, q} edges, no two of which have the same color. In the case where G is bipartite there is always such a forest which is a matching. © 1991.