both its endpoints are not from $L(T)$ for some input tree $T$. A triangulation $H$ of $L({\ensuremath{\mathcal{P}}})$ is *restricted* if every fill-in edge of $H$ is valid.

\[thm:EL\_compatibility\] A Profile ${\ensuremath{\mathcal{P}}}$ of unrooted phylogenetic trees is compatible if and only if there exists a restricted triangulation of $L({\ensuremath{\mathcal{P}}})$.

For rest of the paper we will assume that for any profile ${\ensuremath{\mathcal{P}}}$, $G({\ensuremath{\mathcal{P}}})$ is connected. Otherwise, there exists a partition ${\ensuremath{\mathcal{P}}}_{part}$ of ${\ensuremath{\mathcal{P}}}$ such that for every $P \in {\ensuremath{\mathcal{P}}}_{part}$, $G(P)$ is connected and $P$ is maximal such set. Then, ${\ensuremath{\mathcal{P}}}$ is compatible if and only if $P$ is compatible for every $P \in {\ensuremath{\mathcal{P}}}_{part}$. Note that, if $G({\ensuremath{\mathcal{P}}})$ is connected, then $L({\ensuremath{\mathcal{P}}})$ is also connected.

Characterization using minimal cuts
===================================

Let ${\ensuremath{\mathcal{P}}}= \{T_1, T_2, \cdots, T_k\}$ be a profile of phylogenetic trees. A minimal separator $F$ of $L({\ensuremath{\mathcal{P}}})$ is *legal* if for every $F' \subseteq F$ such that $F' \subseteq V(L(T))$ for some input tree $T$, $F'$ is a clique in $L(T)$.

\[thm:edge\_label\] Profile ${\ensuremath{\mathcal{P}}}$ is compatible if and only if there exists a maximal set ${\ensuremath{\mathcal{F}}}$ of pairwise parallel minimal separators in $L({\ensuremath{\mathcal{P}}})$ where every separator in ${\ensuremath{\mathcal{F}}}$ is legal.

Assume that ${\ensuremath{\mathcal{P}}}$ is compatible. From Theorem \[thm:EL\_compatibility\], there 