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.
