Proof. It is clear that $\mathcal{P}_{T,0}, \mathcal{P}_{T,1}, \ldots $ are pairwise disjoint. Henceforth, to show that $\mathcal{P}_{T,k }=(\bigcup_{i=0}^{k}\mathcal{P}_{T,i})\setminus (\bigcup_{i=0}^{k-1}\mathcal{P}_{T,i})$ is equal to $\mathcal{S}_{T,k }\setminus (\bigcup_{i=0}^{k-1}\mathcal{S}_{T,i})=(\bigcup_{i=0}^{k}\mathcal{S}_{T,i})\setminus (\bigcup_{i=0}^{k-1}\mathcal{S}_{T,i})$, we only need to verify that $\bigcup_{i=0}^{k}\mathcal{P}_{T,i}=\bigcup_{i=0}^{k}\mathcal{S}_{T,i}$ holds for each non-negative integer k. Since $ \bigcup_{i=0}^{k}\mathcal{S}_{T,i} \subseteq \bigcup_{i=0}^{k}\mathcal{P}_{T,i}$ holds trivially, our task reduces to proving that $\mathcal{P}_{T,k }\subseteq \mathcal{S}_{T,k } $.

Consider an $\mathrm{L}_T$-split $Y\mid Z\in \mathcal{P}_{T,k}$. By definition, there exists a set $F\in \binom{\mathrm{E}_T}{k} $ intersecting with $T_{y,z}$ for each $y\in Y$ and $z\in Z$. Since T is a tree, there are k + 1 connected components $V_1,\ldots, V_{k+1}$ in T − F. Denote $V_i\cap \mathrm{L}_T$ by $\mathrm{L}_i$ for each $i\in [k+1]$. Clearly, $\mathrm{L}_i\mid \emptyset \subseteq Y\mid Z$ for each $i\in [k+1]$. For any $f\in F$, say $f=u_iu_j$ with $u_i\in V_i$ and $u_j\in V_j$, from $\operatorname{PS}(T,Y\mid Z)=|{F}|$ we derive the existence of $y\in Y$ and $z\in Z$ such that $\{f\}=F\cap T_{y,z}$. This then implies that both $\mathrm{L}_i$ and $\mathrm{L}_j$ are non-empty and

(1)\begin{equation} \mathrm{L}_i\mid \mathrm{L}_j \subseteq Y\mid Z. \end{equation}

We now construct a tree T′ on $[k+1]$ such that ij is an edge if and only if $\operatorname{dist}_T(V_i,V_j)=1$. Let $U\mid W$ be the unique partition of $\mathrm{V}_{T'}$ into its two independent sets. From Eq. (1), we infer that $\{Y,Z\}=\{\cup_{i\in U}\mathrm{L}_i, \cup_{j\in W}\mathrm{L}_j \}$, and thus $Y\mid Z = \mathbf{S}_{T,F} \in \mathcal{S}_{T,k}$, as desired.

Proof. Assume that e = uv. Take $x\in \mathrm{L}_T\cap \operatorname{C}_{T-e }[u]$ and $y \in \mathrm{L}_T\cap \operatorname{C}_{T-e }[v] $. Clearly, x and y fall into different parts of $\mathbf{S}_{T,\{e\} }$, showing that $\mathbf{S}_{T,\{e\} }$ is proper.

If $e\neq e'$ and $\deg_T(w)=2$ for all $w\in [e,e']_T$, then $\mathbf{S}_{T,\{e,e'\}}$ is surely improper.

It remains to show that $\mathbf{S}_{T,\{e,e'\}}$ is proper in the case that $e\neq e'$ and $[e,e']_T$ contains a vertex w with $\deg_T(w)\geqslant 3$. We first find $x , y \in \mathrm{L}_T$ such that $\{e, e'\}\subseteq T_{x , y}$. Thanks to $\deg_T(w)\geqslant 3$, we can then pick a vertex $w'\in \operatorname{N}_T(w)$ outside the path between x and y in T. Choose $z\in \mathrm{L}_T\cap \operatorname{C}_{T-w}[w'] $. One can check that x and z fall into different parts of $\mathbf{S}_{T,\{e,e'\}}$, and thus $\mathbf{S}_{T,\{e,e'\}}$ is a proper split.

Proof. The backward direction is obvious. We only consider the forward direction.

Assume that $v_1\in e_1$, $v_2\in e_2$ and $\operatorname{dist}_T(e_1,e_2)=\operatorname{dist}_T(v_1,v_2)$. Note that v ₁ and v ₂ must be inner vertices of the phylogenetic tree T. If $v_1=v_2$ and $\deg_T(v_1)=3$, then it is direct from $\mathbf{S}_{T,\{e_1,e_2\}} = \mathbf{S}_{T, \{e_3\}} $ that $e_1,e_2$, and e ₃ are the three edges incident with v ₁ in T, as required. We thus assume that either $v_1\neq v_2$ or $\deg_T(v_1) \gt 3$, and we aim to derive a contradiction. Our assumption now enables us find $w_1,w_2\in \mathrm{V}_T$ such that $v_1w_1, v_2w_2\in \mathrm{E}_T\setminus (\{e_1,e_2\}\cup T_{v_1,v_2})$ and $v_1w_1\neq v_2w_2$. We can accordingly find $x_1,y_1,x_2,y_2\in \mathrm{L}_T$ such that, for each $i\in [2]$, $e_{3-i}\notin T_{x_i,y_i}\supseteq \{e_i, v_iw_i\}$, thus implying that x_i and y_i belong to different parts of $\mathbf{S}_{T,\{e_1,e_2\}}$. Since $ T_{x_1,y_1}$ and $ T_{x_2,y_2}$ are disjoint, one of them cannot contain the edge e ₃. This contradicts $\mathbf{S}_{T,\{e_1,e_2\}} = \mathbf{S}_{T,\{e_3 \}} $.

Proof. By Remark 2.4, $\mathbf{S}_{T,\{e_1,e_2\}}\notin \mathcal{P}_{T,2}$ if and only if there exists $e_3\in \mathrm{E}_T $ such that $\mathbf{S}_{T,\{e_1,e_2\}} = \mathbf{S}_{T, \{e_3\}} $. It follows from Lemma 2.5 that the latter condition is further equivalent to the condition that e ₁ and e ₂ share a common endpoint v with $\deg_T(v)=3$.

Proof. Let e ₁ and e ₂ be the edges incident with x and y in T, respectively. Note that $\{x,y\}\mid (\mathrm{L}_T\setminus \{x,y\})=\mathbf{S}_{T,\{e_1,e_2\}}$. The result now follows directly from Corollary 2.6.

Proof. Take $x,y\in \mathrm{L}_{\tilde{T}}\subseteq \mathrm{L}_T$. Clearly, we have $T_{x,y}=\tilde{T}_{x,y}$. Therefore, x and y belong to the same part of $\mathbf{S}_{\tilde{T},F }$ if and only if they belong to the same part of $\mathbf{S}_{T,F }$.

Proof. Let us write T′ for the tree $T[V_i+w_0]$. Take $y_i\in Y_i$ and $y\in Y\setminus Y_i$. Considering that $Z\cap Y_i\subseteq Z\cap Y=\emptyset$ and $|{\{p\in [k]:\ Z\cap Y_p\neq \emptyset \}}|\geqslant 3$, we may assume that $i\geqslant 4$ and $Z\cap Y_j\neq \emptyset$ for all $j\in [3]$. This implies the existence of $y_j\in Y_j$ for each $j\in [3]$ such that $|{T_{y_j,y_i}\cap \{e_1,e_2\}}|=1$. Since $T_{y_j,w_0}$, $j\in [3]$, are three disjoint edge sets, the pigeonhole principle tells us that $\{e_1,e_2\}\cap \mathrm{E}_{T'}\neq \emptyset$. For each $z\in Z$, $\{e_1,e_2\}\cap T_{y,z}$ is a singleton set. As $T_{y,z}\cap \mathrm{E}_{T'}=\emptyset$, we see that $\{e_1,e_2\}\setminus \mathrm{E}_{T'}\neq \emptyset$. To sum up, we have $|{\{e_1,e_2\}\cap \mathrm{E}_{T'}}|=|{\{e_1,e_2\}\setminus \mathrm{E}_{T'}}|=1$, which means that $e_1\neq e_2$. Assume that $\{e_1\}= \{e_1,e_2\}\cap \mathrm{E}_{T'} $. If $V_i=\{w_i\}$, then clearly $e_1=w_0w_i$. If $|{V_i}|\geqslant 2$, then, applying Lemma 2.8 for $F=\{e_1,e_2\}$ and $\tilde{T}=T[V_i]$, we find that $\mathbf{S}_{T[V_i], \{e_1\} } =Y_i\mid \emptyset$. In view of Lemma 2.3, we now conclude that $ e_1 \notin \mathrm{E}_{T[V_i]}$, i.e., $e_1=w_0w_i$.

Proof. Let $\mathbf{S} =Y \mid Z \in \mathcal{S}_{T,2}$. Take $\{e_1,e_2\}, \{e'_1,e'_2\} \in \binom{\mathrm{E}_T}{2}$ such that $ U\mid W=\widehat{\mathbf{S}}_{T,\{e_1,e_2\}}$ and $ U'\mid W'=\widehat{\mathbf{S}}_{T,\{e'_1,e'_2\}}$ are two splits satisfying $Y=U\cap \mathrm{L}_T=U'\cap \mathrm{L}_T$. We aim to show that either $U\subseteq U'$ or $W\subseteq W'$. Due to the symmetry between Y and Z as well as the symmetry between $ U\mid W$ and $ U'\mid W'$, we may assume that $\operatorname{c}(T[U])=1$, $\operatorname{c}(T[W])=2$ and W ₁ and W ₂ are the two connected components of $T[W]$. For each $i\in [2]$, take $z_i\in Z\cap W_i$ and let $\{w_i\}=W_i\cap e_i$. The scenario we now encounter is depicted in Fig. 4.

Figure 4.

Edge boundary of size two in a tree.

Since T is a phylogenetic tree, we have $\mathrm{L}_{T[W_1]}\cup \mathrm{L}_{T[W_2]}\subseteq \mathrm{L}_T$. Accordingly, as $(U\mid W)|_{\mathrm{L}_T}=(U'\mid W')|_{\mathrm{L}_T}=Y\mid Z$, Lemmas 2.3 and 2.8 tell us that, for each $i\in [2]$, $\mathrm{E}_{T[W_i]}\cap \{e_1', e_2'\}$ cannot be a singleton set. Without loss of generality, we distinguish the following two cases.

CASE 1. $\{e_1',e_2'\}\subseteq \mathrm{E}_{T[W_1]}$.

This forces $U'\supseteq U\cup W_2\supseteq U$.

CASE 2. $\{e_1',e_2'\}\cap \mathrm{E}_{T[W]}=\emptyset$.

Since $\widehat{\mathbf{S}}_{T,\{e'_1,e'_2\}}|_{\mathrm{L}_T}=(U'\mid W')|_{\mathrm{L}_T}=Y\mid Z$, we know that $T_{z_1,z_2}\cap \{e_1', e_2'\}$ contains zero or two elements. Given that $\{e_1',e_2'\}\cap \mathrm{E}_{T[W]}=\emptyset$, it follows that $T_{w_1,w_2}\cap \{e_1', e_2'\}$ has size zero or two. This demonstrates that $W'\supseteq W$, as required.

Proof. For each $i\in [2]$, let $T_i=T[\operatorname{C}_{T[W]}[v_i]]$. It is direct from definition that $Y\mid (\mathrm{L}_T\setminus Y)=\mathbf{S}_{T,\{v_1u_1,v_2u_2\}}\in \mathcal{S}_{T,2}$ and $\mathrm{Ext}_{T,Y}\subseteq W$. The latter implies that $\partial_T(\mathrm{Ext}_{T,Y})\subseteq \mathrm{E}_{T[W]}\cup \{v_1u_1,v_2u_2\}= \mathrm{E}_{T_1} \cup \mathrm{E}_{T_2} \cup \{v_1u_1,v_2u_2\} $. Let $\partial_T(\mathrm{Ext}_{T,Y})= \{e_1,e_2\}\in \binom{\mathrm{E}_T}{2}$. By symmetry, it suffices to verify that $E=\emptyset$, where $E\doteq \{e_1,e_2\}\cap \mathrm{E}_{T_1}$.

If $v_1=v_2$, then $\deg_{T_1}(v_1)=\deg_T(v_1)-2 $, and hence, by Eq. (2),

(3)\begin{equation} \deg_{T_1}(v_1)\geqslant 5-2=3. \end{equation}

If $v_1\neq v_2$, then $\deg_{T_1}(v_1)=\deg_T(v_1)-1 \neq 1 $. If $v_1\neq v_2$ and $v_2\in \mathrm{V}_{T_1}$, we have $\deg_{T_1}(v_2)=\deg_T(v_2)-1\neq 1 $. These observations imply that $\mathrm{L}_{T_1}\subseteq Y$. Thus, we can apply Lemma 2.8 to get that $ \mathbf{S}_{T_1,E} =\mathbf{S}_{T,\{e_1,e_2\}}|_{\mathrm{L}_{T_1}} $ is an improper split. Accordingly, Lemma 2.3 tells us that either $E=\emptyset$, or $|{E}|=2$ and $\deg_{T_1}(w)=2$ for all $w\in [e_1,e_2]_{T_1}$. Assume, for the sake of contradiction, that the second possibility happens. Since $\deg_{T_1}(w)\neq 2$ for all $w\in \mathrm{V}_{T_1}\setminus \{v_1,v_2\}$, we know that $\emptyset \neq [e_1,e_2]_{T_1}\subseteq \{v_1,v_2\}$, and hence $2\in \{\deg_{T_1}(v_1), \deg_{T_1}(v_2)\}$. By virtue of Eq. (3), one of $v_1,v_2$ having degree two forces $v_1\neq v_2$. We thus have two cases to consider: 1) $[e_1,e_2]_{T_1}=\{v_1,v_2\}$ is of size two; 2) $[e_1,e_2]_{T_1}=\{v_i\}\subsetneq \{v_1,v_2\}$ for some $i\in [2]$. For case 1), we find that $v_1v_2\in \mathrm{E}_T$ and $\deg_T(v_1)=\deg_T(v_2)=3$. It follows that $\max\{\deg_T(v_1), \deg_T(v_2)\} +\operatorname{dist}_T(v_1,v_2)=4$, violating Eq. (2), as desired. For case 2), we have $\deg_T(v_i)=\deg_{T_1}(v_i)+1=3$ and hence $\{e\in \mathrm{E}_T:\ v_i\in e\}=\{e_1,e_2,v_iu_i\}$. It follows that $\mathbf{S}_{T,\{v_1u_1,v_2u_2\}}=Y\mid (\mathrm{L}_T\setminus Y)=\mathbf{S}_{T,\{e_1,e_2\}}=\mathbf{S}_{T,\{v_iu_i\}}$, which contradicts Lemma 2.5.

Proof. Surely, exactly one of the following possibilities must occur: (a’) $\operatorname{dist}_T(v_1, v_2)=0$; (b’) $\operatorname{dist}_T(v_1, v_2)=1$; (c’) $\operatorname{c}(T[\mathrm{Ext}_{T,Y}])=1$ while $\operatorname{dist}_T(v_1, v_2) \gt 1$; (d’) $\operatorname{c}(T[\mathrm{Ext}_{T,Y}]) \gt 1$, and hence $\operatorname{dist}_T(v_1, v_2) \gt 1$.

Case (c’) corresponds precisely to case (c).

Let $\mathcal{U}=\{U\subseteq \mathrm{V}_T:\ U\mid W\in \widehat{\mathcal{S}}_{T,2}, Y=U\cap \mathrm{L}_T\}$. By definition, $\mathrm{Ext}_{T,Y}$ is the inclusion-minimal element in $\mathcal U$. This means that it cannot happen that $v_1v_2\in \mathrm{E}_T$ and $\deg_T(v_1)=\deg_T(v_2)=3$, as this would imply $\mathrm{Ext}_{T,Y}\setminus \{v_1,v_2\}\in \mathcal{U}$; see Fig. 7(A). We can also exclude the possibility of $v_1=v_2$ and $\deg_T(v_1)= 4$, as this would give $\mathrm{Ext}_{T,Y}-v_1\in \mathcal{U}$; see Fig. 7(B). Since $\mathbf{S}_{T,\{v_1u_1,v_2u_2\}} = Y\mid (\mathrm{L}_T\setminus Y) \in \mathcal{P}_{T,2}$, Corollary 2.6 asserts that neither $v_1=v_2$ and $\deg_T(v_1)=3$ nor $u_1=u_2$ and $\deg_T(u_1)=3$ is valid. Therefore, we now find that cases (a’), (b’) and (d’) are equivalent to (a), (b) and (d), respectively.

Figure 7.

Excluding two possibilities in the proof of Lemma 4.5. A) $\widehat{\mathbf{S}}_{T,\{e_1,e_2\}}=U\mid W$, $\widehat{\mathbf{S}}_{T,\{e'_1,e'_2\}}=U'\mid W'$, $Y\subseteq U'\subseteq U'\cup \{v_1,v_2\}=U$. B) $\widehat{\mathbf{S}}_{T,\{e_1,e_2\}}=U\mid W$, $\widehat{\mathbf{S}}_{T,\{e'_1,e'_2\}}=U'\mid W'$, $Y\subseteq U'\subseteq U'\cup \{v_1\}=U$.

Convention 4.6

For the statements and proofs of Lemmas 4.4, 4.7 and Corollary 4.8, we introduce the following notations. Assume that T is a phylogenetic tree, $Y\mid (\mathrm{L}_T\setminus Y)\in \mathcal{P}_{T,2}$, and $|{Y}|\geqslant 3$. Let $\partial_T(\mathrm{Ext}_{T,Y})=\{v_1u_1,v_2u_2\}$, where $\{v_1,v_2\}\subseteq \mathrm{Ext}_{T,Y}$ and $\deg_T(v_1)\geqslant \deg_T(v_2)$. Let $B_1,\ldots,B_{k'}$ be all distinct sets of the form $\mathrm{L}_T\cap \operatorname{C}_{T-v_1}[u]$, where $ u\in \operatorname{N}_T(v_1) \setminus \{u_1,u_2\}$ and $ v_2\notin \operatorname{C}_{T-v_1}[u] $; let $C_1,\ldots,C_{k^{\prime\prime}}$ be all distinct sets of the form $\mathrm{L}_T\cap \operatorname{C}_{T-v_2}[u]$, where $ u\in \operatorname{N}_T(v_2) \setminus \{u_1,u_2\}$ and $ v_1\notin \operatorname{C}_{T-v_2}[u] $. Let $B\doteq\bigcup_{i\in [k']}B_i$, $C\doteq\bigcup_{i\in [k^{\prime\prime}]}C_i$ and $D\doteq Y\setminus (B\cup C\cup \{v_1,v_2\})$. Note that $B\neq \emptyset$; B = C if and only if $v_1=v_2$; $C=\emptyset$ exactly when $\deg_T(v_2)=1$; $D=\emptyset$ exactly when $T[\mathrm{Ext}_{T,Y}]$ is not connected or $\operatorname{dist}_T(v_1,v_2)\leq 1$. See Fig. 8 for an illustration.

Figure 8.

Distributions of B_i, C_i and D as described in Convention 4.6.

Proof. Let $V=\mathrm{V}_T$, $X=\mathrm{L}_T$ and $W=\mathrm{Ext}_{T,Y}$. Use the notation Δ for $\{Y'\subsetneq Y:\ Y' \mid(X\setminus Y')\in \mathcal{P}_{T,2}\}$. Note that $\Gamma_{\mathcal{P}_{T,2}}(Y)$ consists of all the inclusion-maximal elements of Δ. Let $Y'\in \Delta$ and $W'=\mathrm{Ext}_{T,Y'}$. Since T is a tree, deleting two edges from T results in exactly three connected components in the remaining graph. Therefore, we must have

(4)\begin{equation} \{\operatorname{c}(T[W']),\operatorname{c}(T-W')\}=[2]. \end{equation}

CASE 1. $T[W]$ is connected, and either $v_1\neq v_2$ or $\deg_T(v_1)\geqslant 5$. This includes cases (1), (2), (3) and (4).

Since $T[W] $ is connected, both B and C are non-empty. This gives

(5)\begin{equation} B\neq \emptyset, C\neq \emptyset, Y=B\cup C\cup D, \end{equation}

and allows us to define $ \mathcal{U}_1 \doteq \{B_i \cup C_j:\ i\in [k'],j\in [k^{\prime\prime}], B_i\neq C_j\}\subseteq 2^Y$. We claim that

(6)\begin{equation} \mathcal{U}_1=\{Z\in \Gamma_{\mathcal{P}_{T,2}}(Y):\ Z\cap B\neq \emptyset, Z\cap C\neq \emptyset\}. \end{equation}

Keeping in mind the validity of Eqs. (5) and (6), let us prove statements (1), (2), (3) and (4).

For statement (1), we are reduced to proving $D=\emptyset$ and $\{B_i:\ i\in [k']\}=\{C_j:\ j\in [k^{\prime\prime}]\}$. These follow directly from $v_1=v_2$.

For statement (2), we only need to check that $D=\emptyset$, $k',k^{\prime\prime}\geqslant 2$, and both B and C belong to Δ. The first and second conditions follow directly from $v_1v_2\in \mathrm{E}_T$ and $\deg_T(v_1)\geqslant \deg_T(v_2)\geqslant 4$, respectively. Because $\deg_T(v_1)\geqslant \deg_T(v_2)\geqslant 4$, by Corollary 2.6, $B\mid (X\setminus B)=\mathbf{S}_{T,\{v_1v_2,v_1u_1\}}\in \mathcal{P}_{T,2}$ and $C\mid (X\setminus C)=\mathbf{S}_{T,\{v_1v_2,v_2u_2\}}\in \mathcal{P}_{T,2}$, as desired.

To prove (3), it suffices to verify that $D=\emptyset$, $k' \gt k^{\prime\prime}=1$ and $B \in \Delta$. The first two are direct from $v_1v_2\in \mathrm{E}_T$ and $\deg_T(v_1) \gt \deg_T(v_2)=3$. By Corollary 2.6, the last one follows from $\deg_T(v_1)\geqslant 4$ and $B\mid (X\setminus B)=\mathbf{S}_{T,\{v_1v_2,v_1u_1\}}$.

As for statement (4), it remains to show that $D\neq \emptyset$ and that both $B\cup D$ and $C\cup D$ belong to Δ. The former follows directly from $\operatorname{c}(T[W])=1$ and $\operatorname{dist}_T(v_1,v_2) \gt 1$. To show the latter, by symmetry, it suffices to prove that $(B\cup D)\mid (X\setminus(B\cup D))\in \mathcal{P}_{T,2}$. According to Convention 4.6, there exists $w_2'\in \operatorname{N}_T(v_2)$ such that $D=X\cap \operatorname{C}_{T-v_1-v_2}[w_2']$. Note that $v_1,v_2,u_1$, and $w_2'$ are pairwise distinct. Then, by Corollary 2.6, $(B\cup D)\mid (X\setminus(B\cup D))=\mathbf{S}_{T,\{v_1u_1,v_2w_2'\}}\in \mathcal{P}_{T,2}$, as desired.

To complete the proof in this case, we need to verify Eq. (6). To obtain Eq. (6), we will deduce that $\mathcal{U}_1 \subseteq \Delta$, and that

(7)\begin{equation} Y'\subseteq B_i\cup C_j \end{equation}

whenever $i\in [k']$ and $j\in [k^{\prime\prime}]$ are two elements satisfying $B_i\neq C_j$, $Y'\cap B_i\neq \emptyset$ and $Y'\cap C_j\neq \emptyset$.

Pick $B_i\cup C_j\in \mathcal{U}_1$. On the one hand, $B_i\cup C_j\neq Y$. Otherwise, either $v_1=v_2$ and $\deg_T(v_1)=4$ or $v_1v_2\in \mathrm{E}_T$ and $\deg_T(v_1)=\deg_T(v_2)=3$, violating Lemma 4.5. On the other hand, by Convention 4.6, there are distinct $w_i\in \operatorname{N}_T(v_1)-v_2$ and $w_j\in \operatorname{N}_T(v_2)-v_1$ such that $B_i=X\cap \operatorname{C}_{T-v_1}[w_i]$ and $C_j=X\cap \operatorname{C}_{T-v_2}[w_j]$. As either $v_1\neq v_2$ or $\deg_T(v_1)\geqslant 5$, by Corollary 2.6, $(B_i\cup C_j) \mid (X\setminus (B_i \cup C_j))=\mathbf{S}_{T,\{v_1w_i,v_2w_j\}}$ belongs to $\mathcal{P}_{T,2}$, as desired. This proves $\mathcal{U}_1 \subseteq \Delta$.

If $v_1,v_2\notin W'$, then, by Eq. (4), $\operatorname{c}(T[W']-\{v_1,v_2\})=\operatorname{c}(T[W'])\leq 2$. However, $Y'\setminus (B_i\cup C_j)$, $Y'\cap B_i$ and $Y'\cap C_j$ are pairwise non-reachable in $T[W']-\{v_1,v_2\}$, while $Y'\cap B_i\neq \emptyset$ and $Y'\cap C_j\neq \emptyset$. This forces Eq. (7) to hold. Henceforth, it remains to show that $v_1,v_2\notin W'$. Let us pick $x_0\in Y\setminus Y'$, $x_1\in X \cap \operatorname{C}_{T-v_1}[u_1]$ and $x_2\in X \cap \operatorname{C}_{T-v_2}[u_2]$. Then $x_0,x_1$, and x ₂ are pairwise non-reachable leaves in $T-\{v_1,v_2\}$ and thus in $T-(W'\cup \{v_1,v_2\})$, which means $\operatorname{c}(T-(W'\cup \{v_1,v_2\})) \geqslant 3$. We thus derive from Eq. (4) that at least one of v ₁ and v ₂ does not belong to W′, say v_t. As a result, $Y'\cap B_i\neq \emptyset$ and $Y'\cap C_j\neq \emptyset$ are non-reachable in $T[W']$. It must happen that $\operatorname{c}(T[W'])\geqslant 2$. This, together with Eq. (4), implies that $\operatorname{c}(T-W')=1$. As x ₀ and $x_{3-t}$ are leaves of $T-W'$ that are non-reachable in $T-v_{3-t}$, we conclude that $v_{3-t} \notin W' $, thus completing our proof in Case 1.

CASE 2. $ T [W] $ is not connected. This includes cases (5) and (6).

Before verifying statements (5) and (6), we establish two relevant facts. The first fact is that

(8)\begin{equation} Y' \subseteq B_i \cup (Y\setminus B) \end{equation}

holds for some $i\in [k']$ whenever none of $B\setminus Y' $, $Y'\cap B $ and $Y'\setminus B $ is empty. Observe that, for distinct $i , j \in [k']$, $Y'\cap B_i$, $Y'\cap B_j$ and $Y'\setminus B $ are pairwise non-reachable in $T[W'-v_1]$. Henceforth, if $v_1\notin W'$, we can infer from $\operatorname{c}(T[W'-v_1])=\operatorname{c}(T[W'])\leq 2$ and $Y'\setminus B \neq \emptyset $ that Eq. (8) holds, as desired. Our task is thus to deduce $v_1\notin W'$. Choose $x_0\in B \setminus Y'$ arbitrarily. Since $\{x_0\}\cup (X\setminus Y)\subseteq X\setminus Y'=\mathrm{L}_{T-W'}$ and $v_1\in [\{x_0\}, X\setminus Y]_T$, we only need to check that $\operatorname{c}(T-W')=1$. By Lemma 4.5, it holds that either $ u_1 \neq u_2 $ or $ \deg_T(u_1) \geqslant 4 $. Hence there exists $\{w_1,w_2\}\in \binom{\operatorname{N}_T(u_1) \setminus \{v_1,v_2\}}{2}$. Pick $x_1\in X \cap \operatorname{C}_{T-u_1 }[w_1]$ and $x_2\in X\cap \operatorname{C}_{T-u_1 }[w_2]$. Observe that $x_0,x_1$, and x ₂ are pairwise non-reachable in $T-u_1$ and thus in $T-W'-u_1$. Consequently, $\operatorname{c}(T-W'-u_1)\geqslant 3$. It then follows from $\operatorname{c}(T-W')\leq 2$ that $u_1\notin W'$. This, along with $Y'\cap B\neq \emptyset$ and $Y'\setminus B\neq \emptyset$, implies that $\operatorname{c}(T[W'])\geqslant 2$. We can thus apply Eq. (4) to obtain $\operatorname{c}(T-W')=1$, as desired.

We now want to deduce

(9)\begin{equation} \mathcal{{U}}_2=\{Z\in \Gamma_{\mathcal{P}_{T,2}}(Y):\ Z\nsubseteq B, B\nsubseteq Z, Z\cap B\neq \emptyset\}, \end{equation}

where $\mathcal{{U}}_2\doteq \{B_i\cup(Y\setminus B): i\in [k']\}$. If $\mathcal{{U}}_2 \subseteq \Delta$, then it is clear that Eq. (8) implies Eq. (9). So, what remains to prove is $\mathcal{{U}}_2 \subseteq \Delta$. As $T[W]$ is not connected, it holds that $k'=\deg_T(v_1)-1\geqslant 2$. Hence $Y\notin \mathcal{{U}}_2$. Let $Z=B_i\cup(Y\setminus B)$ for some $i\in [k']$. To finish the proof of $\mathcal{{U}}_2 \subseteq \Delta$, we aim to show that $Z\mid (X\setminus Z)\in \mathcal{P}_{T,2}$. Following Convention 4.6, there is a $w_i\in \operatorname{N}_T(v_1)-u_2$ such that $B_i=X\cap \operatorname{C}_{T-v_1}[w_i]$. By Corollary 2.6, $Z\mid (X\setminus Z)=\mathbf{S}_{T,\{v_1w_i,v_2u_2\}}\in \mathcal{P}_{T,2}$, as desired.

In the sequel, making use of the conditions $k'\geqslant 2$ and Eq. (9) implicitly, we complete the proof of cases (5) and (6).

Let us start with statement (5). From $\deg_T(v_2)=1$ it follows that $Y\setminus B=\{v_2\}$. Thus, for any set Z, $B\subsetneq Z \subseteq Y$ implies Z = Y; either B = Z or $Z\subseteq Y\setminus B$ implies $Z\mid (X\setminus Z)\notin \mathcal{P}_{T,2}$. These observations indicate that $\{Z\subseteq Y:\ B \subseteq Z \text{or } Z\cap B=\emptyset\}$ does not intersect with $\Gamma_{\mathcal{P}_{T,2}}(Y)$. Therefore, we only need to check that

(10)\begin{equation} \{Z\in \Gamma_{\mathcal{P}_{T,2}}(Y):\ Z\subsetneq B\}=\begin{cases} \{B-x:\ x\in B\setminus \operatorname{N}_T(v_1)\}, &\text{if } \deg_T(v_1)=3,\\ \{B-x:\ x\in B \}, &\text{if } \deg_T(v_1)\geqslant 4. \end{cases} \end{equation}

The proof of Eq. (10) is divided into two cases.

1. (1) Either $\deg_T(v_1)\geqslant 4$ or $B \cap \operatorname{N}_T(v_1)=\emptyset$.

   It is sufficient to verify that $B-x\in \Delta$ for all $x\in B$. Consider an arbitrary $x\in B$, and let e be the edge incident to x in T. Whether $\deg_T(v_1)\geqslant 4$ or $B \cap \operatorname{N}_T(v_1)=\emptyset$, the edges $v_1u_1$ and e cannot share a common endpoint of degree three in T. Consequently, by Corollary 2.6, $(B-x)\mid (X\setminus(B-x))=\mathbf{S}_{T,\{v_1u_1,e\}}\in \mathcal{P}_{T,2}$, namely $B-x\in \Delta$.

2. (2) $\deg_T(v_1)=3$ and $B \cap \operatorname{N}_T(v_1)\neq \emptyset$.

   From $\deg_T(v_1)=3$ we have $|{B \cap \operatorname{N}_T(v_1)}|\leq 2$. If $|{B \cap \operatorname{N}_T(v_1)}|= 2$, then $|{Y}|=|{B}|+1=3$, and hence Eq. (10) follows from Corollary 2.7. Now, assume that $B \cap \operatorname{N}_T(v_1)$ contains only one leaf x ₀. Let $\operatorname{N}_T(v_1)=\{u_1,x_0,w\}$. Then, $(B-x_0)\mid (X\setminus(B-x_0))=\mathbf{S}_{T,\{v_1w\}}\notin \mathcal{P}_{T,2}$. Thus, a proper subset of B belonging to Δ must be a subset of B − x for some $x\in B-x_0$. To show Eq. (10), it remains to verify that $B-x\in \Delta$ for all $x\in B-x_0$, which follows from similar arguments in the previous case.

It is time to prove statement (6). From $\deg_T(v_2)\geqslant 3$ and $\operatorname{c}(T[W]) \gt 1$, it follows that $k^{\prime\prime}\geqslant 2$ and $C=Y\setminus B\neq \emptyset$. Since $C=Y\setminus B$, we obtain $\mathcal{U}_2= \{B_i\cup C:\ i\in [k']\}$. Let $ \mathcal{U}_2'\doteq \{C_j \cup B:\ j\in [k^{\prime\prime}]\}$. Our goal is to show that $ \Gamma_{\mathcal{P}_{T,2}}(Y)=\mathcal{U}_2\cup \mathcal{U}_2'$. By switching the roles of B and C and replacing $\{B_i:\ i\in [k']\}$ with $\{C_j:\ j\in[k^{\prime\prime}]\}$, we know from Eq. (9) that $\mathcal{U}_2' =\{Z\in \Gamma_{\mathcal{P}_{T,2}}(Y):\ Z\nsubseteq C, C\nsubseteq Z, Z\cap C\neq \emptyset\}$. Take $Z\in \Gamma_{\mathcal{P}_{T,2}}(Y)\setminus \mathcal{U}_2'$. Then $C\subsetneq Z \subsetneq Y$. This implies $Z\nsubseteq B$, $B\nsubseteq Z$, and $Z\cap B\neq \emptyset$. Thus , $Z\in \mathcal{U}_2$ follows, as was to be shown.

Proof of Lemma 4.4

Let $V=\mathrm{V}_T$ and $X=\mathrm{L}_T$. When (1) holds, we necessarily have $|{Y}| \geqslant 3$ and $Y\mid(X\setminus Y)\in \mathcal{P}_{T,2}$. If (2) holds, the definition of a 2-special configuration implies $|{Y}| \geqslant 3$, and, in view of Corollary 2.6, $Y\mid(X\setminus Y)\in \mathcal{P}_{T,2}$. Henceforth, hereafter we shall assume that $|{Y}| \geqslant 3$, $Y\mid(X\setminus Y)\in \mathcal{P}_{T,2}$, $W\doteq \mathrm{Ext}_{T,Y}$, and adopt the convention from Convention 4.6 regarding $k',k^{\prime\prime},v_1,v_2,B,C,D$, etc.

Let $\Pi\doteq \varrho_2(\Gamma_{\mathcal{P}_{T,2}}(Y))$. It is clear that condition (1) is equivalent to the following condition (1’):

1. (1’) Π is a k-partition of Y, and $\Gamma_{\mathcal{P}_{T,2}}(Y)=\operatorname{\mathcal{H}}_{\Pi, 2}$.

According to Lemma 4.5, there are four cases to consider. We are going to establish the equivalence between (1’) ((1)) and (2) in each of these cases.

CASE 1. $v_1=v_2$ and $\deg_T (v_1)\geqslant 5$, as given in Lemma 4.5 (a) and shown in Fig. 9(A).

In this case, (T, Y) is a 2-special configuration of type A and $\phi_T(Y)=k'$. Hence, (2) amounts to requiring $k=k'$.

By Lemma 4.7 (1), $ \Gamma_{\mathcal{P}_{T,2}}(Y) = \bigl\{B_i\cup B_j:\ \{i,j\}\in \binom{[k']}{2}\bigr\}$, which states that Y is a $(k',2)$-set with respect to $\mathcal{P}_{T,2}$. Therefore, (1) also holds if and only if $k=k' $.

CASE 2. $v_1v_2\in \mathrm{E}_T$ and $\deg_T( v_1) =\max \{\deg_T( v_1), \deg_T( v_2) \}\geqslant 4$. This corresponds to Lemma 4.5 (b), as shown in Fig. 9(B).

In this case, $D=\emptyset$, $k'=\deg_T (v_1)-2\geqslant 2$, $k^{\prime\prime}=\deg_T (v_2)-2$, and $ \phi_T(Y)=k'+k^{\prime\prime}$.

CASE 2.1. $\deg_T (v_2)\geqslant 4$, which means that $k^{\prime\prime}\geqslant 2$.

In this case, (T, Y) is a 2-special configuration if and only if its type is B. Thus, (2) is equivalent to $k'=k^{\prime\prime}=2$ and k = 4.

It follows from Lemma 4.7 (2) that

\begin{equation*} \Pi =\{B_i:\ i\in [k']\}\cup \{C_j:\ j\in [k^{\prime\prime}]\}, \end{equation*}

which is a $(k'+k^{\prime\prime})$-partition of Y. Having a look into Lemma 4.7 (2) again, we find that $ \Gamma_{\mathcal{P}_{T,2}}(Y) =\operatorname{\mathcal{H}}_{\Pi,2} $ if and only if $k'=k^{\prime\prime}=2$. Combining these two facts yields that (1’) is also equivalent to $k'=k^{\prime\prime}=2$ and k = 4.

CASE 2.2. $\deg_T (v_2)=3$, equivalently $k^{\prime\prime}=1$. In this case, (T, Y) is a 2-special configuration if and only if its type is C. Therefore, (2) is equivalent to $k=k'+1=3$.

In view of Lemma 4.7 (3), we have

\begin{equation*} \Pi =\{B_i:\ i\in [k']\}\cup \{C \}, \end{equation*}

which is a $(k'+1)$-partition of Y. Comparing it with Lemma 4.7 (3), we know that $\Gamma_{\mathcal{P}_{T,2}}(Y) =\operatorname{\mathcal{H}}_{\Pi,2} $ if and only if $k'=2$. Thus, (1’) is also equivalent to $k=k'+1=3$.

CASE 3. $T[W]$ is connected and $\operatorname{dist}_T(v_1,v_2) \gt 1$, as given in Lemma 4.5 (c) and shown in Fig. 9(C).

Figure 9.

Different cases in the proof of Lemma 4.4. A) Case 1 B) Case 2 C) Case 3 D) Case 4

In this case, $k'=\deg_T(v_1)-2\geqslant 1$, $k^{\prime\prime}=\deg_T(v_2)-2\geqslant 1$ and $\phi_T(Y)=k'+k^{\prime\prime}+1$. Additionally, (T, Y) is a 2-special configuration if and only if it is of type D, which is equivalent to $\deg_T(v_1)= \deg_T(v_2)=3 $. Hence, (2) holds if and only if $k'=k^{\prime\prime}=1$ and k = 3.

By Lemma 4.7 (4), it happens $\Gamma_{\mathcal{P}_{T,2}}(Y)=\{B_i\cup C_j:\ i\in[k'], j\in [k^{\prime\prime}]\} \cup \{B\cup D, C\cup D\}$. Accordingly,

\begin{equation*} \Pi=\{B_i:\ i\in[k']\} \cup \{C_j:\ j\in [k^{\prime\prime}]\} \cup \{D\}, \end{equation*}

which is a $(k'+k^{\prime\prime}+1)$-partition of Y. We see that $\Gamma_{\mathcal{P}_{T,2}}(Y)=\operatorname{\mathcal{H}}_{\Pi,2}$ if and only if $k'=k^{\prime\prime}=1$. Thus, (1’) is also equivalent to $k'=k^{\prime\prime}=1$ and $k=k'+k^{\prime\prime}+1=3$.

CASE 4. $ T [W] $ is not connected, and either $u_1\neq u_2$ or $\deg_T(u_1)\geqslant 4$. This corresponds to the case of Lemma 4.5 (d), as illustrated in Fig. 9(D).

CASE 4.1. $v_2\in \mathrm{L}_T$, namely $\deg_T(v_2)=1$.

Note that $Y=B+v_2$. We thus derive from $|{Y}|\geqslant 3$ that $\phi_T(Y)=\deg_T(v_1)=k'+1\geqslant 3$.

CASE 4.1.1. Suppose $\deg_T(v_1)=3 $, and hence (T, Y) is not a 2-special configuration and $k'=2$. In this case, statement (2) cannot hold. By virtue of $k'=2$, Lemma 4.7 (5) yields that $\{B_i+v_2:\ i\in [2]\}\subseteq \Gamma_{\mathcal{P}_{T,2}}(Y)$ and $\{v_2\}\in \Pi$. Thus, if $\Gamma_{\mathcal{P}_{T,2}}(Y)=\operatorname{\mathcal{H}}_{\Pi,2}$, then $\Pi=\bigl\{\{v_2\}, B_1, B_2 \bigr\} $ and hence $B=B_1\cup B_2 \in \operatorname{\mathcal{H}}_{\Pi,2} \setminus \Gamma_{\mathcal{P}_{T,2}}(Y)$. Therefore, statement (1’) cannot hold either.

CASE 4.1.2. Suppose $\deg_T(v_1)\geqslant 4$. Whenever (T, Y) is a 2-special configuration, its type must be E. By further taking into account that $|{Y}|=|{B}|+1\geqslant k'+1=\phi_T(Y)=\deg_T(v_1)\geqslant 4$, (2) holds if and only if $k' = |{B}| =3 $.

From Lemma 4.7 (5) and $|{B}|\geqslant 3$, it follows that

\begin{equation*} \Pi=\binom{B}{|{B}|-2} \cup \left(\bigcup_{i: |{B_i}|\geqslant 2, i\in [k']}\binom{B_i}{|{B_i}|-1}\right) \cup \{B_i:\ i\in [k']\} \cup \left\{\{v_2\}\right\}. \end{equation*}

As $\binom{B}{|{B}|-2}\subseteq \Pi$, Π is a k-partition for $k\geqslant 3$ only if $|{B}|=3$. If $|{B}|=3$, then $k'=3$ and by Lemma 4.7 (5) we see that (1’) holds. Thus (1’) is also equivalent to $k' = |{B}| =3 $.

CASE 4.2. $\deg_T(v_2)\geqslant 3$.

In this case, $ k'=\deg_T(v_1)-1\geqslant 2$, $k^{\prime\prime}= \deg_T(v_2)-1\geqslant 2$ and (2) cannot hold. By Lemma 4.7 (6), $B_i\cup C_j\in \Pi$ for each $i\in [k']$ and $j\in [k^{\prime\prime}]$. Thus, Π is not a partition, implying that (1’) cannot hold either.

Proof. As (T, Y) is a 2-special configuration and $\varrho_2(\Gamma_{\mathcal{P}_{T,2}}(Y))=\{Y_1, \dots, Y_k \}$, from Lemma 4.4 it follows that Y is a $(k,2)$-set with respect to $\mathcal{P}_{T,2}$ and $k=\phi_T(Y)=\operatorname{c}(T[\mathrm{Ext}_{T,Y}]-(\{v_1,v_2\}\setminus \mathrm{L}_T))$. Thus we can enumerate the connected components of $T[\mathrm{Ext}_{T,Y}]-(\{v_1,v_2\}\setminus \mathrm{L}_T)$ as $V_1,\ldots,V_k$.

Adopt notations from Convention 4.6. We see from Fig. 6 that

\begin{equation*}\{V_i\cap \mathrm{L}_T: i\in [k]\}=\begin{cases} \{B_i: i\in [k']\}\cup \{C_j:\ j\in [k^{\prime\prime}]\}, & \text{if} \ (T,Y) \ \text{is of type } \mathtt{A}, \mathtt{B} \text{ or } \mathtt{C},\\ \{B, C, D\}, & \text{if} \ (T,Y) \ \text{is of type } \mathtt{D},\\ \bigl\{\{y\}:\ y\in Y \bigr\}, & \text{if} \ (T,Y) \ \text{is of type } \mathtt{E}. \end{cases}\end{equation*}

According to Lemma 4.7, we have

\begin{equation*}\varrho_2(\Gamma_{\mathcal{P}_{T,2}}(Y))=\begin{cases} \{B_i: i\in [k']\}\cup \{C_j:\ j\in [k^{\prime\prime}]\}, & \text{if} \ (T,Y) \ \text{is of type } \mathtt{A}, \mathtt{B} \text{ or } \mathtt{C},\\ \{B, C, D\}, & \text{if} \ (T,Y) \ \text{is of type } \mathtt{D},\\ \bigl\{\{y\}:\ y\in Y \bigr\}, & \text{if} \ (T,Y) \ \text{is of type } \mathtt{E}. \end{cases}\end{equation*}

Therefore, it follows that $\{V_i\cap \mathrm{L}_T:\ i\in [k]\}=\varrho_2(\Gamma_{\mathcal{P}_{T,2}}(Y))=\{Y_1, \dots, Y_k \}$.

Proof. (1). By Corollary 4.8 and Remark 4.9, there exist $w_1, w_2\in \operatorname{N}_T(v_1)\cup \operatorname{N}_T(v_2)$ such that $Y_i=\mathrm{L}_T \cap \operatorname{C}_{T-\{v_1,v_2\}}[w_1]$ and $Y_j=\mathrm{L}_T \cap \operatorname{C}_{T-\{v_1,v_2\}}[w_2]$. Since $v_1,v_2\in [Y_i,Y_j]_T$, it follows that $v_1,v_2\in [w_1,w_2]_T$. Thus, by symmetry we may assume that $w_1\in \operatorname{N}_T(v_1)$ and $w_2\in \operatorname{N}_T(v_2)$. Denote $\operatorname{C}_{T-\{w_1,w_2\}}[v_1]$ by W. Then $Y_{ij}=W\cap \mathrm{L}_T$, $\partial_T(W)= \{v_1w_1,v_2w_2\}$ and $\{v_1,v_2\} \subseteq W$. As v ₁ and v ₂ satisfy Eq. (2), by Lemma 2.11, W is exactly $\mathrm{Ext}_{T,Y_{ij}}$. Because $T[W]$ is connected, by the definitions of types A, B, C and D, $(T,Y_{ij})$ is a 2-special configuration of the same type as (T, Y). Then, by Lemma 4.4, Y_ij is a $(k,2)$-set with respect to $\mathcal{P}_{T,2}$, as desired.

(2). From the above proof of (1), we know that $(T, Y_{ij})$ is a 2-special configuration of type A. Since $v_1=v_2$ and $Y_{ij}\mid (Y_i\cup Y_j)=\mathbf{S}_{T,\{v_1w_1,v_2w_2\}}$, the claim follows directly from Corollary 4.8.

Proof. We start with (1). By Lemma 4.4, Y ₁₂ being a $(4,2)$-set with respect to $\mathcal{P}_{T,2}$ implies that (T, Y) is a 2-special configuration. Clearly, $Y_{12}=\mathbf{S}_{T,\{v_1u_1,v_1v_2\}}$ while u ₁ and v ₂ satisfy Eq. (2). Thus, by Lemma 2.11, $\mathrm{Ext}_{T,Y_{12}}=\operatorname{C}_{T-v_1}[u_1]\cup \operatorname{C}_{T-v_1}[v_2]$. Since $T[\mathrm{Ext}_{T,Y_{12}}]$ is not connected, the only possible type of $(T,Y_{12})$ is E. The definition of type E requires that each Y_i, $i\in \{3,4,5,6\}$, consists of a single element. Similarly, if Y ₃₄ is a $(4,2)$-set with respect to $\mathcal{P}_{T,2}$, then all Y_i, $i\in \{1,2,5,6\}$, have size one. In conclusion, if both Y ₁₂ and Y ₃₄ are $(4,2)$-sets with respect to $\mathcal{P}_{T,2}$, then all Y_i, $i\in [6]$, are singleton sets, which implies that $T\cong \widetilde{\mathtt{A}}_0$.

Now, we consider (2). Suppose the type of (T, Y) is C or D. Let w ₂ be the unique vertex in $\operatorname{N}_T(v_2)\cap [v_1,v_2]_T$. Then $Y_{12}=\mathbf{S}_{T,\{v_1u_1, w_2v_2\}}$ while u ₁ and v ₂ satisfy Eq. (2). Hence, by Lemma 2.11, $\mathrm{Ext}_{T,Y_{12}}=\operatorname{C}_{T-v_1}[u_1]\cup \operatorname{C}_{T-w_2}[v_2]$. Note that $T[\mathrm{Ext}_{T,Y_{12}}]$ is not connected and $\deg_T(v_2)=3$. By definition, (T, Y) is not a 2-special configuration. Consequently, by Lemma 4.4, Y ₁₂ is not a $(3,2)$-set with respect to $\mathcal{P}_{T,2}$.

At last, we examine (3). By symmetry, suppose $\{i,j\}=[2]$. Denote the only leaf in Y_i by y_i for each $i\in [3]$. It is clear that $Y_{12}\mid \{y_1,y_2\}=\mathbf{S}_{T,\{v_1y_3,v_1u_1\}}$. Let $U\doteq \mathrm{V}_T\setminus \{y_1,y_2,v_1\}$. From $\widehat{\mathbf{S}}_{T,\{v_1y_3,v_1u_1\}}=U\mid \{y_1,y_2,v_1\}$, it follows that $\{y_3,v_2\}\subseteq\mathrm{Ext}_{T,Y_{12}}\subseteq U$. Since y ₃ and v ₂ are not reachable in $T[U]$, $T[\mathrm{Ext}_{T,Y_{12}}]$ is not connected. Therefore, by Lemma 4.4, Y ₁₂ is a $(4,2)$-set with respect to $\mathcal{P}_{T,2}$ if and only if $(T,Y_{12})$ is a 2-special configuration of type E. The latter condition is equivalent to $\mathrm{L}_T\setminus \{y_1,y_2,y_3\}$ being a claw of T, i.e., $T\cong \widetilde{\mathtt{A}}_0$.

Proof. The sufficiency follows from Corollary 4.10 (1), while the necessity follows from Lemma 4.12.

Proof. By symmetry, it suffices to verify the result for $I=[3]$ and $j\in \{5,6\}$. We only consider the case $I=[3]$ and j = 5, as the case $I=[3]$ and j = 6 can be verified with the same argument.

There exist $e_1,e_2\in \mathrm{E}_T$ such that $((\bigcup_{i\in [3]}Y_i)+w)\mid ((\bigcup_{i\in \{4,5,6\}}Y_i)-w)=\mathbf{S}_{T,\{e_1,e_2\}}$. Let $T'=T-V_5$ and $w_4\in V_4\cap \operatorname{N}_T(v_2)$, where $V_i\doteq \operatorname{C}_{T-\{v_1,v_2\}}[Y_i]$ for $i=4,5$. Because $v_2w_4$ and $v_2u_2$ are not incident with a common vertex of degree 3 in T′, combining Lemma 2.8 and Corollary 2.6 yields $\mathbf{S}_{T',\{e_1,e_2\}\cap \mathrm{E}_{T'}}=\mathbf{S}_{T,\{e_1,e_2\}}|_{\mathrm{L}_{T'}}=(Y_1\cup Y_2\cup Y_3)\mid (Y_4 \cup Y_6)=\mathbf{S}_{T',\{v_2w_4,v_2u_2\}}\in \mathcal{P}_{T',2}$. This implies $e_1,e_2\in \mathrm{E}_{T'}$. Consequently, $\mathbf{S}_{T,\{e_1,e_2\}}|_{Y_5}=\{w\}\mid (Y_5-w)$ is improper, which means $Y_5=\{w\}$, as desired.

Proof. We assume that $\{x,y,z\}$ is a claw of T. Let u ₀ be the common neighbor of $x,y$, and z in T, and let v ₀ be the only vertex in $ \operatorname{N}_T(u_0)\setminus\{x,y,z\}$. Let

\begin{equation*}W=\begin{cases} \mathrm{L}_T\setminus (\operatorname{N}_T(v_0)\cup \{x,y,z\}), & \text{if }\deg_T(v_0)=3,\\ \mathrm{L}_T\setminus \{x,y,z\} ,& \text{otherwise}. \end{cases}\end{equation*}

It follows from $|{\mathrm{L}_T}|\geqslant 7$ that $|{W}|\geqslant 3$. Let $w\in W$. It is easy to verify that $\mathrm{Ext}_{T,\{x,y,z,w\}}=\{x,y,z,w,u_0\}$, and thus $(T,\{x,y,z,w\})$ is a 2-special configuration of type E. Then, by Lemma 4.4, $\{x,y,z,w\}$ is a $(4,2)$-set with respect to $\mathcal{P}_{T,2}$. Consequently, $\{x,y,z\}\in \mathcal{Y}^{\text{claw}}(\mathcal{P}_{T,2}) $.

Conversely, suppose that $\{x,y,z\}\in \mathcal{Y}^{\text{claw}}(\mathcal{P}_{T,2}) $. That is, there exists $\{w_1, w_2, w_3\}\in \binom{\mathrm{L}_T\setminus \{x,y,z\}}{3}$ such that $\{x,y,z,w_i\}$ is a $(4,2)$-set with respect to $\mathcal{P}_{T,2}$ for all $i\in [3]$. This, together with Lemma 4.4 and the condition $\max_{v\in \mathrm{V}_T}\deg_T(v)\leq 4$, reveals that $(T,\{x,y,z,w_i\})$ is a 2-special configuration of type B or E for each $i\in[3]$. Since a leaf is contained in at most one claw of T, to prove that $\{x,y,z\}$ is a claw of T, it suffices to show that the type of $(T, \{x,y,z,w_i\})$ is E for each $i\in [3]$, which would mean that $\{x,y,z,w_i\}$ contains a claw of T. If $(T,\{x,y,z,w_i\})$ is of type B, then applying Lemma 4.14 with $Y=\{x,y,z,w_i\}$ yields $\mathrm{L}_T\setminus Y=\{w_1, w_2 , w_3\}-w_i$, which violates the assumption $|{\mathrm{L}_T}|\geqslant 7$; see Fig. 10.

Figure 10.

A possible tree appeared in the proof of Lemma 4.15.