Define
 |  |  |
(1)
|
 |  |  |
(2)
|
 |  |  |
(3)
|
where 
,
, 
, and 
are vertices of a graph and 
is the graph distance between vertices 
and 
. Then a connected Ptolemaic graph is a graph 
such that a weak form of the triangle
inequality
 |  |  |
(4)
|
 |  |  |
(5)
|
 |  |  |
(6)
|
holds for any four vertices 
(Kay and Chartrand 1965, Howorka 1981).
The numbers of connected Ptolemaic graphs on 
, 2, ... vertices are 1, 1, 2, 5, 14, 47, 170, 676, 2834,
12471, 56675, 264906, ... (OEIS A287888).
The definition can be extended to disconnected graphs by allowing 4-tuples of points in each connected component to satisfy these conditions separately (Bahrani and Lumbroso 2016).
A connected graph is Ptolemaic iff is it distance-heritary and chordal (Howorka 1981, Bahrani and Lumbroso 2016). Ptolemaic graphs are perfect.
Classes of graphs that are Ptolemaic include block graphs.
