WorksMathematics
A Proof of The Twin-Star Hypothesis in Dimension Five
Abstract
It was recently shown that the question of whether the determinant-like map is unique up to multiplication by a scalar is equivalent to a combinatorial conjecture regarding cycle-free -partitions of the complete graph , known as the twin-star hypothesis. This hypothesis asserts that every cycle-free -partition of is weakly equivalent to one that contains a component isomorphic to the twin-star graph . This hypothesis was previously established for . In the present paper, we prove it for . Consequently, the associated determinant-like map is unique up to a scalar in dimension .
Introduction
The decomposition of complete graphs into spanning trees is a natural problem in graph theory, and has been investigated from several perspectives. In particular, decompositions of complete graphs of even order into isomorphic spanning trees have been studied through graph factorizations and labeling methods [4, 9]. Further work has examined which tree structures can occur in such factorizations, including trees with a prescribed number of non-leaf vertices and particular families of trees [5, 8]. Although the structure of an individual spanning tree is well understood, requiring the edges of a complete graph to be distributed among several spanning trees, with each edge belonging to exactly one tree, imposes strong restrictions on their possible structures. Related questions have been studied under additional conditions, such as edge-coloring constraints [2, 7, 11] and geometric restrictions [1]. More general questions regarding partitions of complete graphs have also been considered in [3].
Let be an integer, and let denote the complete graph on vertices. A cycle-free -partition of is an ordered -tuple
of cycle-free spanning subgraphs whose edge sets are pairwise disjoint and together contain every edge of . Since has edges and each cycle-free spanning subgraph has at most edges, every component must have exactly edges and is therefore a spanning tree.
Our interest is in understanding how these partitions can be transformed into one another while preserving the cycle-free property. A particularly useful family of transformations was introduced by Lippold, Staic, and Stancu in [10]. Given a cycle-free -partition and three distinct vertices , , of , they proved that there exists a unique cycle-free -partition which agrees with on every edge outside the triangle with vertices , , , but differs from on at least two of the three edges of this triangle. Moreover, the transformation
is an involution, called the triangle involution , or simply the involution .
Triangle involutions provide a way to modify a cycle-free partition locally without destroying the spanning-tree structure of its components. By applying these transformations, we obtain a natural equivalence relation on the set of cycle-free -partitions of .
Two cycle-free -partitions are said to be involution equivalent if one can be obtained from the other by a finite sequence of triangle involutions. This leads to the following conjecture, formulated in [10].
Conjecture 1.1. Any two cycle-free -partitions of are involution equivalent.
Conjecture 1.1 was established for by Lippold, Staic, and Stancu [10]. A further reduction of this conjecture is obtained in [6]. The Authors showed that the problem can be approached by focusing on a particular spanning tree among the components of a partition. To formulate it, we need to recall the following definition from [6 Definition 3.9].
Definition 1.2. Two cycle-free -partitions of are said to be weakly equivalent if, after possibly relabeling the vertices of and permuting the components of one partition, the resulting partitions are involution equivalent.
The particular spanning tree targeted in this reduction is the twin-star graph . It consists of two adjacent vertices of degree , each joined to leaves. Thus is a tree on vertices with exactly leaves; see Figure 4. With this terminology, the reduction of Conjecture 1.1, known as the twin-star hypothesis, can be stated as follows.
Figure 4. The twin-star graph , with vertices.
Conjecture 1.3. Every cycle-free -partition of is weakly equivalent to one containing a component isomorphic to .
The relationship between Conjectures 1.1 and 1.3 was established in [6]. If Conjecture 1.1 holds, then Conjecture 1.3 follows. Conversely, if the twin-star hypothesis holds for every , then Conjecture 1.1 also holds. Using this reduction, the authors of [6] established the case , extending the previously known cases , and . The advantage of this formulation is that it reduces the problem of comparing arbitrary cycle-free partitions to that of obtaining a specific tree structure in one of their components.
These combinatorial questions also have an important algebraic motivation. They arise from a uniqueness problem concerning a determinant-like map associated with the generalized exterior algebra introduced by Staic in [13]. Let be a field and let be a -dimensional vector space over . Motivated by a generalization of the classical determinant, Staic conjectured in [13] the existence and uniqueness, up to multiplication by a scalar, of a nonzero linear map
satisfying the following vanishing condition:
whenever there exist three indices such that
The connection between this algebraic construction and the combinatorial structure of was developed in [10], where the uniqueness problem for was shown to be equivalent to Conjecture 1.1.
The existence of for arbitrary was established in [12], while its uniqueness in general remains open. The map also has applications in geometry and combinatorics [12, 15], as well as in equilibrium problems in classical mechanics [14]. Consequently, progress on the twin-star hypothesis also provides information about the uniqueness of this determinant-like map.
The purpose of the present paper is to establish the twin-star hypothesis in dimension five. When , a cycle-free 5-partition of consists of five spanning trees, each having 9 edges. The twin-star is the tree on 10 vertices with two adjacent vertices of degree 5 and eight leaves. We prove that every cycle-free 5-partition of is weakly equivalent to one containing a component isomorphic to , thereby establishing Conjecture 1.3 for . Since the twin-star hypothesis is already known for , our result also establishes Conjecture 1.1 for . Consequently, the corresponding map
is unique up to multiplication by a scalar.
The paper is organized as follows. In § 2, we introduce the notation and establish some preliminary results on cycle-free partitions. In § 3, we give more properties of cycle-free -partitions and introduce the notion of an extremal component, which is a component chosen to have the maximum number of leaves among all the component of all partition weakly equivalent to a given partition, and among all such components, the minimum number of branch vertices. Using weak equivalence, we establish the structural properties of this component and prove that it has at least leaves; see Theorem 3.8. In § 4, we specialize to and determine the possible branch-degree configurations of an extremal component with six or seven leaves. § 5 and § 6 exclude these two cases, respectively, showing that an extremal component must have eight leaves and hence be isomorphic to . This establishes our main result in Theorem 6.8.
Preliminaries
In this section, we introduce the notation used throughout the paper and establish some preliminary results on cycle-free partitions that we use in the subsequent sections.
Let be a graph. We denote its vertex and edge sets by and , respectively. An edge joining two vertices and is denoted by . We write for the degree of a vertex in and for the set of its neighbors. We also use the notation
to denote a path with consecutive vertices .
We refer to vertices of degree at least 3 as branch vertices and we use the notations
Since every vertex of a tree with at least two vertices is either a leaf, a degree-2 vertex, or a branch vertex, we have
We recall the following identity relating the number of leaves of a tree to the degrees of its branch vertices.
Lemma 2.1. For every tree with at least two vertices,
Proof. Since is a tree, we have that
and consequently
Splitting the sum according to vertex degree, we obtain
which gives the desired identity. □
Before studying the effect of triangle involutions on cycle-free -partitions of , we first illustrate how such an involution changes the distribution of edges among the components of a cycle-free partition in general. Consider as an example the cycle-free 2-partition of defined by
as shown in Figure 1.

Figure 1. An illustration of the triangle involution on the cycle-free 2-partition of .
We apply the involution . Since the involution changes only the three edges of the triangle with vertices , the only possible nontrivial changes involve the edge and one of the edges or . The edge cannot be exchanged with , because this would give the second component the edge set
which contains a cycle. Therefore this possibility is excluded. Since the involution is nontrivial, it follows that it must exchange the edges and between the two components. Thus, writing , we obtain
Both resulting components are again spanning trees.
Let and let be a cycle-free -partition of . The fact that the components of a cycle-free -partition together contain every edge of imposes a restriction on the degree of each vertex.
Lemma 2.2. For every vertex and every , we have
.
Proof. The edges incident with are distributed among the spanning trees , so
Since each is connected, every summand is at least . Hence, for any fixed ,
The following lemma describes how an involution can change the attachment of a leaf in a component of the cycle-free -partition .
Lemma 2.3. Let be a leaf of , with , and suppose that and do not belong to . Then the involution has one of the following two effects:
It replaces by in .
It leaves unchanged, in which case and belong to two different components and are exchanged by the involution.
In particular, if and belong to the same component, then the involution replaces by in .
Proof. Among the three edges of the triangle with vertices , the component contains only . If the involution changes , this edge must be replaced by either or . The first possibility is impossible, since deleting the leaf edge isolates , while adding does not reconnect it. Thus the only possible change in is the replacement of by .
If remains unchanged, the other two edges must be exchanged between two distinct components, because the involution is nontrivial. This also proves the final assertion.
The possibility (i) in Lemma 2.3 allows us to move a leaf from one vertex to another while preserving the spanning-tree structure. We introduce the following terminology to describe this type of operation.
Definition 2.4. Let be a component of a cycle-free -partition, and let be a leaf of adjacent to a vertex . For a vertex , if the involution replaces the edge by in , we say that it transfers the leaf from to , or that receives the leaf . In this case, is called a destination of .
The following lemma provides a sufficient condition for the existence of such a destination for a leaf in . The particular case was established in [6].
Lemma 2.5. Suppose that is a leaf of , with , and let satisfy for every . If , then there exists that receives the leaf .
Proof. Suppose, for a contradiction, that no vertex receives the leaf . We fix , and write
for some . By Lemma 2.3, we have , and we apply the involution which leaves unchanged while exchanging and .
Let denote the new -th component. Then
Since both and are trees, the edge lies on the unique path from to in . Since is incident with , this path has the form
Consequently, the unique path from to in does not start with . This situation is illustrated in Figure 2.
Figure 2. The exchange of and between and .
Similarly, if denotes the new -th component, then
Since and are trees, the edge belongs to the unique path from to in . In particular, the path from to in does not start with . The same is true for every other component , since none contains .
Therefore, for every , none of the paths from to in can start with .
There are edges incident with and out of these, belong to , while the edges with , are excluded as possible first edges of the paths above. Hence these paths have at most
possible first edges. Since the components are edge-disjoint, the paths must start with distinct edges. Therefore
which gives
contrary to the hypothesis. □
A consequence of Lemma 2.5 is the existence of a lower bound on the number of possible destinations of any leaf.
Corollary 2.6. Let be a leaf of , with . Among the vertices satisfying , at least receive the leaf .
Proof. Put . Among the vertices different from and , exactly are adjacent to in . Hence there are
vertices satisfying .
We now determine how many of these vertices fail to receive the leaf . By Lemma 2.5, every set of at least such vertices contains a destination of . Therefore, the number of such vertices that fail to receive is at most . Since there are eligible vertices, at least
of them receive the leaf . □
We conclude this section by recalling the following characterization of the twin-star graph , established in [6]. We include a short proof for the convenience of the reader.
Lemma 2.7. Let be a component of a cycle-free -partition of . Then
Moreover, if and only if, is isomorphic to .
Proof. By Lemma 2.2, every vertex of has degree at most . If , then is a star whose central vertex has degree , which is a contradiction. Hence
Suppose now that . Then has exactly two non-leaf vertices, say and . Since is connected, these vertices must be adjacent, and every other vertex is a leaf adjacent to either or . Consequently,
Since both degrees are at most , we obtain
Thus each of and is adjacent to leaves, so is isomorphic to .
Conversely, the twin-star has exactly leaves, which completes the proof. □
This characterization shows that the twin-star hypothesis can be established by finding, within each weak-equivalence class of cycle-free -partitions, a component with leaves.
An extremal component
In this section, we establish a general lower bound for the number of leaves of a suitable component of a cycle-free -partition. Our approach is to choose a component with as many leaves as possible and, among such components, with as few branch vertices as possible. We then use weak equivalence to rule out certain configurations, thereby restricting the structure of this component.
Throughout this section, let and let be a cycle-free -partition of . We first give the following definition.
Definition 3.1. A spanning tree is called an extremal component of if it occurs as a component of a cycle-free -partition weakly equivalent to and satisfies the following conditions:
(E1) is maximal among all components of all partitions weakly equivalent to ,
(E2) is minimal among the components satisfying (E1).
Since there are only finitely many cycle-free -partitions of , an extremal component exists. Let be one of such component and fix a weakly equivalent partition containing . After permuting the components if necessary, we may assume that .
We now establish some properties of the component . The first shows that a degree-2 vertex of cannot lie between two non-leaf vertices.
Lemma 3.2. Every degree-2 vertex of the extremal component is adjacent to a leaf.
Proof. Let satisfy , and write . Suppose that neither nor is a leaf. Since is a tree, . We apply the triangle involution . On this triangle, the component contains the edges and , so after the involution one of these edges is replaced by . Consequently, becomes a leaf, while neither nor becomes a leaf. The new -th component therefore has one more leaf than , contradicting (E1). □
An immediate consequence of Lemma 3.2 is that degree-2 vertices of cannot be adjacent.
Corollary 3.3. Two degree-2 vertices of the extremal component cannot be adjacent.
Proof. Suppose that are adjacent and satisfy . We write
By Lemma 3.2, the vertices and are leaves. Hence is a path in . Since , are leaves and , have degree 2, none of these four vertices is adjacent to any vertex outside this path. Thus the path is a connected component of , which is impossible because is connected and has vertices. □
By Lemma 3.2 and Corollary 3.3, every degree-2 vertex of is adjacent to exactly one leaf and one branch vertex. In particular, no degree-2 vertex of lies between two branch vertices. This leads to the following terminology.
Definition 3.4. A pendant path in a tree is a path of the form
In Definition 3.4, the leaf is called a terminal leaf and a leaf that is not a terminal leaf is called a direct leaf.
The next observation gives a restriction on how branch vertices can be connected in the component .
Lemma 3.5. A degree-3 branch vertex of the extremal component cannot have two branch neighbors.
Proof. Suppose that and that are two branch neighbors of as shown in Figure 3. Since is a tree, . We apply the involution . The component contains and , so one of these edges is replaced by . Thus becomes a degree-2 vertex. One of or gains one degree and the other retains its degree, so both remain branch vertices. No leaf is created or lost. The resulting -th component therefore has the same number of leaves as but one fewer branch vertex, contradicting (E2). □
Figure 3. A forbidden configuration of branch vertices in an extremal component.
Lemma 3.5 shows that the component can not have the configuration illustrated in Figure 3.
We now apply Corollary 2.6 to the terminal leaf of a pendant path in and use the extremal conditions to restrict its possible destinations.
Lemma 3.6. If the extremal component satisfies , then
Proof. We choose a pendant path in as in (2). By Corollary 2.6, the terminal leaf has at least possible destinations.
A destination cannot be a non-leaf. Indeed, if the involution replaces by , where is a non-leaf, then becomes a new leaf, remains a leaf, and no old leaf is lost. This produces a component with more leaves than , contradicting (E1).
A destination also cannot be the terminal leaf of another pendant path . In that case, replacing by makes a leaf and a degree-2 vertex. Thus the numbers of leaves and branch vertices remain unchanged, so the resulting component is again extremal. However, and become adjacent degree-2 vertices, contradicting Corollary 3.3.
It follows that every successful destination is a leaf adjacent to a branch vertex. By Lemma 3.2 and Corollary 3.3, each degree-2 vertex is adjacent to exactly one leaf. Therefore, the number of direct leaves is . Moreover, since every destination of must be a direct leaf of , and there exists at least distinct destinations, we obtain
as required.
The proof of Lemma 3.6 also yields the following corollary.
Corollary 3.7. The extremal component satisfies that; if is the terminal leaf of a pendant path in , then every destination of is a direct leaf of .
We can now establish the main result of this section.
Theorem 3.8. The extremal component satisfies .
Proof. Suppose first that . By (1), we have
Since each branch vertex contributes at least 1 in the identity of Lemma 2.1, we have
Hence .
Suppose now that . By Lemma 3.6,
Using (1), this is equivalent to
On the other hand, Lemma 2.1 gives . Combining these inequalities, we obtain
and therefore
Since is an integer, it follows that .
Theorem 3.8, together with Lemma 2.7, shows that the extremal component satisfies
For , this leaves only three possibilities, which are . By Lemma 2.7, the case gives that is isomorphic to . Thus to establish Conjecture 1.3 for , it suffices to exclude the cases and . We consider these cases in the following sections.
Preliminary reductions for
We now specialize to cycle-free 5-partitions of . Before examining the six- and seven-leaf cases separately, we establish two results that are useful in both. Throughout this section, we denote by a cycle-free 5-partition of and choose a weakly equivalent partition whose component satisfies the extremal conditions (E1) and (E2) of Definition 3.1.
We first determine the possible degrees of the branch vertices in the two cases and .
Lemma 4.1. If , the possible branch-degree multisets are of type
If , the possible branch-degree multisets are of type
Proof. Suppose first that . Lemma 2.1 gives
By Lemma 2.2, every branch degree is at most 5, so the summands belong to . The possible decompositions are
corresponding to , , , and branch-degree multisets, respectively. The last case is impossible; indeed, this case has the property that and which implies that by (1). Therefore, the four branch vertices induce a tree. One of the branch vertices must have at least two branch neighbors, contradicting Lemma 3.5.
Suppose now that . Since has only three non-leaf vertices, , and Lemma 2.1 yields
The only decompositions of 5 into at most three summands from are , , and . These give the stated multisets.
The following result is used to exclude the configurations and in the six- and seven-leaf cases, respectively.
Lemma 4.2. Suppose that and are nonadjacent degree-3 branch vertices of , with leaf neighbors at and at , as illustrated in Figure 5. Then such a configuration is impossible.
Proof. Observe first that transferring either or from to , or either or from to , would preserve the number of leaves and decrease the number of branch vertices of . Indeed, the vertex losing the leaf would have degree 2, while the other would have degree 4. Thus none of these transfers is possible, by (E2).
Since and are nonadjacent in , the five edges
belong to the other four components. We show that these five edges must belong to different components.
First, cannot belong to the same component as any of the other four edges. For instance, if and belonged to the same component, then Lemma 2.3 would imply that the involution transfers the leaf from to , contradicting (E2). The same argument applies to the other three edges.
Now suppose that two of the four edges
belong to the same component , where . Recall that . By interchanging and and relabeling their leaf neighbors if necessary, we may assume that and that either or also belongs to .
We apply the involution to the original partition and denote the resulting partition by . Since transferring the leaf from to would contradict (E2), Lemma 2.3 implies that the involution leaves the fifth component unchanged and exchanges the component memberships of and . In particular,
If , then as well, since the involution does not involve this edge. Thus and belong to the same component . By Lemma 2.3, the involution transfers the leaf from to in the fifth component , contradicting (E2).
Similarly, if , then . Since also belongs to , the involution transfers the leaf from to in , again contradicting (E2).
Therefore, the four edges must belong to different components. Together with the first part of the proof, this shows that all five edges belong to different components among , which is impossible. □
Figure 5. Two nonadjacent degree-3 branch vertices with two leaf neighbors each and .
In the next section, we turn to the particular case where .
The six-leaf case
In this section, we still consider to be a cycle-free 5-partition of and choose a weakly equivalent partition whose component satisfies the extremal conditions (E1) and (E2). We focus on the case where and show that this is not possible. By Lemma 4.1, there are only three possible branch-degree multisets: , , and . We start with the following lemma.
Lemma 5.1. Suppose and . Then the terminal leaf of either pendant path can be transferred to every leaf adjacent to a branch vertex.
Proof. There are exactly leaves adjacent to branch vertices. By Corollary 2.6, the terminal leaf of either pendant path has at least destinations. From Corollary 3.7, neither a non-leaf nor the terminal leaf of the other pendant path can be a destination. Thus all four leaves adjacent to branch vertices are destinations.
The branch-degree multiset 5,3
Lemma 5.2. If the extremal component satisfies , then cannot have branch-degree multiset .
Proof. Suppose that and are the two branch vertices, with and , as shown in Figure 6. They must be adjacent: otherwise the path joining them would contain a degree-2 vertex adjacent to no leaf, contrary to Lemma 3.2. Since and , equation (1) gives . Hence has exactly two pendant paths.
By Lemma 5.1, we may successively relocate the two pendant paths so that both are based at . After relabeling, the two paths have the form
, and .
We apply the triangle involution . The component contains and , but not . Replacing by would raise the degree of from 5 to 6, contradicting Lemma 2.2. Hence the involution replaces by . In the resulting fifth component, has degree 2 and is adjacent to the non-leaves and . As shown in Figure 6, the component still has six leaves and two branch vertices, so it remains extremal, but violates Lemma 3.2.
Figure 6. The involution creates a degree-2 vertex with no leaf neighbor.
The branch-degree multiset 4,3,3
Lemma 5.3. If the extremal component satisfies , then cannot have branch-degree multiset .
Proof. Here , so (1) gives . By Lemma 3.5, the degree-4 vertex must be the middle vertex. We may therefore write
Since , there is a unique pendant path.
We show that, after passing to a weakly equivalent partition, we may assume that the unique pendant path is based at , as illustrated in Figure 7.
Figure 7. The extremal component with branch-degree multiset .
If the pendant path is already based at , there is nothing to prove. Otherwise, after interchanging and if necessary, we can write it as , where is the terminal leaf. The remaining five leaves are adjacent directly to branch vertices. By Corollary 2.6 and 3.7, at least four of these five leaves receive . Since has two direct leaf neighbors, at least one is a destination. Transferring to this leaf moves the pendant path from to , without changing the numbers of leaves or branch vertices. Thus the resulting component remains extremal and has the configuration shown in Figure 7.
We may thus assume that the unique pendant path is based at . Consequently, each of and has exactly two leaf neighbors. Lemma 4.2 excludes this configuration. □
The branch-degree multiset 4,4
The remaining case requires us to track the components containing certain edges outside . To do this, we first choose a convenient form for the component of .
Lemma 5.4. If the extremal component satisfies and the branch-degree multiset of is , then after passing to a weakly equivalent partition, we may assume that
Thus have degree , the vertices have degree , and are leaves, as shown in Figure 8.
Figure 8. A convenient form of the extremal six-leaf component with branch-degree multiset .
Proof. Since and , equation (1) gives . The two branch vertices are adjacent, because no degree-2 vertex lies between two branch vertices. By Lemma 5.1, we can successively relocate the pendant paths so that both are based at the same branch vertex, say . At each step, the number of leaves and branch vertices is preserved, so the resulting fifth component remains extremal. Relabeling the vertices gives (3). □
We now consider the component as in Figure 8. The next lemma shows that the edges , , , and belong to four distinct components and, more importantly, that their component memberships can be permuted while remains unchanged.
Lemma 5.5. If the extremal component is as in Figure 8, then the four edges
, , , and
belong to four different components among . Moreover, for any ordering of , there exists a finite sequence of triangle involutions producing a partition such that and
.
All these involutions involve only the vertices .
Proof. Since none of the four edges belongs to , we write
where . We first show that these indices are pairwise distinct.
Consider the involution . The only edge of this triangle belonging to is . Replacing it by would create an additional leaf, contradicting (E1), while replacing it by would isolate . Hence the involution leaves unchanged and exchanges and , which forces .
Similarly, the involution cannot replace by , since this would isolate . Replacing by would preserve the number of leaves and branch vertices but create adjacent degree-2 vertices and , contradicting Corollary 3.3. Thus remains unchanged, and and are exchanged, forcing .
The same reasoning applied to the involutions and shows that both leave unchanged and exchange with , and with , respectively. Consequently,
We now prove that and . First, apply the involution to the original partition and denote the result by . This involution leaves unchanged and exchanges the component memberships of and . Hence
We then apply the involution to this new partition. Since it must also leave unchanged, it exchanges the component memberships of and . These two edges must therefore belong to different components, giving .
To show that , we return to the original partition and apply the involution . Denote the resulting partition by . This involution leaves unchanged and exchanges the component memberships of and , so
Applying the involution to this partition, we again obtain an exchange of the component memberships of and while leaving unchanged. Consequently, these edges must belong to different components, and hence .
Therefore are pairwise distinct, and hence .
Finally, the involutions , , , and exchange the component memberships of the following pairs of edges respectively:
These exchanges generate the symmetric group , so every permutation of the component memberships of the four edges can be realized. Since each involution leaves unchanged, the same holds for any finite sequence of these involutions. □
A consequence of Lemma 5.5 is the following result.
Corollary 5.6. If the extremal component is as in Figure 8, then the edges
belong to four different components among .
Proof. Suppose first that and belong to the same component. By Lemma 2.3, the involution replaces by in . This makes a new leaf while remains a leaf, contradicting (E1). Hence and belong to different components. Similarly, and belong to different components.
Now suppose that and belong to the same component , where and . The edge is one of the four edges considered in Lemma 5.5. By that lemma, we can apply a sequence of involutions to obtain a partition such that and . Since none of these involutions involves , the edges and remain in the -th component. Consequently, the three edges , , and form a cycle in , contradicting the fact that is a tree. Therefore all four edges belong to different components.
We are now ready to exclude the six-leaf branch-degree multiset .
Lemma 5.7. If the extremal component satisfies , then cannot have branch-degree multiset .
Proof. We recall that is as in Figure 8. By Corollary 5.6, the edges , , , and belong to four different components among . The five edges incident with but not contained in are exactly
Consequently, there is a unique such that and lie in the same component.
We show that, after passing to a weakly equivalent partition, we may assume that is a pendant path in , while and remain in the same component.
Suppose first that . If , Lemma 5.1 allows us to transfer the terminal leaf of the pendant path to the direct leaf . This produces the pendant path , as desired. The case is identical.
Suppose now that . If , we first apply the involution . The component contains and , but not . Replacing by would increase the number of leaves to seven, contradicting (E1). Hence the involution replaces by , transforming the pendant path into . The vertex is now the terminal leaf, and Lemma 5.1 allows us to transfer it to , producing the pendant path . The case follows in the same way.
In each case, the involutions preserve the number of leaves and branch vertices, so the resulting fifth component remains extremal. Moreover, none of these involutions involves . Consequently, the edges and retain their original component memberships and therefore still belong to the same component.
We have thus obtained a weakly equivalent partition whose fifth component contains the pendant path , with and belonging to the same component. By Lemma 2.3, the involution transfers the terminal leaf from to . As a result, becomes a new leaf while remains a leaf, increasing the number of leaves of the fifth component to seven. This contradicts (E1) and completes the proof. □
Therefore, we get the following result.
Proposition 5.8. The extremal component satisfies .
In the next section, we show that the case is not possible.
The seven-leaf case
Here, we still consider to be a cycle-free 5-partition of and choose a weakly equivalent partition whose component satisfies the extremal conditions (E1) and (E2). By Proposition 5.8, the extremal component has at least seven leaves. If it has eight leaves, then is isomorphic to by Lemma 2.7. We therefore suppose throughout this section that and show that this is impossible. By Lemma 4.1, the only possible branch-degree multisets are
We consider them in this order.
The branch-degree multiset 5,3,3
Lemma 6.1. If the extremal component satisfies , then cannot have branch-degree multiset .
Proof. Since and , equation (1) gives . Thus the three branch vertices induce a path. By Lemma 3.5, the middle vertex of this path cannot have degree 3. Hence, after relabeling if necessary, we may write
In particular, each of and has exactly two leaf neighbors, while has exactly three. This configuration is shown in Figure 9. Lemma 4.2 shows that this configuration is not possible.
Figure 9. The extremal component in the case with branch-degree multiset .
The branch-degree multiset 4,4,3
Lemma 6.2. If the extremal component satisfies , then cannot have branch-degree multiset .
Proof. Here, we have that , so the three branch vertices form a path. Its middle vertex cannot have degree 3, by Lemma 3.5. Therefore, after relabeling, we write as
with
The configuration is shown in Figure 10. The five edges
Figure 10. The seven-leaf configuration with branch degrees .
do not belong to . We write
where . We prove that these indices are pairwise distinct. First, and . Indeed, if , then and belong to the same component. By Lemma 2.3, the involution transfers the leaf from to . This preserves the number of leaves and decreases the number of branch vertices, contradicting (E2). The same argument with in place of gives .
We now apply the involution to the original partition. Since transferring to would contradict (E2), this involution leaves unchanged and exchanges the component memberships of and . Thus now belongs to the -th component, while still belongs to the -th component. If , the involution would transfer the leaf from to , again contradicting (E2). Hence .
Moreover, the involutions and exchange the component memberships of with those of and , respectively, while leaving unchanged. These exchanges correspond to the transpositions and , which generate the symmetric group . Consequently, starting from the original partition, we can arrange for to belong to any one of the components , without changing or the component memberships of and .
Let . Choose such a partition with
We apply the involution . Since replacing by would produce a component with branch-degree multiset , which is impossible by Lemma 6.1, the involution must replace by . Denote the resulting partition by and put . Then has branch path , with degrees , respectively, as in Figure 11 and
Figure 11. The component with branch path .
Transferring either leaf or from to would preserve the seven leaves and decrease the number of branch vertices from three to two, contradicting (E2). Therefore, Lemma 2.3 gives
Since was arbitrary in , we obtain
It remains to show that . Suppose otherwise. We apply the involution to the partition . Since transferring from to is forbidden, the involution leaves unchanged and exchanges the component memberships of and . Thus now belongs to the -th component, which also contains because . By Lemma 2.3, the involution would then transfer the leaf from to , contradicting (E2). Hence .
Hence are five pairwise distinct elements of , which is impossible.
The branch-degree multiset
It remains to exclude the case where the branch-degree multiset is . In this case there are two branch vertices and one degree-2 vertex. We first choose labels that make it easy to follow the possible transfers of the terminal leaf.
Put
The branch-degree multiset 5,4
and set
For , let be the tree defined by
Thus consists of the eight fixed edges in and one edge joining the leaf 9 to . The vertices in are adjacent to 1, whereas 3, 5, 7 are adjacent to 2. Figure 12 shows as an example. If the edge is replaced by , the resulting tree is isomorphic to .

Figure 12. The tree .
Lemma 6.3. Up to weakly equivalent partition, we may assume that for some .
Proof. Let be the branch vertices, with and . By (1), , hence the unique degree-2 vertex belongs to a pendant path based at or . If the path is based at , we obtain the required form by relabeling.
Suppose instead that the path is based at . Then has four direct leaf neighbors and has two. By Corollary 2.6 and 3.7, the terminal leaf has at least four destinations among these six direct leaves. Therefore at least one direct leaf at receives it. The transfer moves the pendant path from to and preserves the numbers of leaves and branch vertices, so the resulting component is still extremal. Relabeling gives for some .
Our next goal is to show that, while the eight edges of stay in the fifth component, the leaf 9 can be attached at several different vertices of . The following two lemmas make this precise.
Lemma 6.4. Suppose that for some , and assume that no cycle-free 5-partition weakly equivalent to has a component isomorphic to . Let be the set of vertices for which a sequence of triangle involutions, changing only the attachment of the leaf 9 in the fifth component and keeping all edges of fixed, produces a partition with fifth component . Then .
Proof. Clearly . Suppose that , and fix . We consider the weakly equivalent partition whose fifth component is . Choose three distinct vertices .
If , then and . Put . None of the edges , , belongs to , and
Therefore, Lemma 2.5 implies that some vertex in receives the leaf 9. That vertex cannot be 2, since this would produce . Hence one of belongs to , which is a contradiction.
If , the same argument applies with . The vertex 1 cannot receive the leaf: it already has degree 5 in , so receiving 9 would violate Lemma 2.2. Thus one of must receive the leaf, again contradicting their choice. It follows that .
We now show that if the edges and , for some , belong to the same component, then the partition is weakly equivalent to one whose fifth component is .
Lemma 6.5. Suppose that for some . If there exist and such that
then the partition is weakly equivalent to one whose fifth component is .
Proof. If , the involution transfers the leaf 9 from to 2, by Lemma 2.3, and we are done. Suppose that , and assume by contradiction that no weakly equivalent partition contains .
Let . Since and both belong to , we have , or else these three edges would form a cycle in . We write . For each , let be the number of vertices for which . The six edges from to lie outside and are distributed among the four components $\Gamma_1,\ldots,\Gamma_4. Thus
We first prove that
We consider the possible destinations of the leaf 9, which is initially attached to the vertex . By Corollary 2.6, the leaf 9 has at least four destinations. The vertices eligible to receive it are those in , together with one additional vertex: 2 if , or 1 if . The additional vertex cannot receive 9, because the result would be in the first case and would violate the degree bound in the second.
We also show that cannot receive 9. Indeed, if the involution transfers the leaf 9 from to , then the edges and remain in . By Lemma 2.3, the involution would then transfer the leaf 9 from to 2, producing , which is again a contradiction.
Consequently, at least four vertices in receive the leaf 9. Together with its original attachment vertex , this gives at least five vertices in at which the leaf 9 can be attached. Moreover, each of these attachments can be obtained without involving in any involution. Hence the component memberships of all edges incident with remain unchanged.
Let be any of these five vertices. If , we transfer the leaf 9 from to by applying the involution . If , we make no change. We denote the resulting partition by . Then , and since the transfer does not involve , the edges incident with retain their original component memberships. In particular,
We show that belongs to neither nor . If , then and belong to the same component. By Lemma 2.3, the involution transfers the leaf 9 from to . The involution then transfers it from to 2, producing , which is a contradiction.
Suppose instead that . Applying the involution to the partition , it either transfers the leaf 9 to , leading to the same contradiction, or it leaves unchanged and exchanges the component memberships of and . In the latter case, the edges
all belong to the same component, forming a cycle which is again a contradiction.
Therefore, for each of these five vertices , the edge belongs to neither nor . Since contains exactly six vertices, at most one of the six edges joining to these vertices can belong to or . Hence
as required.
By (5) and (6), we have . After interchanging and if necessary, we may assume that .
Recall that there are five vertices in to which the leaf 9 can be attached. Since and contains six vertices, at least two of these five vertices are joined to by an edge of . Choose one such vertex .
If , we apply the involution to transfer the leaf 9 from to ; otherwise, we make no change. We denote the resulting partition by . Then , and since the transfer does not involve , we still have
and
We now apply the involution to the partition . If it transfers the leaf from to , then the involution transfers from to , producing , which is a contradiction.
Otherwise, let denote the resulting partition. By Lemma 2.3, the involution leaves unchanged and exchanges the component memberships of and . Consequently,
while
Among the six edges with , only changes component membership, moving from to . Thus, if denotes the number of these edges belonging to , then
On the other hand, the argument used to establish (6) applies to , with playing the role previously played by . Indeed, now belongs to , while and still belong to . The same argument therefore gives , which is a contradiction. This completes the proof. □
We are now ready to prove that the partition is weakly equivalent to a partition whose fifth component is .
Lemma 6.6. Suppose that for some . Then the partition is weakly equivalent to one whose fifth component is .
Proof. The five edges
are precisely the edges incident with that do not belong to . Since , each of the other four components contains at least one of these five edges. Consequently, exactly one of contains two of them, while each of the remaining three contains one.
If belongs to the component containing two edges, then there exist and such that
The conclusion then follows from Lemma 6.5.
We may therefore assume that there exist distinct and distinct such that
Suppose, for a contradiction, that no partition weakly equivalent to contains a component isomorphic to . Let be the set defined in Lemma 6.4.
We first show that neither nor belongs to . Suppose that . By Lemma 6.4, we can transfer the leaf from to through a sequence of involutions that keeps the eight edges of in the fifth component. We denote the resulting partition by . Since none of these involutions involves , we have
We now apply the involution . If it transfers the leaf from to , the resulting fifth component is , contrary to our assumption. Otherwise, by Lemma 2.3, the involution leaves unchanged and exchanges the component memberships of and . Thus, in the resulting partition , we have
Lemma 6.5 then applies and gives a contradiction. The same argument applies if . Hence
Since , with , and , we conclude that
We write , and let
By the distribution of the five edges in (7), the indices are pairwise distinct. Moreover, , since otherwise the edges , , and would form a cycle in . We now exclude the three remaining possibilities for the component containing .
Suppose first that . We apply the involution and denote the resulting partition by . Since and belong to , while belongs to , the involution replaces one of or in by . Thus one of these two edges moves into , which still contains . The fifth component remains . Lemma 6.5 therefore applies to the resulting partition, giving a contradiction.
Suppose next that . Since , we can transfer the leaf from to , keeping the edges of in the fifth component. Denote the resulting partition by . Every intermediate attachment vertex belongs to , which contains neither nor . Furthermore, none of these transfers involves . Consequently,
while
We apply the involution to this partition. Since and belong to , while belongs to , the involution moves one of or into the -th component, leaving unchanged. After interchanging and if necessary, we may assume that moves into that component. Thus, writing for the resulting partition, we have
We now apply the involution . If it transfers the leaf $9$ from to , the resulting fifth component is , which is a contradiction. Otherwise, Lemma 2.3 implies that the involution leaves unchanged and exchanges the component memberships of and $(2,9). Hence, in the resulting partition , we have
Applying Lemma 6.5 again gives a contradiction.
Finally, if , we repeat the preceding argument with in place of and in place of . This also leads to a contradiction. Therefore belongs to none of the five components , which is a contradiction. Hence the partition is weakly equivalent to one whose fifth component is . □
Therefore, we have the following Corollary.
Corollary 6.7. If the extremal component satisfies , then cannot have branch-degree multiset .
Proof. By Lemma 6.3, after weak equivalence, we may assume that for some . Lemma 6.6 gives a weakly equivalent partition whose fifth component is . Since has eight leaves, this contradicts the maximality in (E1). □
Having excluded all three possible branch-degree multisets for an extremal component with seven leaves, we can now establish our main result.
Theorem 6.8. Conjecture 1.3 holds for .
Proof. Let be a cycle-free 5-partition of . Let be an extremal component of as in Definition 3.1. Thus is weakly equivalent to a partition with . By Theorem 3.8 and Lemma 2.7, we have
Proposition 5.8 and Lemmas 6.1, 6.2 together with Corollary 6.7 exclude the cases and . Hence , and Lemma 2.7 implies that is isomorphic to . Therefore, is weakly equivalent to a cycle-free 5-partition containing a component isomorphic to , proving Conjecture 1.3 for . □
As a consequence of Theorem 6.8, we obtain the following uniqueness result for the determinant-like map in dimension 5.
Corollary 6.9. The determinant-like map is unique up to multiplication by a scalar.
Proof. By Theorem 6.8 and the previously established cases , the twin-star hypothesis holds for every . Hence Conjecture 1.1 holds for by [6]. The uniqueness of then follows from the equivalence established in [10]. □
Conclusion
One of the main difficulties in studying cycle-free -partitions of is that triangle involutions affect the distribution of edges among different components, making it difficult to control the entire partition simultaneously. Our approach addresses this difficulty by focusing on a single extremal component and examining the remaining components only when necessary. This approach could potentially be extended to higher dimensions, although, in its present form, it would require treating each dimension separately. This leads to a natural question: Question: Can the twin-star hypothesis be established in all dimensions through a uniform extremal approach?
One possible direction is to refine the extremal conditions (E1) and (E2) of Definition 3.1, for instance, by also maximizing the number of pendant paths attached to a single branch vertex or by imposing additional restrictions on the degrees of branch vertices. Although such refinements were not necessary for , they may provide further structural information toward a proof of the twin-star hypothesis in general.
Acknowledgments. The authors would like to thank Mihai D. Staic for insightful discussions and valuable suggestions.
DEPARTMENT OF MATHEMATICS AND STATISTICS, BOWLING GREEN STATE UNIVERSITY, BOWLING GREEN, OH 43403, USA
Email address: nyadjoп@bgsu.edu
References
- [1]P. Bose, F. Hurtado, E. Rivera-Campo, and D. R. Wood, Partitions of complete geometric graphs into plane trees, Comput. Geom. 34 (2006), 116–125.
- [2]R. A. Brualdi and S. Hollingsworth, Multicolored trees in complete graphs, J. Combin. Theory Ser. B 68 (1996), 310–313.DOI
- [3]S. M. Cioaba and P. J. Cameron, A graph partition problem, Amer. Math. Monthly 122 (2015), 972–982.
- [4]D. Froncek, Bi-cyclic decompositions of complete graphs into spanning trees, Discrete Math. 307 (2007), 1317–1322.DOI
- [5]D. Froncek, P. Kovar, and M. Kubesa, Factorizations of complete graphs into trees with at most four non-leave vertices, Graphs Combin. 27 (2011), 621–646.DOI
- [6]M. J. Fyfe, S. R. Lippold, P. Nyadjo Fonga, M. D. Staic, and A. Stancu, Twin-star hypothesis and cycle-free d-partitions of K₂d, arXiv:2407.13959v2, 2026.arxiv.org/abs/2407.13959
- [7]S. Glock, D. Kühn, R. Montgomery, and D. Osthus, Decompositions into isomorphic rainbow spanning trees, J. Combin. Theory Ser. B 146 (2021), 439–484.arxiv.org/abs/1903.04262
- [8]P. Kovar, M. Kubesa, and M. Meszka, Factorizations of complete graphs into brooms, Discrete Math. 312 (2012), 1084–1093.DOI
- [9]M. Kubesa, Spanning tree factorizations of complete graphs, J. Combin. Math. Combin. Comput. 52 (2005), 33–49.
- [10]S. R. Lippold, M. D. Staic, and A. Stancu, Edge partitions of the complete graph and a determinant-like function, Monatsh. Math. 198 (2022), 819–858.arxiv.org/abs/2102.09422
- [11]G. Mazzuoccolo and G. Rinaldi, Rainbow spanning tree decompositions in complete graphs colored by cyclic 1-factorizations, Discrete Math. 342 (2019), 1006–1016.DOI
- [12]M. D. Staic, Existence of the detˢ² map, Bull. Lond. Math. Soc. 55 (2023), no. 4, 1685–1699.DOI
- [13]M. D. Staic, The exterior graded Swiss-Cheese operad Λˢ²ᵥ, Comm. Algebra 51 (2023), no. 7, 2705–2728.DOI
- [14]M. D. Staic, The r-equilibrium problem, Linear Multilinear Algebra 73 (2025), no. 15, 3421–3433.
- [15]M. D. Staic and J. Van Grinsven, A geometric application for the map detˢ², Comm. Algebra 50 (2022), no. 3, 1106–1117.









