The term "Haugstrup graphs" is used in this work for three auxiliary graphs used by Haugstrup (2026) to construct a 21217-vertex graph that is 6-chromatic, tetrahedron-free, and embeddable as a unit-distance
graph in three-dimensional Euclidean space.
All previously known 6-chromatic unit-distance
graphs in 
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 
. The vertices of 
are constructed from a unit-edge regular
icosahedron together with those of a regular
dodecahedron in dual position with edges lengths 
, where 
is the golden ratio.
The Haugstrup graphs are implemented in the Wolfram Language as GraphData[
"Haugstrup", 21
] etc.
