Граф Эрдёша — Диофанта
Граф Эрдёша — Диофанта — это множество точек на плоскости с целочисленными координатами, расстояния между которыми являются целыми числами, и которые нельзя расширить добавлением других точек. Эквивалентно это множество можно описать как полный граф с находящимися на целочисленной решётке вершинами, такой что попарные расстояния между вершинами являются целыми числами, в то время как все остальные точки решётки имеют нецелочисленное расстояние по меньшей мере до одной вершины.
Графы Эрдёша — Диофанта названы именами Пала Эрдёша и Диофанта Александрийского. Графы образуют подмножество множества диофантовых фигур, которые определяются как полные графы на диофантовой плоскости, в которых все рёбра имеют целочисленные длины. Тогда графы Эрдёша — Диофанта — это в точности диофантовы фигуры, которые нельзя расширить. Существование графов Эрдёша — Диофанта следует из теоремы Эрдёша — Эннинга, согласно которой бесконечные диофантовы фигуры должно быть коллинеарны на диофантовой плоскости. Следовательно, любой процесс расширения неколлинеарнной диофантовой фигуры путём добавления вершин должен достичь стадии, когда фигуру расширить нельзя.
Любое множество из нулевого числа точек или из одной точки можно тривиально расширить, а любое диофантово множество из двух точек можно расширить точками на той же прямой. Таким образом, все диофантовы множества с менее чем тремя точками могут быть расширены, а потому графы Эрдёша — Диофанта с менее чем тремя вершинами не существуют.
Путём числового поиска Конер и Курц[1] показали, что графы Эрдёша — Диофанта с тремя вершинами существуют. Наименьший треугольник Эрдёша — Диофанта имеет длины сторон 2066, 1803 и 505. Следующий по размеру треугольник Эрдёша — Диофанта имеет стороны 2549, 2307 и 1492. В обоих случаях сумма трёх сторон является чётным числом. Бранчева доказал, что это свойство имеет место для всех треугольников Эрдёша — Диофанта, полная длина любого замкнутого пути в графе Эрдёша — Диофанта всегда чётна.
Примером графа Эрдёша — Диофанта с четырьмя вершинами является полный граф, образованный вершинами прямоугольника со сторонами 4 и 3.