Haugstrup (2026) constructed a 21217-vertex graph with the properties that it is 6-chromatic, tetrahedron-free, and can
be embedded as a unit-distance graph in three-dimensional Euclidean space. All previously
known 6-chromatic unit-distance graphs in 
contained contained unit-edge tetrahedra.
In the process of constructing this graph, Haugstrup used the Mycielskian graph 
, a unit-distance graph 
obtained from 
through the addition of a regular
decagon with radius 
(where 
is the golden ratio), a
graph 
that has a unit-distance embedding in 
, and the 47-vertex de
Grey-Haugstrup graph.
Haugstrup also constructed a 48-vertex 6-chromatic graph with graph dimension 3. Haugtrup's original faithful graph (i.e., all vertices separated by a unit distance are joined by an edge) had 152 edges, though 3 of these edges may be removed while still preserving chromatic number 6. Exact coordinates were found for the vertices by E. Weisstein (Jan. 6, 2026).
The Haugstrup graphs are implemented in the Wolfram Language as GraphData[
"Haugstrup", 31
] and GraphData[
"Haugstrup", 48
].
