Median graph

In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest paths between each pair of a, b, and c.

The concept of median graphs has long been studied, for instance by Birkhoff & Kiss (1947) or (more explicitly) by Avann (1961), but the first paper to call them "median graphs" appears to be Nebeský (1971). As Chung, Graham, and Saks write, "median graphs arise naturally in the study of ordered sets and discrete distributive lattices, and have an extensive literature". In phylogenetics, the Buneman graph representing all maximum parsimony evolutionary trees is a median graph. Median graphs also arise in social choice theory: if a set of alternatives has the structure of a median graph, it is possible to derive in an unambiguous way a majority preference among them.

Additional surveys of median graphs are given by Klavžar & Mulder (1999), Bandelt & Chepoi (2008), and Knuth (2008).

Every tree is a median graph. To see this, observe that in a tree, the union of the three shortest paths between pairs of the three vertices a, b, and c is either itself a path, or a subtree formed by three paths meeting at a single central node with degree three. If the union of the three paths is itself a path, the median m(a,b,c) is equal to one of a, b, or c, whichever of these three vertices is between the other two in the path. If the subtree formed by the union of the three paths is not a path, the median of the three vertices is the central degree-three node of the subtree.

...
Wikipedia