A note on 3-Steiner intervals and betweenness

The geodesic and geodesic interval, namely the set of all vertices lying on geodesics between a pair of vertices in a connected graph, is a part of folklore in metric graph theory. It is also known that Steiner trees of a (multi) set with k (k>2) vertices, generalize geodesics. In Brešar et al. (2009) 1], the authors studied the k-Steiner intervals S(u₁,u₂,…,u_k) on connected graphs (k≥3) as the k-ary generalization of the geodesic intervals. The analogous betweenness axiom (b2) and the monotone axiom (m) were generalized from binary to k-ary functions as follows. For any u₁,…,u_k,x,x₁,…,x_k∈V(G) which are not necessarily distinct, The authors conjectured in Brešar et al. (2009) 1] that the 3-Steiner interval on a connected graph G satisfies the betweenness axiom (b2) if and only if each block of G is geodetic of diameter at most 2. In this paper we settle this conjecture. For this we show that there exists an isometric cycle of length 2k+1, k>2, in every geodetic block of diameter at least 3. We also introduce another axiom (b2(2)), which is meaningful only to 3-Steiner intervals and show that this axiom is equivalent to the monotone axiom.