Figure \[fig:gadgets\] and increment $q$ by one.

(ii) For each $c_r\in C_\ell$ with $c_r=(a_i,a_j,a_k)$ in turn, replace the leaf $D_q$ in ${{\mathcal S}}_\ell$ (resp. ${{\mathcal S}}_\ell'$) with the 8-taxon tree on the top right (resp. bottom right) in Figure \[fig:gadgets\] and increment $q$ by one.

(iii) For each $a_i\in A_\ell$ in turn, replace the leaf $D_q$ in ${{\mathcal S}}_\ell$ and ${{\mathcal S}}_\ell'$ with the cherry $\{a_i,d_q\}$ and increment $q$ by one.

(iv) For each element in $\{q,q+1,\ldots,|A'|\}$, replace the leaf label $D_q$ in ${{\mathcal S}}_\ell$ and ${{\mathcal S}}_\ell'$ with $d_q$.

![Gadgets for a pair $(a_i,a_j)$ (left) and gadgets for a triple $(a_i,a_j,a_k)$ (right) that are used in the reduction from [4-Disjoint-Intermezzo]{} to [CPS-Existence]{}.[]{data-label="fig:gadgets"}](gadgets){width=".6\textwidth"}

We call ${{\mathcal P}}_I=\{{{\mathcal T}}_\ell,{{\mathcal T}}_\ell' \mid 1 \leq \ell \leq 4\}$ the set of [*intermezzo trees*]{} associated with $I$. The next observation is an immediate consequence from the above construction and the fact that, for each $1 \leq \ell \leq 4$, the elements in $B_\ell$ and $C_\ell$ are pairwise disjoint.

For an instance $I$ of [4-Disjoint-Intermezzo]{}, the set of intermezzo trees associated with $I$ consists of eight pairwise non-isomorphic rooted binary phylogenetic trees whose set of leaves is $A'\cup D$.

We now establish the main result 