betaFeedback

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 det⁡S2\det^{S^2} is unique up to multiplication by a scalar is equivalent to a combinatorial conjecture regarding cycle-free dd-partitions of the complete graph K2dK_{2d}, known as the twin-star hypothesis. This hypothesis asserts that every cycle-free dd-partition of K2dK_{2d} is weakly equivalent to one that contains a component isomorphic to the twin-star graph TSdTS_d. This hypothesis was previously established for d≤4d\le4. In the present paper, we prove it for d=5d=5. Consequently, the associated determinant-like map det⁡S2\det^{S^2} is unique up to a scalar in dimension 55.

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 d≥2d \ge2 be an integer, and let K2dK_{2d} denote the complete graph on 2d2d vertices. A cycle-free dd-partition of K2dK_{2d} is an ordered dd-tuple

P=(Γ1,…,Γd)\mathcal{P} = (\Gamma_1, \ldots, \Gamma_d)

of cycle-free spanning subgraphs whose edge sets are pairwise disjoint and together contain every edge of K2dK_{2d}. Since K2dK_{2d} has d(2d−1)d(2d - 1) edges and each cycle-free spanning subgraph has at most 2d−12d - 1 edges, every component Γi\Gamma_i must have exactly 2d−12d - 1 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 dd-partition P\mathcal{P} and three distinct vertices xx, yy, zz of K2dK_{2d}, they proved that there exists a unique cycle-free dd-partition P(x,y,z)\mathcal{P}^{(x,y,z)} which agrees with P\mathcal{P} on every edge outside the triangle with vertices xx, yy, zz, but differs from P\mathcal{P} on at least two of the three edges of this triangle. Moreover, the transformation

P⟼P(x,y,z)\mathcal{P} \longmapsto\mathcal{P}^{(x,y,z)}

is an involution, called the triangle involution (x,y,z)(x,y,z), or simply the involution (x,y,z)(x,y,z).

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 dd-partitions of K2dK_{2d}.

Two cycle-free dd-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 dd-partitions of K2dK_{2d} are involution equivalent.

Conjecture 1.1 was established for d=3d=3 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 dd-partitions of K2dK_{2d} are said to be weakly equivalent if, after possibly relabeling the vertices of K2dK_{2d} 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 TSdTS_d. It consists of two adjacent vertices of degree dd, each joined to d−1d-1 leaves. Thus TSdTS_d is a tree on 2d2d vertices with exactly 2d−22d-2 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 TSdTS_d, with 2d2d vertices.

Conjecture 1.3. Every cycle-free dd-partition of K2dK_{2d} is weakly equivalent to one containing a component isomorphic to TSdTS_d.

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 1≤i≤d1\leq i\leq d, then Conjecture 1.1 also holds. Using this reduction, the authors of [6] established the case d=4d=4, extending the previously known cases d=1d=1, d=2d=2 and d=3d=3. 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 ΛVdS2\Lambda^{S^2}_{V_d} introduced by Staic in [13]. Let kk be a field and let VdV_d be a dd-dimensional vector space over kk. 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

det⁡S2:Vd⊗2d(2d−1)⟶k\det^{S^2}: V_d^{\otimes2d(2d-1)} \longrightarrow k

satisfying the following vanishing condition:

det⁡S2(⨂1≤i<j≤2dvi,j)=0\det^{S^2}\left(\bigotimes_{1\leq i<j\leq2d} v_{i,j}\right)=0

whenever there exist three indices 1≤x<y<z≤2d1\leq x<y<z\leq2d such that

vx,y=vx,z=vy,z.v_{x,y}=v_{x,z}=v_{y,z}.

The connection between this algebraic construction and the combinatorial structure of K2dK_{2d} was developed in [10], where the uniqueness problem for det⁡S2\det^{S^2} was shown to be equivalent to Conjecture 1.1.

The existence of det⁡S2\det^{S^2} for arbitrary dd 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 d=5d=5, a cycle-free 5-partition P\mathcal{P} of K10K_{10} consists of five spanning trees, each having 9 edges. The twin-star TS5TS_5 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 K10K_{10} is weakly equivalent to one containing a component isomorphic to TS5TS_5, thereby establishing Conjecture 1.3 for d=5d=5. Since the twin-star hypothesis is already known for 1≤d≤41\le d\le4, our result also establishes Conjecture 1.1 for d=5d=5. Consequently, the corresponding map

det⁡S2:V5⊗45⟶k\det^{S^2}: V_5^{\otimes45} \longrightarrow k

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 dd-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 d+1d+1 leaves; see Theorem 3.8. In § 4, we specialize to d=5d=5 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 TS5TS_5. 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 HH be a graph. We denote its vertex and edge sets by V(H)V(H) and E(H)E(H), respectively. An edge joining two vertices uu and vv is denoted by (u,v)(u,v). We write dH(v)d_H(v) for the degree of a vertex vv in HH and NH(v)N_H(v) for the set of its neighbors. We also use the notation

u0−u1−⋯−umu_0-u_1-\cdots-u_m

to denote a path with consecutive vertices u0,u1,…,umu_0,u_1,\ldots,u_m.

We refer to vertices of degree at least 3 as branch vertices and we use the notations

ℓ(H)=number of leaves of H,\ell(H)=\text{number of leaves of }H,
p(H)=number of vertices of degree 2 of H,p(H)=\text{number of vertices of degree 2 of }H,
b(H)=number of branch vertices of H.b(H)=\text{number of branch vertices of }H.

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

ℓ(H)+p(H)+b(H)=∣V(H)∣.(1)\ell(H)+p(H)+b(H)=|V(H)|. \tag*{(1)}

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 HH with at least two vertices,

ℓ(H)=2+∑dH(v)≥3(dH(v)−2).\ell(H) = 2 + \sum_{d_H(v)\ge3} (d_H(v)-2).

Proof. Since HH is a tree, we have that

∑v∈V(H)dH(v)=2(∣V(H)∣−1),\sum_{v\in V(H)} d_H(v) = 2(|V(H)|-1),

and consequently

∑v∈V(H)(dH(v)−2)=−2.\sum_{v\in V(H)} (d_H(v)-2) = -2.

Splitting the sum according to vertex degree, we obtain

−ℓ(H)+∑dH(v)≥3(dH(v)−2)=−2,-\ell(H) + \sum_{d_H(v)\ge3} (d_H(v)-2) = -2,

which gives the desired identity. □

Before studying the effect of triangle involutions on cycle-free dd-partitions of K2dK_{2d}, 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 T=(Λ1,Λ2)\mathcal{T}=(\Lambda_1,\Lambda_2) of K4K_4 defined by

E(Λ1)={(1,2),(2,3),(3,4)},E(Λ2)={(1,3),(1,4),(2,4)},E(\Lambda_1)=\{(1,2),(2,3),(3,4)\}, \qquad E(\Lambda_2)=\{(1,3),(1,4),(2,4)\},

as shown in Figure 1.

An illustration of the triangle involution (1, 2, 3) on the cycle-free 2-partition

Figure 1. An illustration of the triangle involution (1,2,3)(1,2,3) on the cycle-free 2-partition T=(Λ1,Λ2)\mathcal{T}=(\Lambda_1,\Lambda_2) of K4K_4.

We apply the involution (1,2,3)(1,2,3). Since the involution changes only the three edges of the triangle with vertices 1,2,31,2,3, the only possible nontrivial changes involve the edge (1,3)(1,3) and one of the edges (1,2)(1,2) or (2,3)(2,3). The edge (1,3)(1,3) cannot be exchanged with (1,2)(1,2), because this would give the second component the edge set

{(1,2),(1,4),(2,4)},\{(1,2),(1,4),(2,4)\},

which contains a cycle. Therefore this possibility is excluded. Since the involution is nontrivial, it follows that it must exchange the edges (2,3)(2,3) and (1,3)(1,3) between the two components. Thus, writing T(1,2,3)=(Δ1,Δ2)\mathcal{T}^{(1,2,3)}=(\Delta_1,\Delta_2), we obtain

E(Δ1)={(1,2),(1,3),(3,4)},E(Δ2)={(2,3),(1,4),(2,4)}.E(\Delta_1)=\{(1,2),(1,3),(3,4)\}, \qquad E(\Delta_2)=\{(2,3),(1,4),(2,4)\}.

Both resulting components are again spanning trees.

Let d≥2d \ge2 and let P=(Γ1,…,Γd)\mathcal{P} = (\Gamma_1,\ldots,\Gamma_d) be a cycle-free dd-partition of K2dK_{2d}. The fact that the components of a cycle-free dd-partition together contain every edge of K2dK_{2d} imposes a restriction on the degree of each vertex.

Lemma 2.2. For every vertex v∈V(K2d)v \in V(K_{2d}) and every 1≤i≤d1 \le i \le d, we have

1≤dΓi(v)≤d1 \le d_{\Gamma_i}(v) \le d.

Proof. The 2d−12d-1 edges incident with vv are distributed among the dd spanning trees Γ1,…,Γd\Gamma_1,\ldots,\Gamma_d, so

∑i=1ddΓi(v)=2d−1.\sum_{i=1}^{d} d_{\Gamma_i}(v) = 2d - 1.

Since each Γi\Gamma_i is connected, every summand dΓi(v)d_{\Gamma_i}(v) is at least 11. Hence, for any fixed j∈{1,…,d}j \in\{1,\ldots,d\},

dΓj(v)≤(2d−1)−(d−1)=d.d_{\Gamma_j}(v) \le(2d-1) - (d-1) = d.

The following lemma describes how an involution can change the attachment of a leaf in a component of the cycle-free dd-partition P\mathcal{P}.

Lemma 2.3. Let vv be a leaf of Γd\Gamma_d, with (a,v)∈E(Γd)(a,v) \in E(\Gamma_d), and suppose that (a,b)(a,b) and (b,v)(b,v) do not belong to E(Γd)E(\Gamma_d). Then the involution (a,b,v)(a,b,v) has one of the following two effects:

  1. It replaces (a,v)(a,v) by (b,v)(b,v) in Γd\Gamma_d.

  2. It leaves Γd\Gamma_d unchanged, in which case (a,b)(a,b) and (b,v)(b,v) belong to two different components and are exchanged by the involution.

In particular, if (a,b)(a,b) and (b,v)(b,v) belong to the same component, then the involution replaces (a,v)(a,v) by (b,v)(b,v) in Γd\Gamma_d.

Proof. Among the three edges of the triangle with vertices a,b,va,b,v, the component Γd\Gamma_d contains only (a,v)(a,v). If the involution changes Γd\Gamma_d, this edge must be replaced by either (a,b)(a,b) or (b,v)(b,v). The first possibility is impossible, since deleting the leaf edge (a,v)(a,v) isolates vv, while adding (a,b)(a,b) does not reconnect it. Thus the only possible change in Γd\Gamma_d is the replacement of (a,v)(a,v) by (b,v)(b,v).

If Γd\Gamma_d 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 HH be a component of a cycle-free dd-partition, and let vv be a leaf of HH adjacent to a vertex aa. For a vertex b∉{a,v}b \notin\{a,v\}, if the involution (a,b,v)(a,b,v) replaces the edge (a,v)(a,v) by (b,v)(b,v) in HH, we say that it transfers the leaf vv from aa to bb, or that bb receives the leaf vv. In this case, bb is called a destination of vv.

The following lemma provides a sufficient condition for the existence of such a destination for a leaf in Γd\Gamma_d. The particular case d=4d=4 was established in [6].

Lemma 2.5. Suppose that vv is a leaf of Γd\Gamma_d, with (a,v)∈E(Γd)(a,v) \in E(\Gamma_d), and let B⊆V(K2d)∖{a,v}B \subseteq V(K_{2d}) \setminus\{a,v\} satisfy (a,b)∉E(Γd)(a,b) \notin E(\Gamma_d) for every b∈Bb \in B. If ∣B∣≥d−dΓd(a)+1|B| \ge d-d_{\Gamma_d}(a)+1, then there exists b∈Bb \in B that receives the leaf vv.

Proof. Suppose, for a contradiction, that no vertex b∈Bb \in B receives the leaf vv. We fix b∈Bb \in B, and write

(a,b)∈E(Γr),(b,v)∈E(Γs),(a,b) \in E(\Gamma_r), \qquad(b,v) \in E(\Gamma_s),

for some r,s∈{1,…,d−1}r,s \in\{1,\ldots,d-1\}. By Lemma 2.3, we have r≠sr \ne s, and we apply the involution (a,b,v)(a,b,v) which leaves Γd\Gamma_d unchanged while exchanging (a,b)(a,b) and (b,v)(b,v).

Let Δr\Delta_r denote the new rr-th component. Then

E(Δr)=(E(Γr)∖{(a,b)})∪{(b,v)}.E(\Delta_r)=\left(E(\Gamma_r)\setminus\{(a,b)\}\right)\cup\{(b,v)\}.

Since both Γr\Gamma_r and Δr\Delta_r are trees, the edge (a,b)(a,b) lies on the unique path from bb to vv in Γr\Gamma_r. Since (a,b)(a,b) is incident with bb, this path has the form

b−a−⋯−v.b-a-\cdots-v.

Consequently, the unique path from aa to vv in Γr\Gamma_r does not start with (a,b)(a,b). This situation is illustrated in Figure 2.

Figure 2. The exchange of (a,b)(a,b) and (b,v)(b,v) between Γr\Gamma_r and Γs\Gamma_s.

Similarly, if Δs\Delta_s denotes the new ss-th component, then

E(Δs)=(E(Γs)∖{(b,v)})∪{(a,b)}.E(\Delta_s)=\left(E(\Gamma_s)\setminus\{(b,v)\}\right)\cup\{(a,b)\}.

Since Γs\Gamma_s and Δs\Delta_s are trees, the edge (b,v)(b,v) belongs to the unique path from aa to bb in Γs\Gamma_s. In particular, the path from aa to vv in Γs\Gamma_s does not start with (a,b)(a,b). The same is true for every other component Γi\Gamma_i, since none contains (a,b)(a,b).

Therefore, for every b∈Bb \in B, none of the d−1d-1 paths from aa to vv in Γ1,…,Γd−1\Gamma_1,\ldots,\Gamma_{d-1} can start with (a,b)(a,b).

There are 2d−12d-1 edges incident with aa and out of these, dΓd(a)d_{\Gamma_d}(a) belong to Γd\Gamma_d, while the ∣B∣|B| edges (a,b)(a,b) with b∈Bb \in B, are excluded as possible first edges of the paths above. Hence these d−1d-1 paths have at most

(2d−1)−dΓd(a)−∣B∣(2d-1)-d_{\Gamma_d}(a)-|B|

possible first edges. Since the components are edge-disjoint, the paths must start with d−1d-1 distinct edges. Therefore

(2d−1)−dΓd(a)−∣B∣≥d−1,(2d-1)-d_{\Gamma_d}(a)-|B| \ge d-1,

which gives

∣B∣≤d−dΓd(a),|B| \le d-d_{\Gamma_d}(a),

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 vv be a leaf of Γd\Gamma_d, with (a,v)∈E(Γd)(a,v) \in E(\Gamma_d). Among the vertices b∉{a,v}b \notin\{a,v\} satisfying (a,b)∉E(Γd)(a,b) \notin E(\Gamma_d), at least d−1d-1 receive the leaf vv.

Proof. Put m=dΓd(a)m=d_{\Gamma_d}(a). Among the 2d−22d-2 vertices different from aa and vv, exactly m−1m-1 are adjacent to aa in Γd\Gamma_d. Hence there are

(2d−2)−(m−1)=2d−m−1(2d-2)-(m-1)=2d-m-1

vertices b∉{a,v}b\notin\{a,v\} satisfying (a,b)∉E(Γd)(a,b)\notin E(\Gamma_d).

We now determine how many of these vertices fail to receive the leaf vv. By Lemma 2.5, every set of at least d−m+1d-m+1 such vertices contains a destination of vv. Therefore, the number of such vertices that fail to receive vv is at most d−md-m. Since there are 2d−m−12d-m-1 eligible vertices, at least

(2d−m−1)−(d−m)=d−1(2d-m-1)-(d-m)=d-1

of them receive the leaf vv. □

We conclude this section by recalling the following characterization of the twin-star graph TSdTS_d, established in [6]. We include a short proof for the convenience of the reader.

Lemma 2.7. Let HH be a component of a cycle-free dd-partition of K2dK_{2d}. Then

ℓ(H)≤2d−2.\ell(H)\le2d-2.

Moreover, ℓ(H)=2d−2\ell(H)=2d-2 if and only if, HH is isomorphic to TSdTS_d.

Proof. By Lemma 2.2, every vertex of HH has degree at most dd. If ℓ(H)=2d−1\ell(H)=2d-1, then HH is a star whose central vertex has degree 2d−1>d2d-1>d, which is a contradiction. Hence

ℓ(H)≤2d−2.\ell(H)\le2d-2.

Suppose now that ℓ(H)=2d−2\ell(H)=2d-2. Then HH has exactly two non-leaf vertices, say aa and bb. Since HH is connected, these vertices must be adjacent, and every other vertex is a leaf adjacent to either aa or bb. Consequently,

dH(a)+dH(b)=2d.d_H(a)+d_H(b)=2d.

Since both degrees are at most dd, we obtain

dH(a)=dH(b)=d.d_H(a)=d_H(b)=d.

Thus each of aa and bb is adjacent to d−1d-1 leaves, so HH is isomorphic to TSdTS_d.

Conversely, the twin-star TSdTS_d has exactly 2d−22d-2 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 dd-partitions, a component with 2d−22d - 2 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 dd-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 d≥3d \ge3 and let P\mathcal{P} be a cycle-free dd-partition of K2dK_{2d}. We first give the following definition.

Definition 3.1. A spanning tree HH is called an extremal component of P\mathcal{P} if it occurs as a component of a cycle-free dd-partition weakly equivalent to P\mathcal{P} and satisfies the following conditions:

(E1) ℓ(H)\ell(H) is maximal among all components of all partitions weakly equivalent to P\mathcal{P},

(E2) b(H)b(H) is minimal among the components satisfying (E1).

Since there are only finitely many cycle-free dd-partitions of K2dK_{2d}, an extremal component exists. Let TT be one of such component and fix a weakly equivalent partition (Γ1,…,Γd)(\Gamma_1,\ldots,\Gamma_d) containing TT. After permuting the components if necessary, we may assume that T=ΓdT = \Gamma_d.

We now establish some properties of the component TT. The first shows that a degree-2 vertex of TT cannot lie between two non-leaf vertices.

Lemma 3.2. Every degree-2 vertex of the extremal component TT is adjacent to a leaf.

Proof. Let v∈V(T)v \in V(T) satisfy dT(v)=2d_T(v) = 2, and write NT(v)={x,y}N_T(v) = \{x,y\}. Suppose that neither xx nor yy is a leaf. Since TT is a tree, (x,y)∉E(T)(x,y) \notin E(T). We apply the triangle involution (v,x,y)(v,x,y). On this triangle, the component T=ΓdT = \Gamma_d contains the edges (v,x)(v,x) and (v,y)(v,y), so after the involution one of these edges is replaced by (x,y)(x,y). Consequently, vv becomes a leaf, while neither xx nor yy becomes a leaf. The new dd-th component therefore has one more leaf than TT, contradicting (E1). □

An immediate consequence of Lemma 3.2 is that degree-2 vertices of TT cannot be adjacent.

Corollary 3.3. Two degree-2 vertices of the extremal component TT cannot be adjacent.

Proof. Suppose that u,v∈V(T)u,v \in V(T) are adjacent and satisfy dT(u)=dT(v)=2d_T(u) = d_T(v) = 2. We write

NT(u)={a,v},NT(v)={u,b}.N_T(u) = \{a,v\}, \qquad N_T(v) = \{u,b\}.

By Lemma 3.2, the vertices aa and bb are leaves. Hence a−u−v−ba-u-v-b is a path in TT. Since aa, bb are leaves and uu, vv have degree 2, none of these four vertices is adjacent to any vertex outside this path. Thus the path is a connected component of TT, which is impossible because TT is connected and has 2d≥62d \ge6 vertices. □

By Lemma 3.2 and Corollary 3.3, every degree-2 vertex of TT is adjacent to exactly one leaf and one branch vertex. In particular, no degree-2 vertex of TT lies between two branch vertices. This leads to the following terminology.

Definition 3.4. A pendant path in a tree HH is a path of the form

x−u−v,with dH(x)≥3,dH(u)=2,and dH(v)=1.(2)x-u-v,\qquad\text{with }d_H(x)\ge3,\qquad d_H(u)=2,\qquad\text{and }d_H(v)=1. \tag*{(2)}

In Definition 3.4, the leaf vv 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 TT.

Lemma 3.5. A degree-3 branch vertex of the extremal component TT cannot have two branch neighbors.

Proof. Suppose that dT(v)=3d_T(v)=3 and that x,yx,y are two branch neighbors of vv as shown in Figure 3. Since TT is a tree, (x,y)∉E(T)(x,y)\notin E(T). We apply the involution (v,x,y)(v,x,y). The component T=ΓdT=\Gamma_d contains (v,x)(v,x) and (v,y)(v,y), so one of these edges is replaced by (x,y)(x,y). Thus vv becomes a degree-2 vertex. One of xx or yy gains one degree and the other retains its degree, so both remain branch vertices. No leaf is created or lost. The resulting dd-th component therefore has the same number of leaves as TT 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 TT can not have the configuration illustrated in Figure 3.

We now apply Corollary 2.6 to the terminal leaf of a pendant path in TT and use the extremal conditions to restrict its possible destinations.

Lemma 3.6. If the extremal component TT satisfies p(T)≥1p(T)\ge1, then

ℓ(T)−p(T)≥d−1.\ell(T)-p(T)\ge d-1.

Proof. We choose a pendant path x−u−vx-u-v in TT as in (2). By Corollary 2.6, the terminal leaf vv has at least d−1d-1 possible destinations.

A destination cannot be a non-leaf. Indeed, if the involution replaces (u,v)(u,v) by (w,v)(w,v), where ww is a non-leaf, then uu becomes a new leaf, vv remains a leaf, and no old leaf is lost. This produces a component with more leaves than TT, contradicting (E1).

A destination also cannot be the terminal leaf ww of another pendant path y−z−wy-z-w. In that case, replacing (u,v)(u,v) by (w,v)(w,v) makes uu a leaf and ww a degree-2 vertex. Thus the numbers of leaves and branch vertices remain unchanged, so the resulting component is again extremal. However, ww and zz 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 ℓ(T)−p(T)\ell(T) - p(T). Moreover, since every destination of vv must be a direct leaf of TT, and there exists at least d−1d - 1 distinct destinations, we obtain

ℓ(T)−p(T)≥d−1,\ell(T) - p(T) \ge d - 1,

as required.

The proof of Lemma 3.6 also yields the following corollary.

Corollary 3.7. The extremal component TT satisfies that; if vv is the terminal leaf of a pendant path in TT, then every destination of vv is a direct leaf of TT.

We can now establish the main result of this section.

Theorem 3.8. The extremal component TT satisfies ℓ(T)≥d+1\ell(T) \ge d + 1.

Proof. Suppose first that p(T)=0p(T) = 0. By (1), we have

b(T)=2d−ℓ(T).b(T) = 2d - \ell(T).

Since each branch vertex contributes at least 1 in the identity of Lemma 2.1, we have

ℓ(T)≥2+b(T)=2+2d−ℓ(T).\ell(T) \ge2 + b(T) = 2 + 2d - \ell(T).

Hence ℓ(T)≥d+1\ell(T) \ge d + 1.

Suppose now that p(T)≥1p(T) \ge1. By Lemma 3.6,

ℓ(T)−p(T)≥d−1.\ell(T) - p(T) \ge d - 1.

Using (1), this is equivalent to

2ℓ(T)+b(T)≥3d−1.2\ell(T) + b(T) \ge3d - 1.

On the other hand, Lemma 2.1 gives b(T)≤ℓ(T)−2b(T) \le\ell(T) - 2. Combining these inequalities, we obtain

3ℓ(T)−2≥3d−1,3\ell(T) - 2 \ge3d - 1,

and therefore

3ℓ(T)≥3d+1.3\ell(T) \ge3d + 1.

Since ℓ(T)\ell(T) is an integer, it follows that ℓ(T)≥d+1\ell(T) \ge d + 1.

Theorem 3.8, together with Lemma 2.7, shows that the extremal component TT satisfies

d+1≤ℓ(T)≤2d−2.d + 1 \le\ell(T) \le2d - 2.

For d=5d = 5, this leaves only three possibilities, which are ℓ(T)∈{6,7,8}\ell(T) \in\{6, 7, 8\}. By Lemma 2.7, the case ℓ(T)=8\ell(T) = 8 gives that TT is isomorphic to TS5T_{S_5}. Thus to establish Conjecture 1.3 for d=5d = 5, it suffices to exclude the cases ℓ(T)=6\ell(T) = 6 and ℓ(T)=7\ell(T) = 7. We consider these cases in the following sections.

Preliminary reductions for d=5d=5

We now specialize to cycle-free 5-partitions of K10K_{10}. Before examining the six- and seven-leaf cases separately, we establish two results that are useful in both. Throughout this section, we denote by P\mathcal{P} a cycle-free 5-partition of K10K_{10} and choose a weakly equivalent partition (Γ1,…,Γ5)(\Gamma_1,\ldots,\Gamma_5) whose component T=Γ5T=\Gamma_5 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 ℓ(T)=6\ell(T)=6 and ℓ(T)=7\ell(T)=7.

Lemma 4.1. If ℓ(T)=6\ell(T)=6, the possible branch-degree multisets are of type

{5,3},{4,4},or{4,3,3}.\{5,3\},\qquad\{4,4\},\qquad\text{or}\qquad\{4,3,3\}.

If ℓ(T)=7\ell(T)=7, the possible branch-degree multisets are of type

{5,4},{5,3,3},or{4,4,3}.\{5,4\},\qquad\{5,3,3\},\qquad\text{or}\qquad\{4,4,3\}.

Proof. Suppose first that ℓ(T)=6\ell(T)=6. Lemma 2.1 gives

∑dT(v)≥3(dT(v)−2)=4.\sum_{d_T(v)\ge3}\bigl(d_T(v)-2\bigr)=4.

By Lemma 2.2, every branch degree is at most 5, so the summands belong to {1,2,3}\{1,2,3\}. The possible decompositions are

3+1,2+2,2+1+1,1+1+1+1,3+1,\qquad2+2,\qquad2+1+1,\qquad1+1+1+1,

corresponding to {5,3}\{5,3\}, {4,4}\{4,4\}, {4,3,3}\{4,3,3\}, and {3,3,3,3}\{3,3,3,3\} branch-degree multisets, respectively. The last case is impossible; indeed, this case has the property that ℓ(T)=6\ell(T)=6 and b(T)=4b(T)=4 which implies that p(T)=0p(T)=0 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 ℓ(T)=7\ell(T)=7. Since TT has only three non-leaf vertices, b(T)≤3b(T)\le3, and Lemma 2.1 yields

∑dT(v)≥3(dT(v)−2)=5.\sum_{d_T(v)\ge3}\bigl(d_T(v)-2\bigr)=5.

The only decompositions of 5 into at most three summands from {1,2,3}\{1,2,3\} are 3+23+2, 3+1+13+1+1, and 2+2+12+2+1. These give the stated multisets. □\square

The following result is used to exclude the configurations {4,3,3}\{4,3,3\} and {5,3,3}\{5,3,3\} in the six- and seven-leaf cases, respectively.

Lemma 4.2. Suppose that yy and zz are nonadjacent degree-3 branch vertices of TT, with leaf neighbors a,ba,b at yy and c,dc,d at zz, as illustrated in Figure 5. Then such a configuration is impossible.

Proof. Observe first that transferring either aa or bb from yy to zz, or either cc or dd from zz to yy, would preserve the number of leaves and decrease the number of branch vertices of TT. 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 yy and zz are nonadjacent in TT, the five edges

(y,z),(z,a),(z,b),(y,c),and (y,d)(y,z),\quad(z,a),\quad(z,b),\quad(y,c),\quad\text{and }(y,d)

belong to the other four components. We show that these five edges must belong to different components.

First, (y,z)(y,z) cannot belong to the same component as any of the other four edges. For instance, if (y,z)(y,z) and (z,a)(z,a) belonged to the same component, then Lemma 2.3 would imply that the involution (y,z,a)(y,z,a) transfers the leaf aa from yy to zz, contradicting (E2). The same argument applies to the other three edges.

Now suppose that two of the four edges

(z,a),(z,b),(y,c),(y,d)(z,a),\quad(z,b),\quad(y,c),\quad(y,d)

belong to the same component Γr\Gamma_r, where r∈{1,2,3,4}r \in\{1,2,3,4\}. Recall that T=Γ5T=\Gamma_5. By interchanging yy and zz and relabeling their leaf neighbors if necessary, we may assume that (z,a)∈E(Γr)(z,a) \in E(\Gamma_r) and that either (z,b)(z,b) or (y,c)(y,c) also belongs to Γr\Gamma_r.

We apply the involution (y,z,a)(y,z,a) to the original partition (Γ1,…,Γ5)(\Gamma_1,\ldots,\Gamma_5) and denote the resulting partition by (Δ1,…,Δ5)(\Delta_1,\ldots,\Delta_5). Since transferring the leaf aa from yy to zz would contradict (E2), Lemma 2.3 implies that the involution leaves the fifth component TT unchanged and exchanges the component memberships of (y,z)(y,z) and (z,a)(z,a). In particular,

Δ5=T,and(y,z)∈E(Δr).\Delta_5=T,\qquad\text{and}\qquad(y,z)\in E(\Delta_r).

If (z,b)∈E(Γr)(z,b) \in E(\Gamma_r), then (z,b)∈E(Δr)(z,b) \in E(\Delta_r) as well, since the involution (y,z,a)(y,z,a) does not involve this edge. Thus (y,z)(y,z) and (z,b)(z,b) belong to the same component Δr\Delta_r. By Lemma 2.3, the involution (y,z,b)(y,z,b) transfers the leaf bb from yy to zz in the fifth component TT, contradicting (E2).

Similarly, if (y,c)∈E(Γr)(y,c) \in E(\Gamma_r), then (y,c)∈E(Δr)(y,c) \in E(\Delta_r). Since (y,z)(y,z) also belongs to Δr\Delta_r, the involution (z,y,c)(z,y,c) transfers the leaf cc from zz to yy in TT, 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 Γ1,…,Γ4\Gamma_1,\ldots,\Gamma_4, which is impossible. □

Figure 5. Two nonadjacent degree-3 branch vertices with two leaf neighbors each and dT(x)>3d_T(x)>3.

In the next section, we turn to the particular case where ℓ(T)=6\ell(T)=6.

The six-leaf case

In this section, we still consider P\mathcal{P} to be a cycle-free 5-partition of K10K_{10} and choose a weakly equivalent partition (Γ1,…,Γ5)(\Gamma_1,\ldots,\Gamma_5) whose component T=Γ5T=\Gamma_5 satisfies the extremal conditions (E1) and (E2). We focus on the case where ℓ(T)=6\ell(T)=6 and show that this is not possible. By Lemma 4.1, there are only three possible branch-degree multisets: {5,3}\{5,3\}, {4,3,3}\{4,3,3\}, and {4,4}\{4,4\}. We start with the following lemma.

Lemma 5.1. Suppose ℓ(T)=6\ell(T)=6 and p(T)=2p(T)=2. Then the terminal leaf of either pendant path can be transferred to every leaf adjacent to a branch vertex.

Proof. There are exactly ℓ(T)−p(T)=4\ell(T)-p(T)=4 leaves adjacent to branch vertices. By Corollary 2.6, the terminal leaf of either pendant path has at least d−1=4d-1=4 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 TT satisfies ℓ(T)=6\ell(T)=6, then TT cannot have branch-degree multiset {5,3}\{5,3\}.

Proof. Suppose that xx and yy are the two branch vertices, with dT(x)=5d_T(x)=5 and dT(y)=3d_T(y)=3, 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 ℓ(T)=6\ell(T)=6 and b(T)=2b(T)=2, equation (1) gives p(T)=2p(T)=2. Hence TT has exactly two pendant paths.

By Lemma 5.1, we may successively relocate the two pendant paths so that both are based at yy. After relabeling, the two paths have the form

y−u1−v1y-u_1-v_1, and y−u2−v2y-u_2-v_2.

We apply the triangle involution (x,y,u1)(x,y,u_1). The component TT contains (x,y)(x,y) and (y,u1)(y,u_1), but not (x,u1)(x,u_1). Replacing (y,u1)(y,u_1) by (x,u1)(x,u_1) would raise the degree of xx from 5 to 6, contradicting Lemma 2.2. Hence the involution replaces (x,y)(x,y) by (x,u1)(x,u_1). In the resulting fifth component, yy has degree 2 and is adjacent to the non-leaves u1u_1 and u2u_2. 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 (x,y,u1)(x,y,u_1) creates a degree-2 vertex yy with no leaf neighbor.

The branch-degree multiset 4,3,3

Lemma 5.3. If the extremal component TT satisfies ℓ(T)=6\ell(T)=6, then TT cannot have branch-degree multiset {4,3,3}\{4,3,3\}.

Proof. Here b(T)=3b(T)=3, so (1) gives p(T)=1p(T)=1. By Lemma 3.5, the degree-4 vertex must be the middle vertex. We may therefore write

y−x−z,dT(x)=4,dT(y)=dT(z)=3.y-x-z,\qquad d_T(x)=4,\qquad d_T(y)=d_T(z)=3.

Since p(T)=1p(T)=1, 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 xx, as illustrated in Figure 7.

Figure 7. The extremal component TT with branch-degree multiset {4,3,3}\{4,3,3\}.

If the pendant path is already based at xx, there is nothing to prove. Otherwise, after interchanging yy and zz if necessary, we can write it as y−b−vy-b-v, where vv 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 vv. Since xx has two direct leaf neighbors, at least one is a destination. Transferring vv to this leaf moves the pendant path from yy to xx, 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 xx. Consequently, each of yy and zz 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 TT. To do this, we first choose a convenient form for the component TT of P\mathcal{P}.

Lemma 5.4. If the extremal component TT satisfies ℓ(T)=6\ell(T)=6 and the branch-degree multiset of TT is {4,4}\{4,4\}, then after passing to a weakly equivalent partition, we may assume that

E(T)={(x,y),(x,a),(x,b),(x,c),(y,d),(y,u),(u,v),(y,w),(w,z)}.(3)E(T)=\{(x,y),(x,a),(x,b),(x,c),(y,d),(y,u),(u,v),(y,w),(w,z)\}. \tag*{(3)}

Thus x,yx,y have degree 44, the vertices u,wu,w have degree 22, and a,b,c,d,v,za,b,c,d,v,z are leaves, as shown in Figure 8.

Figure 8. A convenient form of the extremal six-leaf component TT with branch-degree multiset {4,4}\{4,4\}.

Proof. Since ℓ(T)=6\ell(T)=6 and b(T)=2b(T)=2, equation (1) gives p(T)=2p(T)=2. 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 yy. 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 T=Γ5T=\Gamma_{5} as in Figure 8. The next lemma shows that the edges (u,w)(u,w), (w,v)(w,v), (v,z)(v,z), and (z,u)(z,u) belong to four distinct components and, more importantly, that their component memberships can be permuted while TT remains unchanged.

Lemma 5.5. If the extremal component TT is as in Figure 8, then the four edges

(u,w)(u,w), (w,v)(w,v), (v,z)(v,z), and (z,u)(z,u)

belong to four different components among Γ1,…,Γ4\Gamma_{1},\ldots,\Gamma_{4}. Moreover, for any ordering i,j,k,li,j,k,l of 1,2,3,41,2,3,4, there exists a finite sequence of triangle involutions producing a partition (Δ1,…,Δ5)(\Delta_{1},\ldots,\Delta_{5}) such that Δ5=T\Delta_{5}=T and

(u,w)∈E(Δi),(w,v)∈E(Δj),(v,z)∈E(Δk),and(z,u)∈E(Δl)(u,w)\in E(\Delta_{i}),\quad(w,v)\in E(\Delta_{j}),\quad(v,z)\in E(\Delta_{k}),\quad\text{and}\quad(z,u)\in E(\Delta_{l}).

All these involutions involve only the vertices u,v,w,zu,v,w,z.

Proof. Since none of the four edges belongs to T=Γ5T=\Gamma_{5}, we write

(u,w)∈E(Γi),(w,v)∈E(Γj),(u,z)∈E(Γk),and(v,z)∈E(Γl),(u,w)\in E(\Gamma_{i}),\quad(w,v)\in E(\Gamma_{j}),\quad(u,z)\in E(\Gamma_{k}),\quad\text{and}\quad(v,z)\in E(\Gamma_{l}),

where i,j,k,l∈{1,2,3,4}i,j,k,l\in\{1,2,3,4\}. We first show that these indices are pairwise distinct.

Consider the involution (u,w,v)(u,w,v). The only edge of this triangle belonging to TT is (u,v)(u,v). Replacing it by (w,v)(w,v) would create an additional leaf, contradicting (E1), while replacing it by (u,w)(u,w) would isolate vv. Hence the involution leaves TT unchanged and exchanges (u,w)(u,w) and (w,v)(w,v), which forces i≠ji\ne j.

Similarly, the involution (u,z,v)(u,z,v) cannot replace (u,v)(u,v) by (u,z)(u,z), since this would isolate vv. Replacing (u,v)(u,v) by (z,v)(z,v) would preserve the number of leaves and branch vertices but create adjacent degree-2 vertices ww and zz, contradicting Corollary 3.3. Thus TT remains unchanged, and (u,z)(u,z) and (v,z)(v,z) are exchanged, forcing k≠lk \ne l.

The same reasoning applied to the involutions (w,u,z)(w,u,z) and (w,v,z)(w,v,z) shows that both leave TT unchanged and exchange (u,w)(u,w) with (u,z)(u,z), and (w,v)(w,v) with (v,z)(v,z), respectively. Consequently,

i≠k,andj≠l.i \ne k,\qquad\text{and}\qquad j \ne l.

We now prove that j≠kj \ne k and i≠li \ne l. First, apply the involution (u,w,v)(u,w,v) to the original partition and denote the result by (Δ1,…,Δ5)(\Delta_1,\ldots,\Delta_5). This involution leaves TT unchanged and exchanges the component memberships of (u,w)(u,w) and (w,v)(w,v). Hence

Δ5=T,(u,w)∈E(Δj),and(u,z)∈E(Δk).\Delta_5=T,\qquad(u,w)\in E(\Delta_j),\qquad\text{and}\qquad(u,z)\in E(\Delta_k).

We then apply the involution (w,u,z)(w,u,z) to this new partition. Since it must also leave TT unchanged, it exchanges the component memberships of (u,w)(u,w) and (u,z)(u,z). These two edges must therefore belong to different components, giving j≠kj \ne k.

To show that i≠li \ne l, we return to the original partition and apply the involution (u,z,v)(u,z,v). Denote the resulting partition by (Θ1,…,Θ5)(\Theta_1,\ldots,\Theta_5). This involution leaves TT unchanged and exchanges the component memberships of (u,z)(u,z) and (v,z)(v,z), so

Θ5=T,(u,z)∈E(Θl),and(u,w)∈E(Θi).\Theta_5=T,\qquad(u,z)\in E(\Theta_l),\qquad\text{and}\qquad(u,w)\in E(\Theta_i).

Applying the involution (w,u,z)(w,u,z) to this partition, we again obtain an exchange of the component memberships of (u,w)(u,w) and (u,z)(u,z) while leaving TT unchanged. Consequently, these edges must belong to different components, and hence i≠li \ne l.

Therefore i,j,k,li,j,k,l are pairwise distinct, and hence {i,j,k,l}={1,2,3,4}\{i,j,k,l\}=\{1,2,3,4\}.

Finally, the involutions (u,w,v)(u,w,v), (u,z,v)(u,z,v), (w,u,z)(w,u,z), and (w,v,z)(w,v,z) exchange the component memberships of the following pairs of edges respectively:

((u,w),(w,v)),((u,z),(v,z)),((u,w),(u,z)),and((w,v),(v,z)).\bigl((u,w),(w,v)\bigr),\qquad\bigl((u,z),(v,z)\bigr),\qquad\bigl((u,w),(u,z)\bigr),\qquad\text{and}\qquad\bigl((w,v),(v,z)\bigr).

These exchanges generate the symmetric group S4S_4, so every permutation of the component memberships of the four edges can be realized. Since each involution leaves TT 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 TT is as in Figure 8, then the edges

(x,u),(x,v),(x,w),and(x,z)(x,u),\qquad(x,v),\qquad(x,w),\qquad\text{and}\qquad(x,z)

belong to four different components among Γ1,…,Γ4\Gamma_1,\ldots,\Gamma_4.

Proof. Suppose first that (x,u)(x,u) and (x,v)(x,v) belong to the same component. By Lemma 2.3, the involution (u,x,v)(u,x,v) replaces (u,v)(u,v) by (x,v)(x,v) in TT. This makes uu a new leaf while vv remains a leaf, contradicting (E1). Hence (x,u)(x,u) and (x,v)(x,v) belong to different components. Similarly, (x,w)(x,w) and (x,z)(x,z) belong to different components.

Now suppose that (x,r)(x,r) and (x,s)(x,s) belong to the same component Γi\Gamma_i, where r∈{u,v}r\in\{u,v\} and s∈{w,z}s\in\{w,z\}. The edge (r,s)(r,s) 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 (Δ1,…,Δ5)(\Delta_1,\ldots,\Delta_5) such that Δ5=T\Delta_5=T and (r,s)∈E(Δi)(r,s)\in E(\Delta_i). Since none of these involutions involves xx, the edges (x,r)(x,r) and (x,s)(x,s) remain in the ii-th component. Consequently, the three edges (x,r)(x,r), (r,s)(r,s), and (s,x)(s,x) form a cycle in Δi\Delta_i, contradicting the fact that Δi\Delta_i is a tree. Therefore all four edges belong to different components.

We are now ready to exclude the six-leaf branch-degree multiset {4,4}\{4,4\}.

Lemma 5.7. If the extremal component TT satisfies ℓ(T)=6\ell(T)=6, then TT cannot have branch-degree multiset {4,4}\{4,4\}.

Proof. We recall that TT is as in Figure 8. By Corollary 5.6, the edges (x,u)(x,u), (x,v)(x,v), (x,w)(x,w), and (x,z)(x,z) belong to four different components among Γ1,…,Γ4\Gamma_1,\ldots,\Gamma_4. The five edges incident with xx but not contained in TT are exactly

(x,d),(x,u),(x,v),(x,w),and (x,z).(x,d),\qquad(x,u),\qquad(x,v),\qquad(x,w),\qquad\text{and }(x,z).

Consequently, there is a unique r∈{u,v,w,z}r \in\{u,v,w,z\} such that (x,d)(x,d) and (x,r)(x,r) lie in the same component.

We show that, after passing to a weakly equivalent partition, we may assume that y−d−ry-d-r is a pendant path in TT, while (x,d)(x,d) and (x,r)(x,r) remain in the same component.

Suppose first that r∈{v,z}r \in\{v,z\}. If r=vr=v, Lemma 5.1 allows us to transfer the terminal leaf vv of the pendant path y−u−vy-u-v to the direct leaf dd. This produces the pendant path y−d−vy-d-v, as desired. The case r=zr=z is identical.

Suppose now that r∈{u,w}r \in\{u,w\}. If r=ur=u, we first apply the involution (y,u,v)(y,u,v). The component TT contains (y,u)(y,u) and (u,v)(u,v), but not (y,v)(y,v). Replacing (u,v)(u,v) by (y,v)(y,v) would increase the number of leaves to seven, contradicting (E1). Hence the involution replaces (y,u)(y,u) by (y,v)(y,v), transforming the pendant path y−u−vy-u-v into y−v−uy-v-u. The vertex uu is now the terminal leaf, and Lemma 5.1 allows us to transfer it to dd, producing the pendant path y−d−uy-d-u. The case r=wr=w 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 xx. Consequently, the edges (x,d)(x,d) and (x,r)(x,r) 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 y−d−ry-d-r, with (x,d)(x,d) and (x,r)(x,r) belonging to the same component. By Lemma 2.3, the involution (d,x,r)(d,x,r) transfers the terminal leaf rr from dd to xx. As a result, dd becomes a new leaf while rr 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 TT satisfies ℓ(T)≥7\ell(T) \ge7.

In the next section, we show that the case ℓ(T)=7\ell(T)=7 is not possible.

The seven-leaf case

Here, we still consider P\mathcal{P} to be a cycle-free 5-partition of K10K_{10} and choose a weakly equivalent partition (Γ1,…,Γ5)(\Gamma_1,\ldots,\Gamma_5) whose component T=Γ5T=\Gamma_5 satisfies the extremal conditions (E1) and (E2). By Proposition 5.8, the extremal component TT has at least seven leaves. If it has eight leaves, then TT is isomorphic to TS5T_{S_5} by Lemma 2.7. We therefore suppose throughout this section that ℓ(T)=7\ell(T)=7 and show that this is impossible. By Lemma 4.1, the only possible branch-degree multisets are

{5,3,3},{4,4,3},and{5,4}.\{5,3,3\}, \qquad\{4,4,3\}, \qquad\text{and} \qquad\{5,4\}.

We consider them in this order.

The branch-degree multiset 5,3,3

Lemma 6.1. If the extremal component TT satisfies ℓ(T)=7\ell(T)=7, then TT cannot have branch-degree multiset {5,3,3}\{5,3,3\}.

Proof. Since ℓ(T)=7\ell(T)=7 and b(T)=3b(T)=3, equation (1) gives p(T)=0p(T)=0. 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

y−x−z,dT(x)=5,dT(y)=dT(z)=3.y-x-z,\qquad d_T(x)=5,\qquad d_T(y)=d_T(z)=3.

In particular, each of yy and zz has exactly two leaf neighbors, while xx 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 TT in the case ℓ(T)=7\ell(T)=7 with branch-degree multiset {5,3,3}\{5,3,3\}.

The branch-degree multiset 4,4,3

Lemma 6.2. If the extremal component TT satisfies ℓ(T)=7\ell(T)=7, then TT cannot have branch-degree multiset {4,4,3}\{4,4,3\}.

Proof. Here, we have that p(T)=0p(T)=0, so the three branch vertices form a path. Its middle vertex cannot have degree 3, by Lemma 3.5. Therefore, after relabeling, we write TT as

x−y−z,dT(x)=dT(y)=4,dT(z)=3,x-y-z,\qquad d_T(x)=d_T(y)=4,\qquad d_T(z)=3,

with

NT(x)={y,a,b,c},NT(y)={x,z,d,e},NT(z)={y,f,g}.N_T(x)=\{y,a,b,c\},\qquad N_T(y)=\{x,z,d,e\},\qquad N_T(z)=\{y,f,g\}.

The configuration is shown in Figure 10. The five edges

Figure 10. The seven-leaf configuration with branch degrees {4,4,3}\{4,4,3\}.

(x,z),(x,f),(x,g),(x,d),and(x,e)(x,z),\qquad(x,f),\qquad(x,g),\qquad(x,d),\qquad\text{and}\qquad(x,e)

do not belong to TT. We write

(x,z)∈E(Γi),(x,f)∈E(Γj),(x,g)∈E(Γk),(x,d)∈E(Γl),and(x,e)∈E(Γm),(x,z)\in E(\Gamma_i),\qquad(x,f)\in E(\Gamma_j),\qquad(x,g)\in E(\Gamma_k),\qquad(x,d)\in E(\Gamma_l),\qquad\text{and}\qquad(x,e)\in E(\Gamma_m),

where i,j,k,l,m∈{1,2,3,4}i,j,k,l,m\in\{1,2,3,4\}. We prove that these indices are pairwise distinct. First, i≠ji \ne j and i≠ki \ne k. Indeed, if i=ji=j, then (x,z)(x,z) and (x,f)(x,f) belong to the same component. By Lemma 2.3, the involution (z,x,f)(z,x,f) transfers the leaf ff from zz to xx. This preserves the number of leaves and decreases the number of branch vertices, contradicting (E2). The same argument with gg in place of ff gives i≠ki \ne k.

We now apply the involution (z,x,f)(z,x,f) to the original partition. Since transferring ff to xx would contradict (E2), this involution leaves TT unchanged and exchanges the component memberships of (x,z)(x,z) and (x,f)(x,f). Thus (x,z)(x,z) now belongs to the jj-th component, while (x,g)(x,g) still belongs to the kk-th component. If j=kj=k, the involution (z,x,g)(z,x,g) would transfer the leaf gg from zz to xx, again contradicting (E2). Hence j≠kj \ne k.

Moreover, the involutions (z,x,f)(z,x,f) and (z,x,g)(z,x,g) exchange the component memberships of (x,z)(x,z) with those of (x,f)(x,f) and (x,g)(x,g), respectively, while leaving TT unchanged. These exchanges correspond to the transpositions (1,2)(1,2) and (1,3)(1,3), which generate the symmetric group S3S_3. Consequently, starting from the original partition, we can arrange for (x,z)(x,z) to belong to any one of the components Γi,Γj,Γk\Gamma_i,\Gamma_j,\Gamma_k, without changing TT or the component memberships of (x,d)(x,d) and (x,e)(x,e).

Let t∈{i,j,k}t \in\{i,j,k\}. Choose such a partition (Δ1,…,Δ5)(\Delta_1,\ldots,\Delta_5) with

Δ5=T,(x,z)∈E(Δt),(x,d)∈E(Δl),(x,e)∈E(Δm).\Delta_5=T,\qquad(x,z)\in E(\Delta_t),\qquad(x,d)\in E(\Delta_l),\qquad(x,e)\in E(\Delta_m).

We apply the involution (x,y,z)(x,y,z). Since replacing (y,z)(y,z) by (x,z)(x,z) would produce a component with branch-degree multiset {5,3,3}\{5,3,3\}, which is impossible by Lemma 6.1, the involution must replace (x,y)(x,y) by (x,z)(x,z). Denote the resulting partition by (Θ1,…,Θ5)(\Theta_1,\ldots,\Theta_5) and put T′=Θ5T'=\Theta_5. Then T′T' has branch path y−z−xy-z-x, with degrees 3,4,43,4,4, respectively, as in Figure 11 and

Figure 11. The component T′T' with branch path y−z−xy-z-x.

(x,y)∈E(Θt),(x,d)∈E(Θl),(x,e)∈E(Θm).(x,y)\in E(\Theta_t),\qquad(x,d)\in E(\Theta_l),\qquad(x,e)\in E(\Theta_m).

Transferring either leaf dd or ee from yy to xx would preserve the seven leaves and decrease the number of branch vertices from three to two, contradicting (E2). Therefore, Lemma 2.3 gives

t≠l,andt≠m.t\ne l,\qquad\text{and}\qquad t\ne m.

Since tt was arbitrary in {i,j,k}\{i,j,k\}, we obtain

{i,j,k}∩{l,m}=∅.\{i,j,k\}\cap\{l,m\}=\varnothing.

It remains to show that l≠ml\ne m. Suppose otherwise. We apply the involution (y,x,d)(y,x,d) to the partition (Θ1,…,Θ5)(\Theta_1,\ldots,\Theta_5). Since transferring dd from yy to xx is forbidden, the involution leaves T′T' unchanged and exchanges the component memberships of (x,y)(x,y) and (x,d)(x,d). Thus (x,y)(x,y) now belongs to the ll-th component, which also contains (x,e)(x,e) because l=ml=m. By Lemma 2.3, the involution (y,x,e)(y,x,e) would then transfer the leaf ee from yy to xx, contradicting (E2). Hence l≠ml\ne m.

Hence i,j,k,l,mi,j,k,l,m are five pairwise distinct elements of {1,2,3,4}\{1,2,3,4\}, which is impossible. □\square

The branch-degree multiset {5,4}\{5,4\}

It remains to exclude the case where the branch-degree multiset is {5,4}\{5,4\}. 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

C={(1,2),(1,4),(1,6),(1,8),(1,10),(2,3),(2,5),(2,7)},C=\{(1,2),(1,4),(1,6),(1,8),(1,10),(2,3),(2,5),(2,7)\},

The branch-degree multiset 5,4

and set

S={3,4,5,6,7,8,10},L={4,6,8,10}.S=\{3,4,5,6,7,8,10\},\qquad L=\{4,6,8,10\}.

For a∈Sa\in S, let HaH_a be the tree defined by

E(Ha)=C∪{(a,9)}.(4)E(H_a)=C\cup\{(a,9)\}. \tag*{(4)}

Thus HaH_a consists of the eight fixed edges in CC and one edge joining the leaf 9 to aa. The vertices in LL are adjacent to 1, whereas 3, 5, 7 are adjacent to 2. Figure 12 shows H4H_4 as an example. If the edge (a,9)(a,9) is replaced by (2,9)(2,9), the resulting tree is isomorphic to TS5TS_5.

The tree $H_4$

Figure 12. The tree H4H_4.

Lemma 6.3. Up to weakly equivalent partition, we may assume that T=HaT=H_a for some a∈La\in L.

Proof. Let x,yx,y be the branch vertices, with dT(x)=5d_T(x)=5 and dT(y)=4d_T(y)=4. By (1), p(T)=1p(T)=1, hence the unique degree-2 vertex belongs to a pendant path based at xx or yy. If the path is based at xx, we obtain the required form by relabeling.

Suppose instead that the path is based at yy. Then xx has four direct leaf neighbors and yy 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 xx receives it. The transfer moves the pendant path from yy to xx and preserves the numbers of leaves and branch vertices, so the resulting component is still extremal. Relabeling gives T=HaT = H_a for some a∈La \in L.

Our next goal is to show that, while the eight edges of CC stay in the fifth component, the leaf 9 can be attached at several different vertices of SS. The following two lemmas make this precise.

Lemma 6.4. Suppose that Γ5=Ha\Gamma_5 = H_a for some a∈Sa \in S, and assume that no cycle-free 5-partition weakly equivalent to (Γ1,…,Γ5)(\Gamma_1,\ldots,\Gamma_5) has a component isomorphic to TS5TS_5. Let R⊆SR \subseteq S be the set of vertices ss for which a sequence of triangle involutions, changing only the attachment of the leaf 9 in the fifth component and keeping all edges of CC fixed, produces a partition with fifth component HsH_s. Then ∣R∣≥5|R| \ge5.

Proof. Clearly a∈Ra \in R. Suppose that ∣R∣≤4|R| \le4, and fix s∈Rs \in R. We consider the weakly equivalent partition whose fifth component is HsH_s. Choose three distinct vertices t1,t2,t3∈S∖Rt_1,t_2,t_3 \in S \setminus R.

If s∈Ls \in L, then dHs(s)=2d_{H_s}(s) = 2 and (s,2)∉E(Hs)(s,2) \notin E(H_s). Put B={2,t1,t2,t3}B = \{2,t_1,t_2,t_3\}. None of the edges (s,b)(s,b), b∈Bb \in B, belongs to HsH_s, and

∣B∣=4=5−dHs(s)+1.|B| = 4 = 5 - d_{H_s}(s) + 1.

Therefore, Lemma 2.5 implies that some vertex in BB receives the leaf 9. That vertex cannot be 2, since this would produce TS5TS_5. Hence one of t1,t2,t3t_1,t_2,t_3 belongs to RR, which is a contradiction.

If s∈{3,5,7}s \in\{3,5,7\}, the same argument applies with B={1,t1,t2,t3}B = \{1,t_1,t_2,t_3\}. The vertex 1 cannot receive the leaf: it already has degree 5 in HsH_s, so receiving 9 would violate Lemma 2.2. Thus one of t1,t2,t3t_1,t_2,t_3 must receive the leaf, again contradicting their choice. It follows that ∣R∣≥5|R| \ge5.

We now show that if the edges (2,c)(2,c) and (2,9)(2,9), for some c∈Lc \in L, belong to the same component, then the partition (Γ1,…,Γ5)(\Gamma_1,\ldots,\Gamma_5) is weakly equivalent to one whose fifth component is TS5TS_5.

Lemma 6.5. Suppose that Γ5=Ha\Gamma_5 = H_a for some a∈Sa \in S. If there exist c∈Lc \in L and i∈{1,2,3,4}i \in\{1,2,3,4\} such that

(2,c),and(2,9)∈E(Γi),(2,c),\quad\text{and}\quad(2,9) \in E(\Gamma_i),

then the partition (Γ1,…,Γ5)(\Gamma_1,\ldots,\Gamma_5) is weakly equivalent to one whose fifth component is TS5TS_5.

Proof. If a=ca = c, the involution (c,2,9)(c,2,9) transfers the leaf 9 from cc to 2, by Lemma 2.3, and we are done. Suppose that a≠ca \ne c, and assume by contradiction that no weakly equivalent partition contains TS5TS_5.

Let (c,9)∈E(Γj)(c,9) \in E(\Gamma_j). Since (2,c)(2,c) and (2,9)(2,9) both belong to Γi\Gamma_i, we have j≠ij \ne i, or else these three edges would form a cycle in Γi\Gamma_i. We write {i,j,k,l}={1,2,3,4}\{i,j,k,l\} = \{1,2,3,4\}. For each r∈{i,j,k,l}r \in\{i,j,k,l\}, let nrn_r be the number of vertices u∈S∖{c}u \in S \setminus\{c\} for which (c,u)∈E(Γr)(c,u) \in E(\Gamma_r). The six edges from cc to S∖{c}S \setminus\{c\} lie outside HaH_a and are distributed among the four components $\Gamma_1,\ldots,\Gamma_4. Thus

ni+nj+nk+nl=6.(5)n_i+n_j+n_k+n_l = 6. \tag*{(5)}

We first prove that

ni+nj≤1.(6)n_i+n_j \le1. \tag*{(6)}

We consider the possible destinations of the leaf 9, which is initially attached to the vertex aa. By Corollary 2.6, the leaf 9 has at least four destinations. The vertices eligible to receive it are those in S∖{a}S \setminus\{a\}, together with one additional vertex: 2 if a∈La \in L, or 1 if a∈{3,5,7}a \in\{3,5,7\}. The additional vertex cannot receive 9, because the result would be TS5TS_5 in the first case and would violate the degree bound in the second.

We also show that cc cannot receive 9. Indeed, if the involution (a,c,9)(a,c,9) transfers the leaf 9 from aa to cc, then the edges (2,c)(2,c) and (2,9)(2,9) remain in Γi\Gamma_i. By Lemma 2.3, the involution (c,2,9)(c,2,9) would then transfer the leaf 9 from cc to 2, producing TS5TS_5, which is again a contradiction.

Consequently, at least four vertices in S∖{a,c}S \setminus\{a,c\} receive the leaf 9. Together with its original attachment vertex aa, this gives at least five vertices in S∖{c}S \setminus\{c\} at which the leaf 9 can be attached. Moreover, each of these attachments can be obtained without involving cc in any involution. Hence the component memberships of all edges incident with cc remain unchanged.

Let uu be any of these five vertices. If u≠au \ne a, we transfer the leaf 9 from aa to uu by applying the involution (a,u,9)(a,u,9). If u=au=a, we make no change. We denote the resulting partition by (Δ1,…,Δ5)(\Delta_1,\ldots,\Delta_5). Then Δ5=Hu\Delta_5=H_u, and since the transfer does not involve cc, the edges incident with cc retain their original component memberships. In particular,

(c,9)∈E(Δj),(2,c),(2,9)∈E(Δi).(c,9) \in E(\Delta_j), \qquad(2,c),(2,9) \in E(\Delta_i).

We show that (c,u)(c,u) belongs to neither Δi\Delta_i nor Δj\Delta_j. If (c,u)∈E(Δj)(c,u) \in E(\Delta_j), then (c,u)(c,u) and (c,9)(c,9) belong to the same component. By Lemma 2.3, the involution (u,c,9)(u,c,9) transfers the leaf 9 from uu to cc. The involution (c,2,9)(c,2,9) then transfers it from cc to 2, producing TS5TS_5, which is a contradiction.

Suppose instead that (c,u)∈E(Δi)(c,u) \in E(\Delta_i). Applying the involution (u,c,9)(u,c,9) to the partition (Δ1,…,Δ5)(\Delta_1,\ldots,\Delta_5), it either transfers the leaf 9 to cc, leading to the same contradiction, or it leaves HuH_u unchanged and exchanges the component memberships of (c,u)(c,u) and (c,9)(c,9). In the latter case, the edges

(2,c),(c,9),(9,2)(2,c), \qquad(c,9), \qquad(9,2)

all belong to the same component, forming a cycle which is again a contradiction.

Therefore, for each of these five vertices uu, the edge (c,u)(c,u) belongs to neither Γi\Gamma_i nor Γj\Gamma_j. Since S∖{c}S \setminus\{c\} contains exactly six vertices, at most one of the six edges joining cc to these vertices can belong to Γi\Gamma_i or Γj\Gamma_j. Hence

ni+nj≤1.n_i+n_j \le1.

as required.

By (5) and (6), we have nk+nl≥5n_k+n_l \ge5. After interchanging kk and ll if necessary, we may assume that nk≥3n_k \ge3.

Recall that there are five vertices in S∖{c}S \setminus\{c\} to which the leaf 9 can be attached. Since nk≥3n_k \ge3 and S∖{c}S \setminus\{c\} contains six vertices, at least two of these five vertices are joined to cc by an edge of Γk\Gamma_k. Choose one such vertex rr.

If r≠ar \ne a, we apply the involution (a,r,9)(a,r,9) to transfer the leaf 9 from aa to rr; otherwise, we make no change. We denote the resulting partition by (Δ1,…,Δ5)(\Delta_1,\ldots,\Delta_5). Then Δ5=Hr\Delta_5=H_r, and since the transfer does not involve cc, we still have

(c,r)∈E(Δk),(c,9)∈E(Δj),(c,r) \in E(\Delta_k), \qquad(c,9) \in E(\Delta_j),

and

(2,c),(2,9)∈E(Δi).(2,c),(2,9) \in E(\Delta_i).

We now apply the involution (r,c,9)(r,c,9) to the partition (Δ1,…,Δ5)(\Delta_1,\ldots,\Delta_5). If it transfers the leaf 99 from rr to cc, then the involution (c,2,9)(c,2,9) transfers 99 from cc to 22, producing TS5TS_5, which is a contradiction.

Otherwise, let (Θ1,…,Θ5)(\Theta_1,\ldots,\Theta_5) denote the resulting partition. By Lemma 2.3, the involution leaves HrH_r unchanged and exchanges the component memberships of (c,r)(c,r) and (c,9)(c,9). Consequently,

Θ5=Hr,(c,9)∈E(Θk),\Theta_5=H_r,\qquad(c,9)\in E(\Theta_k),

while

(2,c) and (2,9)∈E(Θi).(2,c)\text{ and }(2,9)\in E(\Theta_i).

Among the six edges (c,u)(c,u) with u∈S∖{c}u\in S\setminus\{c\}, only (c,r)(c,r) changes component membership, moving from Γk\Gamma_k to Γj\Gamma_j. Thus, if nk′n'_k denotes the number of these edges belonging to Θk\Theta_k, then

nk′=nk−1≥2.n'_k=n_k-1\ge2.

On the other hand, the argument used to establish (6) applies to (Θ1,…,Θ5)(\Theta_1,\ldots,\Theta_5), with Θk\Theta_k playing the role previously played by Γj\Gamma_j. Indeed, (c,9)(c,9) now belongs to Θk\Theta_k, while (2,c)(2,c) and (2,9)(2,9) still belong to Θi\Theta_i. The same argument therefore gives nk′≤1n'_k\le1, which is a contradiction. This completes the proof. □

We are now ready to prove that the partition (Γ1,⋯ ,Γ5)(\Gamma_1,\cdots,\Gamma_5) is weakly equivalent to a partition whose fifth component is TS5TS_5.

Lemma 6.6. Suppose that Γ5=Ha\Gamma_5=H_a for some a∈La\in L. Then the partition (Γ1,⋯ ,Γ5)(\Gamma_1,\cdots,\Gamma_5) is weakly equivalent to one whose fifth component is TS5TS_5.

Proof. The five edges

(2,4),(2,6),(2,8),(2,10),and (2,9)(7)(2,4),\qquad(2,6),\qquad(2,8),\qquad(2,10),\qquad\text{and }(2,9) \tag*{(7)}

are precisely the edges incident with 22 that do not belong to Γ5\Gamma_5. Since dΓ5(2)=4d_{\Gamma_5}(2)=4, each of the other four components contains at least one of these five edges. Consequently, exactly one of Γ1,…,Γ4\Gamma_1,\ldots,\Gamma_4 contains two of them, while each of the remaining three contains one.

If (2,9)(2,9) belongs to the component containing two edges, then there exist c∈Lc\in L and i∈{1,2,3,4}i\in\{1,2,3,4\} such that

(2,c) and (2,9)∈E(Γi).(2,c)\text{ and }(2,9)\in E(\Gamma_i).

The conclusion then follows from Lemma 6.5.

We may therefore assume that there exist distinct p,q∈Lp,q\in L and distinct i,j∈{1,2,3,4}i,j\in\{1,2,3,4\} such that

(2,p),(2,q)∈E(Γi),and(2,9)∈E(Γj).(2,p),(2,q)\in E(\Gamma_i),\qquad\text{and}\qquad(2,9)\in E(\Gamma_j).

Suppose, for a contradiction, that no partition weakly equivalent to P\mathcal{P} contains a component isomorphic to TS5TS_5. Let RR be the set defined in Lemma 6.4.

We first show that neither pp nor qq belongs to RR. Suppose that p∈Rp\in R. By Lemma 6.4, we can transfer the leaf 99 from aa to pp through a sequence of involutions that keeps the eight edges of CC in the fifth component. We denote the resulting partition by (Δ1,…,Δ5)(\Delta_1,\ldots,\Delta_5). Since none of these involutions involves 22, we have

Δ5=Hp,(2,p),(2,q)∈E(Δi),and(2,9)∈E(Δj).\Delta_5=H_p,\qquad(2,p),(2,q)\in E(\Delta_i),\qquad\text{and}\qquad(2,9)\in E(\Delta_j).

We now apply the involution (p,2,9)(p,2,9). If it transfers the leaf 99 from pp to 22, the resulting fifth component is TS5TS_{5}, contrary to our assumption. Otherwise, by Lemma 2.3, the involution leaves HpH_p unchanged and exchanges the component memberships of (2,p)(2,p) and (2,9)(2,9). Thus, in the resulting partition (Θ1,…,Θ5)(\Theta_1,\ldots,\Theta_5), we have

Θ5=Hp,and(2,q),(2,9)∈E(Θi).\Theta_5=H_p,\qquad\text{and}\qquad(2,q),(2,9)\in E(\Theta_i).

Lemma 6.5 then applies and gives a contradiction. The same argument applies if q∈Rq\in R. Hence

R∩{p,q}=∅.R\cap\{p,q\}=\varnothing.

Since R⊆SR\subseteq S, with ∣R∣≥5|R|\geq5, and ∣S∣=7|S|=7, we conclude that

R=S∖{p,q}.R=S\setminus\{p,q\}.

We write L∖{p,q}={r,s}L\setminus\{p,q\}=\{r,s\}, and let

(2,r)∈E(Γk),and(2,s)∈E(Γl).(2,r)\in E(\Gamma_k),\qquad\text{and}\qquad(2,s)\in E(\Gamma_l).

By the distribution of the five edges in (7), the indices i,j,k,li,j,k,l are pairwise distinct. Moreover, (p,q)∉E(Γi)(p,q)\notin E(\Gamma_i), since otherwise the edges (2,p)(2,p), (2,q)(2,q), and (p,q)(p,q) would form a cycle in Γi\Gamma_i. We now exclude the three remaining possibilities for the component containing (p,q)(p,q).

Suppose first that (p,q)∈E(Γj)(p,q)\in E(\Gamma_j). We apply the involution (2,p,q)(2,p,q) and denote the resulting partition by (Δ1,…,Δ5)(\Delta_1,\ldots,\Delta_5). Since (2,p)(2,p) and (2,q)(2,q) belong to Γi\Gamma_i, while (p,q)(p,q) belongs to Γj\Gamma_j, the involution replaces one of (2,p)(2,p) or (2,q)(2,q) in Γi\Gamma_i by (p,q)(p,q). Thus one of these two edges moves into Δj\Delta_j, which still contains (2,9)(2,9). The fifth component remains HaH_a. Lemma 6.5 therefore applies to the resulting partition, giving a contradiction.

Suppose next that (p,q)∈E(Γk)(p,q)\in E(\Gamma_k). Since r∈Rr\in R, we can transfer the leaf 99 from aa to rr, keeping the edges of CC in the fifth component. Denote the resulting partition by (Δ1,…,Δ5)(\Delta_1,\ldots,\Delta_5). Every intermediate attachment vertex belongs to RR, which contains neither pp nor qq. Furthermore, none of these transfers involves 22. Consequently,

Δ5=Hr,(p,q),(2,r)∈E(Δk),\Delta_5=H_r,\qquad(p,q),(2,r)\in E(\Delta_k),

while

(2,p),(2,q)∈E(Δi),and(2,9)∈E(Δj).(2,p),(2,q)\in E(\Delta_i),\qquad\text{and}\qquad(2,9)\in E(\Delta_j).

We apply the involution (2,p,q)(2,p,q) to this partition. Since (2,p)(2,p) and (2,q)(2,q) belong to Δi\Delta_i, while (p,q)(p,q) belongs to Δk\Delta_k, the involution moves one of (2,p)(2,p) or (2,q)(2,q) into the kk-th component, leaving HrH_r unchanged. After interchanging pp and qq if necessary, we may assume that (2,p)(2,p) moves into that component. Thus, writing (Θ1,…,Θ5)(\Theta_1,\ldots,\Theta_5) for the resulting partition, we have

Θ5=Hr,(2,p),(2,r)∈E(Θk),and(2,9)∈E(Θj).\Theta_5=H_r,\qquad(2,p),(2,r)\in E(\Theta_k),\qquad\text{and}\qquad(2,9)\in E(\Theta_j).

We now apply the involution (r,2,9)(r,2,9). If it transfers the leaf $9$ from rr to 22, the resulting fifth component is TS5TS_{5}, which is a contradiction. Otherwise, Lemma 2.3 implies that the involution leaves HrH_r unchanged and exchanges the component memberships of (2,r)(2,r) and $(2,9). Hence, in the resulting partition (Λ1,…,Λ5)(\Lambda_1,\ldots,\Lambda_5), we have

Λ5=Hr,and(2,p),(2,9)∈E(Λk).\Lambda_5=H_r,\qquad\text{and}\qquad(2,p),(2,9)\in E(\Lambda_k).

Applying Lemma 6.5 again gives a contradiction.

Finally, if (p,q)∈E(Γl)(p,q) \in E(\Gamma_l), we repeat the preceding argument with ss in place of rr and Γl\Gamma_l in place of Γk\Gamma_k. This also leads to a contradiction. Therefore (p,q)(p,q) belongs to none of the five components Γ1,…,Γ5\Gamma_1,\ldots,\Gamma_5, which is a contradiction. Hence the partition (Γ1,…,Γ5)(\Gamma_1,\ldots,\Gamma_5) is weakly equivalent to one whose fifth component is TS5TS_5. □

Therefore, we have the following Corollary.

Corollary 6.7. If the extremal component TT satisfies ℓ(T)=7\ell(T)=7, then TT cannot have branch-degree multiset {5,4}\{5,4\}.

Proof. By Lemma 6.3, after weak equivalence, we may assume that T=HaT=H_a for some a∈La\in L. Lemma 6.6 gives a weakly equivalent partition whose fifth component is TS5TS_5. Since TS5TS_5 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 d=5d=5.

Proof. Let P\mathcal{P} be a cycle-free 5-partition of K10K_{10}. Let TT be an extremal component of P\mathcal{P} as in Definition 3.1. Thus P\mathcal{P} is weakly equivalent to a partition (Γ1,…,Γ5)(\Gamma_1,\ldots,\Gamma_5) with Γ5=T\Gamma_5=T. By Theorem 3.8 and Lemma 2.7, we have

6≤ℓ(T)≤8.6 \leq\ell(T) \leq8.

Proposition 5.8 and Lemmas 6.1, 6.2 together with Corollary 6.7 exclude the cases ℓ(T)=6\ell(T)=6 and ℓ(T)=7\ell(T)=7. Hence ℓ(T)=8\ell(T)=8, and Lemma 2.7 implies that TT is isomorphic to TS5TS_5. Therefore, P\mathcal{P} is weakly equivalent to a cycle-free 5-partition containing a component isomorphic to TS5TS_5, proving Conjecture 1.3 for d=5d=5. □

As a consequence of Theorem 6.8, we obtain the following uniqueness result for the determinant-like map det⁡S2\operatorname{det}^{S^2} in dimension 5.

Corollary 6.9. The determinant-like map det⁡S2:V5⊗45⟶k\operatorname{det}^{S^2}:V_5^{\otimes45}\longrightarrow k is unique up to multiplication by a scalar.

Proof. By Theorem 6.8 and the previously established cases d≤4d\leq4, the twin-star hypothesis holds for every 1≤d≤51\leq d\leq5. Hence Conjecture 1.1 holds for d=5d=5 by [6]. The uniqueness of det⁡S2\operatorname{det}^{S^2} then follows from the equivalence established in [10]. □

Conclusion

One of the main difficulties in studying cycle-free dd-partitions of K2dK_{2d} 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 d=5d = 5, 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. [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. [2]R. A. Brualdi and S. Hollingsworth, Multicolored trees in complete graphs, J. Combin. Theory Ser. B 68 (1996), 310–313.DOI
  3. [3]S. M. Cioaba and P. J. Cameron, A graph partition problem, Amer. Math. Monthly 122 (2015), 972–982.
  4. [4]D. Froncek, Bi-cyclic decompositions of complete graphs into spanning trees, Discrete Math. 307 (2007), 1317–1322.DOI
  5. [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. [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. [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. [8]P. Kovar, M. Kubesa, and M. Meszka, Factorizations of complete graphs into brooms, Discrete Math. 312 (2012), 1084–1093.DOI
  9. [9]M. Kubesa, Spanning tree factorizations of complete graphs, J. Combin. Math. Combin. Comput. 52 (2005), 33–49.
  10. [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. [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. [12]M. D. Staic, Existence of the detˢ² map, Bull. Lond. Math. Soc. 55 (2023), no. 4, 1685–1699.DOI
  13. [13]M. D. Staic, The exterior graded Swiss-Cheese operad Λˢ²ᵥ, Comm. Algebra 51 (2023), no. 7, 2705–2728.DOI
  14. [14]M. D. Staic, The r-equilibrium problem, Linear Multilinear Algebra 73 (2025), no. 15, 3421–3433.
  15. [15]M. D. Staic and J. Van Grinsven, A geometric application for the map detˢ², Comm. Algebra 50 (2022), no. 3, 1106–1117.

Paper details

vlnc:W_egr6f87y
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents