A median graph is a connected simple graph in which every three vertices possess a
unique median. A graph vertex 
is a median of vertices 
, 
, and 
if it lies on a shortest path
for each of the pairs 
,
, and 
.
A connected graph 
is a median graph iff it is an induced subgraph of a hypercube
graph such that for any three vertices of 
their median in the hypercube
graph is also a graph vertex of 
(Mulder 1978, Munarini 2019).
The numbers of median graphs on 
, 2, ... vertices are 1,
1, 1, 3, 4, 11, 23, 69, 178, 567, ... (OEIS A292623),
the first few of which are illustrated above.
The graph Cartesian product of two median graphs is a median graph.
Trees are median graphs, so path and star graphs are as well.
Grid graphs (of all dimensions) are median graphs, so ladder graphs are as well.
Other classes of graphs that are median include book 
, Fibonacci
cube, gear (for 
), hypercube, and stacked book graphs.
