Maximally Dense Unit-Distance Graph

A maximally dense unit-distance graph is a unit-distance graph having the maximum possible number of edges (i.e., maximum graph density) for a given number of vertices. Finding a maximally dense unit-distance graph is equivalent to solving the Erdős unit distance problem. This maximum edge count, equivalently the maximum number of unit-distance pairs among planar points, is denoted .

Alon et al. (2026) and OpenAI (2026) disproved the conjectural asymptotic bound , where denotes a quantity tending to 0 in little-O notation, showing that square grid-type constructions are not asymptotically optimal. Sawin (2026) subsequently gave the explicit lower bound for arbitrarily large . This does not determine the true order of , and the exact maximally dense unit-distance graphs presently known for small do not settle the asymptotic structure. The construction gives an infinite-family lower bound, but not a matching upper bound or a classification of extremal unit-distance graphs.

Special cases are summarized in the following table, where is the vertex count.

	maximally dense unit-distance graphs
1	singleton graph
2	path graph
3	triangle graph
4	diamond graph
5	gem graph
6	prism graph , fan graph , 8-Beineke graph, 2-triangular graph
7	wheel graph
8	(8,10)-self-complementary graph, Johnson skeleton graph , (unnamed)
9	generalized quadrangle

Alexeev et al. (2025) determined all nonisomorphic maximally dense unit-distance graphs up to 21 vertices. Their counts for , 2, ... are 1, 1, 1, 1, 1, 4, 1, 3, 1, 1, 2, 1, 1, 2, 1, 1, 7, 16, 3, 1, 5, ... (OEIS A385657). All but one of these graphs were previously discovered by Engel et al. (2025), with the exception being a graph on 17 vertices whose unit-distance embedding does not reside within the Moser ring they searched (Alexeev et al. 2025). The maximally dense unit-distance graphs for to 15 are illustrated above.

The th maximally dense unit-distance graph on vertices is implemented in the Wolfram Language as GraphData["MaximallyDenseUnitDistance", n, k].