of quartet compatibility [@Steel92]. Grunewald et al. [@Grunewald2008] characterized quartet compatibility problem in terms of finding an unification sequence for a structure called the quartet graph.

Vakati and Fernández-Baca characterized the tree compatibility problem in terms of finding a legal triangulation [@Vakati11] of the display graph of a profile, a graph introduced by Bryant and Lagergren [@BryantLagergren06]. Gysel et al. introduced the edge label intersection graph for a profile of phylogenetic trees and used this graph to characterize tree compatibility as a chordal sandwich problem [@Gysel2012]. Here we show that the latter characterization translates to a characterization in terms of minimal cuts of display graphs. We also show how such cuts are closely related to the splits of the compatible supertree. Finally, we show how these two characterizations relate to the legal triangulation characterization given in [@Vakati11].

Preliminaries
=============

For every nonnegative integer $m$, we denote the set $\{1, \dots, m\}$ by $[m]$. Let $G$ be a graph. We represent the vertices and edges of $G$ by $V(G)$ and $E(G)$ respectively. For any $U \subseteq V(G)$, $G-U$ represents the graph derived by removing vertices of $U$ and their incident edges from $G$. Similarly, for any $F \subseteq E(G)$, $G-F$ represents 