Erdős–Diophantine graph

An Erdős–Diophantine graph is an object in the mathematical subject of Diophantine equations consisting of a set of integer points at integer distances in the plane that cannot be extended by any additional points. Equivalently, in geometric graph theory, it can be described as a complete graph with vertices located on the integer square grid ${\displaystyle \mathbb {Z} ^{2}}$ 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 are named after Paul Erdős and Diophantus of Alexandria. They form a subset of the set of Diophantine figures, which are defined as complete graphs in the Diophantine plane for which the length of all edges are integers (unit distance graphs). Thus, Erdős–Diophantine graphs are exactly the 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, any process of extending a non-collinear Diophantine figure by adding vertices must eventually reach a figure that can no longer be extended.

Any set of zero or one point can be trivially extended, and any Diophantine set of two points can be extended by more points on the same line. Therefore, all Diophantine sets with fewer than three nodes can be extended, so Erdős–Diophantine graphs on fewer than three nodes cannot exist.

By numerical search, Kohnert & Kurz (2007) have shown that three-node 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.

• Kohnert, Axel; Kurz, Sascha (2007), "A note on Erdős-Diophantine graphs and Diophantine carpets", Mathematica Balkanica, New Series, 21 (1–2): 1–5, arXiv:math/0511705, MR 2350714
• Dimiev, Stancho; Markov, Krassimir (2002), "Gauss integers and Diophantine figures", Mathematics and Mathematical Education, 31: 88–95, arXiv:math/0203061, Bibcode:2002math......3061D