An Algorithm for the Decomposition of Complete Graph into Minimum Number of Edge-disjoint Trees

In this work, we study methodical decomposition of an undirected, unweighted complete graph (Kₙ of order n, size m) into minimum number of edge-disjoint trees. We find that x, a positive integer, is minimum and x=/2 as the edge set of Kₙ is decomposed into edge-disjoint trees of size sequence M = ₁,m₂,...,mₓ\ where mᵢ≤(n-1) and Σᵢ₌₁ˣ mᵢ = n(n-1)/2. For decomposing the edge set of Kₙ into minimum number of edge-disjoint trees, our proposed algorithm takes total $O(m)$ time.