parallel minimal cuts for $G({\ensuremath{\mathcal{P}}})$.

The next result follows from Theorems \[thm:edge\_label\] and \[thm:maximal\_seps\_equals\_maximal\_cuts\].

\[thm:cuts\_equal\_compatibility\] A profile ${\ensuremath{\mathcal{P}}}$ of unrooted phylogenetic trees is compatible if and only if there exists a complete set of pairwise parallel legal minimal cuts for $G({\ensuremath{\mathcal{P}}})$.

An analogue of Theorem \[thm:cuts\_equal\_compatibility\] can be derived for the edge label intersection graph $L({\ensuremath{\mathcal{P}}})$ as follows. A set ${\ensuremath{\mathcal{F}}}$ of legal minimal separators of $L({\ensuremath{\mathcal{P}}})$ is *complete*, if for every internal edge $e$ of an input tree $T$, there exists a separator $F \in {\ensuremath{\mathcal{F}}}$ where $e$ is the only vertex of $L(T)$ in $F$. The next theorem follows from Theorems \[thm:cuts\_seps\] and \[thm:cuts\_equal\_compatibility\], and Lemma \[lm:parallel\].

A profile ${\ensuremath{\mathcal{P}}}$ of unrooted phylogenetic trees is compatible if and only if there exists a complete set of pairwise parallel legal minimal separators for $L({\ensuremath{\mathcal{P}}})$.

Relationship to splits compatibility
====================================

A *split* of a label set $L$ is a bipartition of $L$. We denote a split $\{X, Y\}$ by $X|Y$. Let $T$ be a phylogenetic tree. Consider an internal edge $e$ of $T$. Deletion of $e$ breaks $T$ into two subtrees $T_1$ and $T_2$. Let $L_1$ and $L_2$ denote the set of all labels in $T_1$ and $T_2$ respectively. Set 