On spaces extremal for the Gomory-Hu inequality (Q498716)

Fix a finite ultra metric space \((X,d)\). The Gomory-Hu inequality states that \(|\mathrm{Sp}(X)|\leq|X|\), where \(\mathrm{Sp}(X)=\{d(x,y) : x,y\in X\}\). Associate with \((X,d)\) the complete weighted graph \((G_X,w_d)\) where \(G_X\) has vertices \(X\) and, for \(x\not=y\in X\), \(w_d(\{x,y\})=d(x,y)\). If \(|X|\geq 3\) then \(|\mathrm{Sp}(X)|=|X|\) if and only if there is a Hamiltonian path (equivalently cycle) in \(G_X\) having exactly two edges with the maximum weight and all other edges distinct weights. The number of non-isometric \((X,d)\) satisfying \(|\mathrm{Sp}(X)|=|X|\) for a given \(\mathrm{Sp}(X)\) is determined.