Erdős Problem #743
tree packing conjecture

Let \(T_2,\ldots,T_n\) be a collection of trees such that \(T_k\) has \(k\) vertices. Can we always write \(K_n\) as the edge disjoint union of the \(T_k\)? A conjecture of Gyárfás, known as the tree packing conjecture. We state it as a packing. For every \(n\) and all trees \(T_k\) on the vertex set `Fin k`, \(2 \leq k \leq n\), there are injective maps \(f_k : \{0, \ldots, k - 1\} \to \{0, \ldots, n - 1\}\) such that the graphs \(f_k(T_k)\) are pairwise edge-disjoint (see `IsPacking`). Every tree with \(k\) vertices is isomorphic to a tree on `Fin k`, so this covers every collection of trees. A tree with \(k\) vertices has \(k - 1\) edges, and \(\sum_{k=2}^{n} (k - 1) = \binom{n}{2}\) is the number of edges of \(K_n\). Hence the copies \(f_k(T_k)\) of a packing cover every edge of \(K_n\). So a packing is the same as a decomposition of \(K_n\) into copies of \(T_2, \ldots, T_n\).