edge. Let $H$ be a subgraph of $G({\ensuremath{\mathcal{P}}})$. We represent by ${\ensuremath{\mathcal{L}}}(H)$, the set of all leaf vertices of $H$. A triangulation $G'$ of $G({\ensuremath{\mathcal{P}}})$ is *legal* if it satisfies the following conditions.

1.  For every clique $C$ of $G'$, if $C$ contains an internal edge, then it cannot contain any other edge of $G({\ensuremath{\mathcal{P}}})$.

2.  There does not exist a fill-in edge with a leaf vertex as an endpoint.

\[thm:lt\] A profile ${\ensuremath{\mathcal{P}}}$ of unrooted phylogenetic trees is compatible if and only if $G({\ensuremath{\mathcal{P}}})$ has a legal triangulation.

The *edge label intersection* graph (see Fig. \[fig:example\]) of a profile ${\ensuremath{\mathcal{P}}}$, denoted $L({\ensuremath{\mathcal{P}}})$, is the graph whose vertex set is the set of all edges of input trees of ${\ensuremath{\mathcal{P}}}$ where there is an edge between vertices $e$ and $e'$ if and only if $e \cap e' \neq \emptyset$ [@Gysel2012]. (Note that in [@Gysel2012], $L({\ensuremath{\mathcal{P}}})$ is the modified edge label intersection graph.)

It can be verified that $L({\ensuremath{\mathcal{P}}})$ is the line graph of $G({\ensuremath{\mathcal{P}}})$ [@Gysel2012]; i.e., the vertices of $L({\ensuremath{\mathcal{P}}})$ are the edges of $G({\ensuremath{\mathcal{P}}})$ and two vertices in $L({\ensuremath{\mathcal{P}}})$ are adjacent if the corresponding edges in $G({\ensuremath{\mathcal{P}}})$ share a common endpoint.

A fill-in edge of $L({\ensuremath{\mathcal{P}}})$ is *valid* if 