Erdős-Diophantine graph

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 $scriptstylemathbb\{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 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, any process of extending a non-collinear Diophantine figure by adding vertices must eventually reach a figure that can no longer be extended.

Examples

Graphs with fewer than three nodes are always collinear, so Erdős-Diophantine graphs with fewer than three nodes cannot exist (due to the non-integer distance condition for the remaining grid).

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.

References

* [http://arxiv.org/abs/math/0511705v1 Axel Kohnert and Sascha Kurz, "A note on Erdős-Diophantine graphs and Diophantine carpets]
* [http://arxiv.org/abs/math/0203061v1 Stancho Dimiev and Krassimir Markov, "Gauss integers and Diophantine figures"]
* [http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1148507742;start= Derivation of a 4-node Erdős-Diophantine graph]