  Deciding whether a collection of unrooted trees is compatible is a
fundamental problem in phylogenetics. Two different graph-theoretic
characterizations of tree compatibility have recently been proposed. In one of
these, tree compatibility is characterized in terms of the existence of a
specific kind of triangulation in a structure known as the display graph. An
alternative characterization expresses the tree compatibility problem as a
chordal graph sandwich problem in a structure known as the edge label
intersection graph. In this paper we show that the characterization using edge
label intersection graphs transforms to a characterization in terms of minimal
cuts of the display graph. We show how these two characterizations are related
to compatibility of splits. We also show how the characterization in terms of
minimal cuts of display graph is related to the characterization in terms of
triangulation of the display graph.
