Electronic Journal of Graph Theory and Applications

Marcus E. Gubanyi

Department of Mathematics and Computer Sciences, Concordia University, Seward, Nebraska, U.S.A.

marcus.gubanyi@cune.edu

The Tree Packing Conjecture of Gyárfás states that for any set of n-1 trees \(\mathcal{T}=\{T_1,T_2\ldots T_{n-1}\}\), where \(T_i\) has i edges, \(\mathcal{T}\) can be packed into \(K_n\). We define a family of trees called two-spiders that are almost stars, and show that packings of \(K_n\) with two-spiders can be constructed by exchanging edges of known packings. We prove that if each tree \(T_i \in \mathcal{T}\) is a two-spider and has at most \(\alpha i\) two-legs for \(\alpha = \frac{3-\sqrt{5}}{4}\), then \(\mathcal{T}\) packs into \(K_n\).

Keywords: tree, packing, complete graph

Mathematics Subject Classification: 05C05, 05C70

DOI: 10.5614/ejgta.2026.14.1.11

1. Introduction

Let \(\mathcal{G} = \{G_1, G_2, \dots, G_n\}\) be a set of simple graphs. Then \(\mathcal{G}\) packs into a simple graph H if there exists a set of edge-disjoint subgraphs in H that are isomorphic to the graphs in \(\mathcal{G}\). For the scope of this paper, we are concerned with perfect packings of a set of trees into \(K_n\). A perfect packing is a packing of \(\mathcal{G}\) into H such that \(\sum_{i=1}^{n} |E(G_i)| = |E(H)|\).

A famous packing problem, known as the Tree Packing Conjecture (TPC), was posed by Gyár-fás and Lehel in 1976 [5].

Conjecture 1. Let \(\mathcal{T} = \{T_1, T_2 \dots T_{n-1}\}\) be a set of n-1 trees, where \(T_i\) has i edges. Then \(\mathcal{T}\) packs into \(K_n\).

Received: 14 March 2020, Revised: 18 January 2026, Accepted: 11 February 2026.

This conjecture seeks perfect packings because:

\[\sum_{T \in \mathcal{T}} |E(T)| = \sum_{i=1}^{n-1} i = |E(K_n)|.\]

The TPC has been well studied and multiple special cases have been proven [4, 5, 6]. Special cases include restricting the trees in \(\mathcal{T}\) to be in a family of trees or to satisfy certain conditions. Gyárfás and Lehel [5] proved that the TPC holds if each tree in \(\mathcal{T}\) is either a path or a star. Roddity [6] proved that the conjecture holds if all but three trees are stars. Similar conjectures have been proposed and proven with a reduced number of trees in \(\mathcal{T}\). One such example, proven by Balogh and Palmer [1], states that any set of trees \(\mathcal{T} = \{T_1, T_2, \dots, T_t\}\) with \(t = \frac{1}{10}n^{\frac{1}{4}}\) and \(|E(T_i)| = n - i + 1\), packs into \(K_n\). Asymptotic behaviors of the TPC were studied by Böttcher et al. [2], using a random tree embedding process.

The special case proved here relates to packings of "almost-stars" studied by Dobson. In [3], Dobson proved the Tree Packing Conjecture holds for \(\mathcal T\) where each tree \(T_i\) has a designated root adjacent to all but a small proportion of vertices. This proportion approaches 0 as i increases. In [4], Dobson increases this proportion when restricting to trees of bounded diameter. In particular, for diameter at most 4 (a class relevant to our work), the Tree Packing Conjecture holds for trees \(T_i\) with less than \(\frac{1}{2}(\sqrt{11}-3)^2i\approx 0.050i\) vertices not adjacent to a designated root. This proportion is constant as i increases. Our result is narrower in scope as we restrict to a class of graphs called two-spiders, but we relax the "root-adjacency" requirement by allowing up to \(\frac{3-\sqrt{5}}{4}i\approx 0.191i\) vertices to not be adjacent to the root in each \(T_i\).

A common definition of a spider graph is a tree such that no more than one vertex has degree greater than two. We define a two-spider as a tree T such that there exists a vertex \(r \in V(T)\) such that for all other vertices \(v \in V(T)\), \(dist(v,r) \leq 2\) and \(deg(v) \leq 2\). Spiders can be described as a collection of edge-disjoint paths joined together at one common vertex, denoted r for root. For two-spiders, these paths are each length one or two. We will refer to these paths as legs, specifically denoting two-legs as the paths of length two. This leads us to our main result:

Theorem 1.1. Let \(\mathcal{T} = \{T_1, T_2, \dots T_{n-1}\}\) be a set of trees such that \(|E(T_i)| = i\). Let \(\alpha = \frac{3-\sqrt{5}}{4}\). If each \(T_i\) is a two-spider with less than \(\alpha i\) two-legs, then \(\mathcal{T}\) packs into \(K_n\).

Consider the case when each tree in \(\mathcal{T}\) is a star. Recall that a star is a tree such that there exists a vertex v with each edge incident to v. The TPC holds by induction when \(\mathcal{T}\) consists of stars, because \(K_n\) is the edge-disjoint union of an n-vertex star with \(K_{n-1}\). This provides the outline for the proof of our special case. A packing of \(K_n\) with \(\mathcal{T}\) consisting of two-spiders can be constructed by transforming stars into two-spiders within the inductive step. In Section 2, we establish a useful lemma for transforming two-spiders. In Section 3, we prove the TPC holds for two-spiders with less than \(\alpha i\) two-legs. Section 4 provides open questions and directions for future work.

2. Preliminaries

The following lemma will be useful in constructing packings of two-spiders into \(K_n\).

Lemma 2.1. Let S, T be subgraphs of Kⁿ such that: T is a tree, S is a star, E(T) ∩ E(S) = ∅, and the root r ∈ S is not in V (T). If x ∈ T is a leaf, e = xy ∈ E(T), and there exists e ′ = yr, e′′ = xr ∈ E(S), then T − e + e ′ ^{=e T} and ^{S + e − e} ′ is a two-spider with one two-leg.

Proof. Consider the given graphs. Suppose x ∈ V (T) is a leaf in T, e = xy ∈ E(T) and e ′ = yr, e′′ = xr ∈ E(S).

First let us show that T −e+e ′ ^{=e T}. Let ^f : ^V (T) ^{→ V} (^{T −}e+^e ′ ) be the function defined as

\[f(v) = \begin{cases} r & \text{if } v = x, \\ v & \text{else.} \end{cases}\]

Let g = uw be an edge of T. If u ̸= x and w ̸= x, then the edge f(u)f(w) = uw is in T − e + e ′ . Suppose that one of u, w equals x, without loss of generality u = x. Since x is a leaf, there is only one edge incident to x in T; furthermore g = e. It follows that: f(u) = f(x) = r, f(w) = f(y) = y and f(u)f(w) = ry = e ′ ∈ T − e + e ′ . Since f preserves structure of the graph and also is a bijection, we have that f is an isomorphism and T − e + e ′ ^{=e T}.

Next we will show that S + e − e ′ is a two-spider with 1 two-leg. Let v ∈ V (S + e − e ′ ) and assume the deg(v) > 2. We know that the degree of each vertex v ̸= r ∈ V (S) is 1. Deleting one edge and adding another in simple graphs can only change the degree of vertices by 1. Thus, the only possible vertex with degree greater than 2 is r. Now let us consider dist(v, r). For all v ̸= y, the edge vr ∈ E(S + e − e ′ ) and dist(v, r) = 1. If v = y, then e = yx, e′′ = xr yields a path of length 2 from v to r. Thus S + e − e ′ is a two-spider and has only one two-leg.

The intent of this lemma is to allow us to transform something that we know how to pack into something else; specifically, we are transforming stars into two-spiders by exchanging edges within the packing. Note that if we have a packing and exchange two edges with Lemma 2.1, the only two graphs in the packing that change are the graphs containing the two edges. Moreover, since we have shown that one of the graphs remains isomorphic after the exchange, only one graph changes up to isomorphism and that graph is the two-spider we will construct in the inductive step of our proof. Figure 1 serves as an example of an exchange. On the left, we have a packing of K⁷ decomposed as an arbitrary packing of K⁶ in black, blue edge (0, 1) is a pendant edge of some tree of that packing, and the red edges are a spanning star. Exchanging edges (0, 1) and (1, 6) according to Lemma 2.1 yields an identical packing of K⁷ with the exception that the red graph is a two-spider with 1 two-leg.

3. A Special Case of the Tree Packing Conjecture

To prove a special case of the tree packing conjecture, Lemma 2.1 will be used to construct a packing where a star is transformed into a two-spider. We are only concerned with how Lemma 2.1 applies to two-spiders, and we restrict T = {T1, T2, . . . Tn−1} to contain only two-spiders. When an edge e = xy ∈ Tⁱ is exchanged with an edge in a star by the Lemma 2.1, we can no longer exchange any edges incident to vertices x and y because exchanging such an edge would transform the tree into something other than a two-spider. Also, we can no longer exchange any other edges of Tⁱ because exchanging such an edge would create a cycle in the packing. We define

Figure 1. Illustration of an edge-exchange according to Lemma 2.1. Exchanging the pendant edge \((0,1) \in T\) with \((1,6) \in S\) results in a two-spider with one two-leg while T is unchanged up to isomorphism.

an exchangeable edge as a pendant edge \(e \in T_i\) incident to the root of \(T_i\). If \(T_i\) has \(\ell_i\) two-legs and \(e = xy \in T_i\) is exchanged, where y is the root of \(T_i\), then we must only remove the vertices x and y from consideration. Any other pendant edge of a two-spider that has not yet been exchanged with, is still available to be exchanged. Note that according to Lemma 2.1, we could use a pendant edge of a two-leg for some \(T_i\) for an exchange. However, we forbid this in our arguments in order to ensure more exchangeable edges are available for future exchanges. An outline of our proof follows.

• 1. Assume inductively that there exists a packing of \(\mathcal{T}\) into \(K_n\).
• 2. Add a vertex r and the edges of a star S with root r, resulting in a packing of \(K_{n+1}\).
• 3. Repeat the following while necessary and possible:
  • (a) Exchange an exchangeable edge \(e = xy \in T_i\) with \(e' = yr \in S\).
  • (b) Remove the vertices x and y from the consideration for future exchanges.
• 4. Merge the resulting two-legs and the remaining star to form \(T_{n-1}\) within the packing.

In order to ensure there is an exchangeable edge for each two-leg in our packing, we must restrict the number of two-legs in each tree. It is sufficient to assume each tree in \(\mathcal{T}\) has less than \(\alpha i\) two-legs where \(\alpha = \frac{3-\sqrt{5}}{4} \approx 0.191\). Note that \(\alpha = \frac{(1-2\alpha)^2}{2}\).

Figure 2 exhibits an exchange used for constructing a two-spider. Any edges incident to vertices 0 or 1 cannot be used for exchanges. The green edge (2,3) is exchangeable because vertex 3 is the root of the green two-spider. The exchange results in a packing of \(K_7\) where each colored tree is unchanged up to isomorphism, except the red two-spider increases its number of two-legs by one.

This leads us to the proof of our main result, Theorem 1.1.

Proof. Let n = 2. Then \(\mathcal{T} = \{T_1\}\) and \(T_1 = K_2\). Thus \(\mathcal{T}\) packs into \(K_n\).

Assume inductively that for \(n \geq 2\), \(\mathcal{T}\) packs into \(K_n\) where each \(T_i\) is a two-spider with \(\ell_i < \alpha i\) two-legs. Suppose \(T_n\) is a two-spider with \(\ell_n < \alpha n\) two-legs. Let S be a star on n+1 vertices. It follows that \(\mathcal{T}' = \mathcal{T} \cup \{S\}\) packs into \(K_{n+1}\).

Let e=xy be an exchangeable edge of some \(T_i\subset K_n\). Since S is a star with \(V(S)=V(K_{n+1})\), there exists edges \(e'=yr, e''=xr\in S\). Applying Lemma 2.1, \(T_i-e+e'\cong T_i\) and S+e-e' is a two-spider with 1 two-leg. Consider the graph \(K_{n-2}\subset K_n\) where vertices x,y are removed. Let \(S'\subset S+e-e'\) be the star with \(V(S')=V(K_{n-2})\cup\{r\}\). Again, apply Lemma 2.1 to S' and \(T_i\) for some i where \(f\in K_{n-2}\cap T_i\) is exchangeable.

Figure 2. Illustration of an edge-exchange to add the second two-leg to T6. Exchanging pendant edge (2, 3) ∈ T⁴ with pendant edge (3, 6) ∈ T⁶ results in a two-spider with an additional two-leg while T⁴ is unchanged up to isomorphism.

Repeat this process, inducting on j defined as the number of exchanges performed, until one of two things occurs: j = ℓⁿ or there does not exist an exchangeable edge in Tⁱ ∩ Kn−2^j . We will show that the former must occur before the latter.

Let m = n−2(ℓn−1). We will prove that there must exist an exchangeable edge in Ti∩K^m ⊂ Kⁿ for some i. It is sufficient to show that the number of edges of K^m is greater than the number of edges that are not exchangeable. Let N be the number of edges in T that are not exchangeable. That is precisely the number of edges that are edges of a two-leg. It follows that:

\[\mathcal{N} = 2\sum_{i=0}^{n-1} \ell_i < 2\sum_{i=0}^{n-1} \alpha i = 2\alpha\sum_{i=0}^{n-1} i = 2\alpha\frac{n(n-1)}{2} = \alpha n^2 - \alpha n\]

Compare this result to the number of edges in K^m with m = n − 2(ℓⁿ − 1) > (1 − 2α)n + 2:

\[|E(K_m)| = \frac{m(m-1)}{2} \tag{1}\]

\[> \frac{((1-2\alpha)n+2)((1-2\alpha)n+1)}{2}\] (2)

\[= \alpha n^2 + \frac{3(1 - 2\alpha)}{2}n + 1 \tag{3}\]

\[> \alpha n^2 - \alpha n\] (4)

\[> \mathcal{N}\] (5)

Thus there exists an exchangeable edge to be used for the ℓⁿ th exchange. Let L = {L1, L2, . . . L^ℓn } be the set of two-legs that were the results of exchanges. Each of these two-legs is a path with 2 edges, and they each share exactly one vertex, the root r. There is only one shared vertex because after each exchange, the other two vertices of that two-leg were removed from consideration for subsequent exchanges. Furthermore, let R be the remaining star with V (R) = V (Kn−2ℓⁿ )∪ {r}. It follows that the edges of R and L form a two-spider with root r and ℓⁿ two-legs on n + 1 vertices. This two-spider is isomorphic to Tn. Since the exchanges left each tree Tⁱ with i < n unchanged up to isomorphism, T ′ = {T1, T2, . . . Tn} packs into Kn+1. By induction, if each Tⁱ is a two-spider with less than αi two-legs, then T = {T1, T2, . . . Tn−1} packs into Kⁿ for all n.

4. Closing Remarks

In this paper, we established a special case of Gyárfás and Lehel's Tree Packing Conjecture [5], where we restricted the trees in T = {T1, T2, . . . Tn} to be two-spiders with each Tⁱ having less than αi two-legs. The constant α is optimal for ensuring that an exchangeable edge exists for each step of the construction, which follows from our definition that exchangeable edges must be incident to the root of a Tⁱ .

Extensions of this work include exploring similar approaches to prove special cases of the conjecture. An alternative definition of an exchangeable edge would require a different approach to constructing packings but may result in a looser restriction on the number of two-legs. Inductive edge-exchanging methods may apply beyond two-spiders, such as for spiders with longer legs or trees with radius 3. A challenge of this approach is ensuring that trees T1, ...Ti−¹ remain the same up to isomorphism while exchanging edges to construct Tⁱ . Our exchanges apply only to two-spiders. Thus, alternative exchange methods are necessary to extend this work.

Acknowledgement

We express thanks to Margaret Bayer and Jeremy Martin for their guidance over the course of this research and their review of the manuscript.

References

• [1] J. Balogh and C. Palmer, On the Tree Packing Conjecture, SIAM J. Discrete Math. 27 (2013), 1995–2006.
• [2] J. Böttcher, J. Hladký, D. Piguet, and A. Taraz, An approximate version of the tree packing conjecture. Israel Journal of Mathematics 211 (1) (2016), 391–446.
• [3] E. Dobson, Packing Almost Stars into the Complete Graph, J. Graph Theory 25 (1997), 169– 172.
• [4] E. Dobson, Packing Trees of Bounded Diameter into the Complete Graph, Australas. J. Combin. 37 (2007), 89–100.
• [5] A. Gyárfás and J. Lehel, Packing Trees of Different Orders into Kn, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1986, Colloq. Math. Soc. János Bolyai 18 (1978), 463– 469.
• [6] Y. Roditty, Packing and covering of the complete graph. III. On the tree packing conjecture. Sci. Ser. A Math. Sci. (NS) 1 (1988): 81–85.
• [7] H. Yap, Packing of graphs–a survey, Annals of Discrete Mathematics 38 (1988). 395–404.