Buneman's theorem for trees with exatcly n vertices

Abstract

Let $\mathcal{T}=(T,w)$ be a positive-weighted tree with at least $n$ vertices. For any $i,j\in \{1,...,n\}$, let $D_{i,j}(\mathcal{T})$ be the weight of the unique path in $T$ connecting $i$ and $j$. The $D_{i,j}(\mathcal{T})$ are called $2$-weights of $\mathcal{T}$ and, if we put in order the $2$-weights, the vector which has the $D_{i,j}(\mathcal{T})$ as components is called \emph{$2$-dissimilarity vector} of $\mathcal{T}$. Given a family of positive real numbers $\{D_{i,j}{\}}_{i,j\in \{1,...,n\}}$, we say that a positive-weighted tree $\mathcal{T}=(T,w)$ realizes the family if $\{1,...,n\}\subset V(T)$ and $D_{i,j}(\mathcal{T})=D_{i,j}$ for any $i,j\in \{1,...,n\}$. A characterization of $2$-dissimilarity families of positive weighted trees is already known (see \cite{B}, \cite{SimP} or \cite{St}): the families must satisfy the well-known \emph{four-point condition}. However we can wonder when there exists a positive-weighted tree with \emph{exactly} $n$ vertices, $1,...,n,$ and realizing the family $\{D_{i,j}\}$. In this paper we will show that the four-point condition is necessary but no more sufficient, and so we will introduce two additional conditions (see Theorem \ref{thm:ThmAgne}).