The de Grey graphs are named graphs constructed by Aubrey de Grey in connection with the Hadwiger-Nelson problem. De Grey (2018)
found the first examples of unit-distance graphs
with chromatic number 5, thus demonstrating that
the solution to the Hadwiger-Nelson problem
(i.e., the chromatic number of the Euclidean
plane) is at least 5. While de Grey's original graph contained 
vertices, he was able to reduce this number (after a correction)
to the 1581-vertex graph illustrated above (de Grey 2018), referred to in this work
as the de Grey graph.
The de Grey graph is implemented in the Wolfram Language as GraphData["DeGreyGraph"].
A few days after the original preprint was published, Mixon (2018) constructed the 1585-vertex Mixon graph, the removal of 8 vertices from which led to the smaller 1577-vertex Mixon graph.
Smaller unit-distance graphs with chromatic number 5, here called the Heule graphs and Parts graphs, were computationally derived from the de Grey graph by Marijn Heule and Jaan Parts between 2018 and 2020. As of August 2026, the smallest of these remains the 509-vertex Parts graph (Parts 2020a, Haugland 2026).
The 2131-vertex Haugland graph instead satisfies the additional restriction that it contain no Moser spindle.
Additional graphs due to de Grey include 59- and 60-vertex unit-distance graphs in three-dimensional Euclidean space (but not in the Euclidean plane) with chromatic number 6, and a 126-vertex graph discussed by Parts (2020b).
de Grey (2026) also constructed a 61-vertex, 5-chromatic, triangle-free unit-distance graph in three-dimensional Euclidean space by spindling a 31-vertex graph. Both graphs are illustrated above. The 61-vertex graph is much smaller than the Voronov-Neopryatnaya-Dergachev graphs, two tetrahedron-free graphs on 372 and 972 vertices with chromatic number 5 and unit-distance embeddings whose vertices all lie on a sphere. Exact coordinates for the 61-vertex graph were found by E. Weisstein (Dec. 19, 2025).
The de Grey graphs on 31, 60, 61, and 126 vertices are implemented in the Wolfram Language as GraphData["DeGreyGraph31"], GraphData["DeGreyGraph60"], GraphData["DeGreyGraph61"], and GraphData["DeGreyGraph126"], respectively. The 59-vertex de Grey graph will be implemented in a future version of the Wolfram Language as GraphData["DeGreyGraph59"].
With 61 Vertices." Geombinatorics 35,
2026.Haugland, J. K. "A Moser-Spindle-Free 5-Chromatic Unit
Distance Graph on 2131 Vertices in the Plane." 5 Aug 2026.