The Chen–Chvátal conjecture for metric spaces induced by distance-hereditary graphs

A classical theorem of Euclidean geometry asserts that any noncollinear set of nn points in the plane determines at least nn distinct lines. Chen and Chvátal conjectured a generalization of this result to arbitrary finite metric spaces, with a particular definition of lines in a metric space. We prove it for metric spaces induced by connected distance-hereditary graphs—a graph GG is called distance-hereditary if the distance between two vertices uu and vv in any connected induced subgraph HH of GG is equal to the distance between uu and vv in GG.