Packing three trees (Q1916129)

Suppose \(G_1, G_2,\dots, G_k\) are graphs of order at most \(n\). Then there is a packing of \(G_1, G_2,\dots, G_k\) into the complete graph \(K_n\) if there exist injections \(\alpha_i: V(G_i)\to V(K_n)\), \(i= 1,2,\dots, n\), such that \(\alpha^*_i(E(G_i))\cap \alpha^*_j(E(G_j))= \varnothing\) for \(i\neq j\), where \(\alpha^*_i: E(G_i)\to E(K_n)\) is induced by \(\alpha_i\). The main result of this paper is Theorem 10: Any three trees of order \(n- 1\) can be packed into \(K_n\). Note that A. M. Hobbs, B. A. Bourgeois and J. Kasiraj had earlier proved that three trees \(T_1\), \(T_2\), \(T_3\) of orders \(n_1< n_2< n_3= n\), respectively, can be packed into \(K_n\), see Discrete Math. 67, 27-42 (1987; Zbl 0642.05043). H. Wang and N. Sauer had proved that if \(T\) is a tree of order \(n\geq 6\) and \(T\neq S_n\) (a star), \(S_n'\) (a tree obtained by subdividing an edge of \(S_{n- 1})\), \(S_6''\) (\(S''_n\) is a tree obtained by replacing an edge of \(S_{n- 2}\) by a path of length 3), then three isomorphic copies of \(T\) can be packed into \(K_n\), see Eur. J. Comb. 14, No. 2, 137-142 (1993; Zbl 0773.05084).