internal edge, then ${\ensuremath{\mathcal{L}}}(G_i)$ is non-empty. Assume that $e=\{u,v\}$ is an internal edge of some input tree $T$. If $F$ does not contain an edge of $T$, then ${\ensuremath{\mathcal{L}}}(T) \subseteq {\ensuremath{\mathcal{L}}}(G_i)$ and thus ${\ensuremath{\mathcal{L}}}(G_i)$ is non empty. Assume that $F$ contains one or more edges of $T$. Let $T_u$, $T_v$ be the two subtrees of $T-e$. Since $F$ is a legal minimal cut, $F$ contains edges from either $T_u$ or $T_v$ but not both. Without loss of generality assume that $F$ does not contain edges from $T_u$. Then, every edge of $T_u$ will be in the same component as $e$. Since $T_u$ contains at least one leaf vertex, ${\ensuremath{\mathcal{L}}}(G_i)$ is non-empty. Thus, ${\ensuremath{\mathcal{L}}}(G_1)|{\ensuremath{\mathcal{L}}}(G_2)$ is a split of ${\ensuremath{\mathcal{L}}}({\ensuremath{\mathcal{P}}})$.

For any legal minimal cut $F$ of $G({\ensuremath{\mathcal{P}}})$, we denote by $\Sigma(F)$ the split of ${\ensuremath{\mathcal{L}}}({\ensuremath{\mathcal{P}}})$ induced by $F$. If ${\ensuremath{\mathcal{F}}}$ is a set of legal minimal cuts of $G({\ensuremath{\mathcal{P}}})$, then we denote $\bigcup_{F \in {\ensuremath{\mathcal{F}}}}\Sigma(F)$ by $\Sigma({\ensuremath{\mathcal{F}}})$.

\[lm:parallel\_implies\_compatible\] Let $F_1$ and $F_2$ be two parallel legal minimal cuts of $G({\ensuremath{\mathcal{P}}})$. Then, $\Sigma(F_1)$ and $\Sigma(F_2)$ are compatible.

Let $\Sigma(F_1) = U_1| U_2$ and $\Sigma(F_2) = V_1|V_2$. Assume that $\Sigma(F_1)$ and $\Sigma(F_2)$ are incompatible. Thus, the intersection of $U_i$ and $V_j$ for every 