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 graph 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 will be implemented in a future version of
the Wolfram Language as GraphData[
"MaximallyDenseUnitDistance",
n,
k
].
Points." Amer. Math. Monthly 53, 248-250,
1946.OpenAI. "Planar Point Sets with Many Unit Distances."
20 May 2026.