Characterizing path-length matrices of unrooted binary trees

We extend some recent results on the necessary and sufficient conditions that a symmetric integer matrix of order n ≥ 3 must satisfy to encode the Path-Length Matrix (PLM) of a Unrooted Binary Tree (UBT) with n leaves. This problem is at the core of the combinatorics of the Balanced Minimum Evolution Problem, a NP-hard problem much studied in the literature on molecular phylogenetics. We show that, for any natural 3 ≤ n ≤ 11, a reduced set of known conditions, excluding Buneman’ strong four-point conditions, is both necessary and sufficient to characterize PLMs of UBTs. In addition, we present a second and more general characterization based solely on linear conditions derived from the topological properties of UBTs.