Electronic Journal of Graph Theory and Applications 14 .
, 179Ae184 A special case of the tree packing conjecture Marcus E.
Gubanyi Department of Mathematics and Computer Sciences.
Concordia University.
Seward.
Nebraska.
gubanyi@cune.
Abstract The Tree Packing Conjecture of Gyyrfys states that for any set of nOe1 trees T = {T1 .
T2 .
TnOe1 }, where Ti has i edges.
T can be packed into Kn .
We define a family of trees called two-spiders that are almost stars, and show that packings of Kn with two-spiders can be constructed by exchanging edges of known packings.
We prove that if each tree Ti OO T is a two-spider and has at most i Oo 3Oe 5 two-legs for = 4 , then T packs into Kn .
Keywords: tree, packing, complete graph Mathematics Subject Classification : 05C05, 05C70 DOI: 10.
5614/ejgta.
Introduction Let G = {G1 .
G2 , .
Gn } be a set of simple graphs.
Then 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 G.
For the scope of this paper, we are concerned withPperfect packings of a set of trees into Kn .
A perfect packing is a packing of G into H such that ni=1 |E(Gi )| = |E(H)|.
A famous packing problem, known as the Tree Packing Conjecture (TPC), was posed by Gyyrfys and Lehel in 1976 .
Conjecture 1.
Let T = {T1 .
T2 .
TnOe1 } be a set of n Oe 1 trees, where Ti has i edges.
Then T packs into Kn .
Received: 14 March 2020.
Revised: 18 January 2026.
Accepted: 11 February 2026.
A special case of the tree packing conjecture Marcus E.
Gubanyi This conjecture seeks perfect packings because:
T OOT
|E(T )| =
nOe1 i = |E(Kn )|.
The TPC has been well studied and multiple special cases have been proven .
, 5, .
Special cases include restricting the trees in T to be in a family of trees or to satisfy certain conditions.
Gyyrfys and Lehel .
proved that the TPC holds if each tree in T is either a path or a star.
Roddity .
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 T .
One such example, proven by Balogh n and |E(Ti )| = and Palmer .
, states that any set of trees T = {T1 .
T2 , .
Tt } with t = 10 n Oe i 1, packs into Kn .
Asymptotic behaviors of the TPC were studied by Byttcher et al.
using a random tree embedding process.
The special case proved here relates to packings of Aualmost-starsAy studied by Dobson.
In .
Dobson proved the Tree Packing Conjecture holds for T where each tree Ti has a designated root adjacent to all but a small proportion of vertices.
This proportion approaches 0 as i increases.
Dobson increases this proportion when restricting to trees of bounded diameter.
In particular, for diameter at most Oo 4 .
class relevant to our wor.
, the Tree Packing Conjecture holds for trees Ti with less than 12 ( 11 Oe .
2 i OO 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 ofOographs called two-spiders, but we relax the Auroot-adjacencyAy requirement by allowing up to 3Oe4 5 i OO 0.
vertices to not be adjacent to the root in each Ti .
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 OO V (T ) such that for all other vertices v OO V (T ), dist.
, .
O 2 and deg.
O 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:
Oo Theorem 1.
Let T = {T1 .
T2 , .
TnOe1 } be a set of trees such that |E(Ti )| = i.
Let = 3Oe4 5 .
each Ti is a two-spider with less than i two-legs, then T packs into Kn .
Consider the case when each tree in 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 T consists of stars, because Kn is the edge-disjoint union of an n-vertex star with KnOe1 .
This provides the outline for the proof of our special case.
A packing of Kn with 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 i two-legs.
Section 4 provides open questions and directions for future work.
Preliminaries The following lemma will be useful in constructing packings of two-spiders into Kn .
A special case of the tree packing conjecture Marcus E.
Gubanyi Lemma 2.
Let S.
T be subgraphs of Kn such that: T is a tree.
S is a star.
E(T ) O E(S) = OI, and the root r OO S is not in V (T ).
If x OO T is a leaf, e = xy OO E(T ), and there exists eA = yr, eAA = xr OO E(S), then T Oe e eA = e T and S e Oe eA is a two-spider with one two-leg.
Proof.
Consider the given graphs.
Suppose x OO V (T ) is a leaf in T , e = xy OO E(T ) and eA = yr, eAA = xr OO E(S).
First let us show that T Oe e eA = e T .
Let f : V (T ) Ie V (T Oe e eA ) be the function defined as r if v = x, f .
= v else.
Let g = uw be an edge of T .
If u = x and w = x, then the edge f .
= uw is in T Oe e eA .
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 .
= f .
= r, f .
= f .
= y and f .
= ry = eA OO T Oe e eA .
Since f preserves structure of the graph and also is a bijection, we have that f is an isomorphism and T Oe e eA = e T.
Next we will show that S e Oe e is a two-spider with 1 two-leg.
Let v OO V (S e Oe eA ) and assume the deg.
> 2.
We know that the degree of each vertex v = r OO 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.
, .
For all v = y, the edge vr OO E(S e Oe eA ) and dist.
, .
= 1.
If v = y, then e = yx, eAA = xr yields a path of length 2 from v to r.
Thus S e Oe eA 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 K7 decomposed as an arbitrary packing of K6 in black, blue edge .
, .
is a pendant edge of some tree of that packing, and the red edges are a spanning star.
Exchanging edges .
, .
, .
according to Lemma 2.
1 yields an identical packing of K7 with the exception that the red graph is a two-spider with 1 two-leg.
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 1 applies to two-spiders, and we restrict T = {T1 .
T2 , .
TnOe1 } to contain only two-spiders.
When an edge e = xy OO Ti 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 Ti because exchanging such an edge would create a cycle in the packing.
We define A special case of the tree packing conjecture Marcus E.
Gubanyi Figure 1.
Illustration of an edge-exchange according to Lemma 2.
Exchanging the pendant edge .
, .
OO T with .
, .
OO 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 OO Ti incident to the root of Ti .
If Ti has Eei two-legs and e = xy OO Ti is exchanged, where y is the root of Ti , 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 Ti 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 Assume inductively that there exists a packing of T into Kn .
Add a vertex r and the edges of a star S with root r, resulting in a packing of Kn 1 .
Repeat the following while necessary and possible:
Exchange an exchangeable edge e = xy OO Ti with eA = yr OO S.
Remove the vertices x and y from the consideration for future exchanges.
Merge the resulting two-legs and the remaining star to form TnOe1 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 T has less than Oo 3Oe 5 i two-legs where = 4 OO 0.
Note that = .
Oe.
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 .
, .
is exchangeable because vertex 3 is the root of the green two-spider.
The exchange results in a packing of K7 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.
Proof.
Let n = 2.
Then T = {T1 } and T1 = K2 .
Thus T packs into Kn .
Assume inductively that for n Ou 2.
T packs into Kn where each Ti is a two-spider with Eei < i two-legs.
Suppose Tn is a two-spider with Een < n two-legs.
Let S be a star on n 1 vertices.
follows that T A = T O {S} packs into Kn 1 .
Let e = xy be an exchangeable edge of some Ti OC Kn .
Since S is a star with V (S) = V (Kn 1 ), there exists edges eA = yr, eAA = xr OO S.
Applying Lemma 2.
Ti Oe e eA O = Ti and A S e Oe e is a two-spider with 1 two-leg.
Consider the graph KnOe2 OC Kn where vertices x, y are Let S A OC S e Oe eA be the star with V (S A ) = V (KnOe2 ) O .
Again, apply Lemma 2.
to S A and Ti for some i where f OO KnOe2 O Ti is exchangeable.
A special case of the tree packing conjecture Marcus E.
Gubanyi Figure 2.
Illustration of an edge-exchange to add the second two-leg to T6 .
Exchanging pendant edge .
, .
OO T4 with pendant edge .
, .
OO T6 results in a two-spider with an additional two-leg while T4 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 = Een or there does not exist an exchangeable edge in Ti O KnOe2j .
We will show that the former must occur before the latter.
Let m = n Oe 2(Een Oe .
We will prove that there must exist an exchangeable edge in Ti O Km OC Kn for some i.
It is sufficient to show that the number of edges of Km 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:
PnOe1 PnOe1 n.
Oe.
= n2 Oe n N = 2 nOe1 i=0 i = 2 i=0 i = 2 i=0 Eei < 2 Compare this result to the number of edges in Km with m = n Oe 2(Een Oe .
> .
Oe .
n 2:
Oe .
Oe .
Oe .
= n2 > n2 Oe n |E(Km )| = .
Thus there exists an exchangeable edge to be used for the Een th exchange.
Let L = {L1 .
L2 , .
LEen } 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 (KnOe2Een ) O .
follows that the edges of R and L form a two-spider with root r and Een two-legs on n 1 vertices.
This two-spider is isomorphic to Tn .
Since the exchanges left each tree Ti with i < n unchanged up to isomorphism.
T A = {T1 .
T2 , .
Tn } packs into Kn 1 .
By induction, if each Ti is a two-spider with less than i two-legs, then T = {T1 .
T2 , .
TnOe1 } packs into Kn for all n.
A special case of the tree packing conjecture Marcus E.
Gubanyi Closing Remarks In this paper, we established a special case of Gyyrfys and LehelAos Tree Packing Conjecture .
, where we restricted the trees in T = {T1 .
T2 , .
Tn } to be two-spiders with each Ti 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 Ti .
Extensions of this work include exploring similar approaches to prove special cases of the 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 , .
TiOe1 remain the same up to isomorphism while exchanging edges to construct Ti .
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