Purely Heterogeneous Spanning Tree Decompositions

Decompositions of complete or near-complete graphs into spanning trees have been widely studied, but usually in the homogeneous case, where all component trees are isomorphic. A spanning tree decomposition \( \mathcal{T} = (T_1, \ldots, T_n) \) of such a graph is purely heterogeneous if no two trees \( T_i \) are isomorphic. We show existence of such decompositions with the maximum degree condition \( \Delta(T_i) = i+1 \) for each \( i \in [1..n] \), for every largest possible graph of odd order, and every even order graph which is the complement of a spanning tree satisfying a necessary maximum degree condition.