The term "Haugstrup graphs" is used in this work for three auxiliary graphs used by Haugstrup (2026) to construct a 21217-vertex
6-chromatic graph that is 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 edge lengths 
, where 
is the golden ratio.
The graph 
, also known as the decagon
Mycielskian graph, has graph
crossing number 10.
The Haugstrup graphs are implemented in the Wolfram Language as GraphData[{"Haugstrup", 21}] etc.
