Compatible decompositions and block realizations of finite metrics

Given a metric D defined on a finite set X , we define a finite collection D of metrics on X to be a compatible decomposition of D if any two distinct metrics in D are linearly independent (considered as vectors in R X × X ), D = ∑ d ∈ D d holds, and there exist points x , x ′ ∈ X for any two distinct metrics d , d ′ in D such that d ( x , y ) d ′ ( x ′ , y ) = 0 holds for every y ∈ X . In this paper, we show that such decompositions are in one-to-one correspondence with (isomorphism classes of) block realizations of D , that is, graph realizations G of D for which G is a block graph and for which every vertex in G not labelled by X has degree at least 3 and is a cut point of G . This generalizes a fundamental result in phylogenetic combinatorics that states that a metric D defined on X can be realized by a tree if and only if there exists a compatible decomposition D of D such that all metrics d ∈ D are split metrics, and lays the foundation for a more general theory of metric decompositions that will be explored in future papers.