Erdős–Diophantine graph

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

An Erdős–Diophantine graph is a finite, complete set of lattice points (points with integer coordinates) in the plane such that every pair of points is at an integer distance from each other, and no other lattice point can be added without breaking this “all distances are integers” property. In other words, it’s a complete graph on points from Z^2 where all edge lengths are integers, and the graph is maximal in this sense.

How it fits with other ideas:
- These graphs are a special kind of Diophantine figure, which are complete graphs in the Diophantine plane with all edge lengths integers.
- Erdős–Diophantine graphs are exactly the Diophantine figures that cannot be extended by adding more lattice points while keeping all edge lengths integers.

Key background:
- The Erdős–Anning theorem says that an infinite Diophantine figure must lie on a straight line. This means that if you start with a non-collinear figure and try to add more lattice points, you can’t keep all distances integral forever; eventually you reach a maximal figure, an Erdős–Diophantine graph.

What’s easy to know and what isn’t:
- Any set with 0 or 1 point can always be extended (you can add more points while keeping distances integral).
- Any Diophantine set of two points can be extended along a line.
- Therefore, Erdős–Diophantine graphs do not exist with fewer than three nodes.

Examples and what they tell us:
- Three points exist: the smallest Erdős–Diophantine triangle has edge lengths 2066, 1803, and 505. A second known triangle has edges 2549, 2307, and 1492. In both cases, the sum of the three edge lengths is even.
- It’s known (and proven) that this even-perimeter property holds for all Erdős–Diophantine triangles.
- A four-point example exists: a complete graph on the four corners of a 4 by 3 rectangle. The distances between adjacent corners are 3 or 4, and the diagonals are 5, all integers.

What this means in short:
- Erdős–Diophantine graphs are maximal, non-extendable sets of lattice points with all mutual distances integers.
- They demonstrate how a non-collinear Diophantine figure cannot be grown indefinitely while preserving the integer-distance condition.
- They connect to broader ideas about Diophantine figures and the geometry of the integer lattice.

Notable references:
- Kohnert, Axel; Kurz, Sascha (2007). A note on Erdős–Diophantine graphs and Diophantine carpets. Mathematica Balkanica.
- Dimiev, Stancho; Markov, Krassimir (2002). Gauss integers and Diophantine figures. Mathematics and Mathematical Education.

Visuals and further examples:
- There are illustrations of a 5-node Erdős–Diophantine graph and a 6-node Erdős–Diophantine graph described in the literature.