Erdős-Diophantine graph
From Wikipedia, the free encyclopedia
In Diophantine geometry, an Erdős-Diophantine graph, named after Paul Erdős and Diophantus of Alexandria, is a complete graph with vertices located on the integer square grid 
such that all mutual distances between the vertices are integers, while all other grid points have a non-integer distance to at least one vertex.
Erdős-Diophantine graphs form a subset of the set of Diophantine figures. The latter are defined as complete graphs in the Diophantine plane for which the length of all edges are integers. So Erdős-Diophantine graphs can be defined as Diophantine figures that cannot be extended. The existence of Erdős-Diophantine graphs follows from the Erdős–Anning theorem, according to which infinite Diophantine figures must be collinear in the Diophantine plane. Hence, for any given non-collinear Diophantine figure there is a limit to how far it can be extended by adding vertices.
[edit] Examples
Graphs with fewer than three nodes are always collinear, so Erdős-Diophantine graphs with fewer than three nodes cannot exist. By numerical search, Kohnert and Kurz have shown that triangular Erdős-Diophantine graphs do exist. The smallest Erdős-Diophantine triangle is characterised by edge lengths 2066, 1803, and 505. The next larger Erdős-Diophantine triangle has edges 2549, 2307 and 1492. In both cases, the sum of the three edge-lengths is even. Brancheva has proven that this property holds for all Erdős-Diophantine triangles. More generally, the total length of any closed path in an Erdős-Diophantine graph is always even.
An example of a 4-node Erdős-Diophantine graph is provided by the complete graph formed by the four nodes located on the vertices of a rectangle with sides 4 and 3.
