de Grey-Haugstrup Graphs

The de Grey-Haugstrup graphs are unit-distance graphs in three-dimensional Euclidean space with chromatic number 6. The construction described by de Grey and Haugstrup (2020) gives graphs on 47 and 48 vertices.

The 47-vertex construction consists of a common 11-vertex scaffold with four copies of the Nechushtan graph attached. Each copy has three distinct attachment roles, which can be permuted independently. The resulting labeled choices comprise 108 classes under graph isomorphism, each containing 12 labeled choices. Each class represents a unit-distance graph with 47 vertices and 146 edges. One member has the exact coordinates given by Haugstrup (2022). It is implemented in the Wolfram Language as GraphData["DeGreyHaugstrupGraph47"] and was used by Haugstrup (2026) in the construction of the 21217-vertex Haugstrup graph.

The 48-vertex graph has chromatic number 6 and graph dimension 3. It is a faithful graph (i.e., all vertices separated by a unit distance are joined by an graph edge) with 152 edges. As it turns out, 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 de Grey-Haugstrup graph on 48 vertices is implemented in the Wolfram Language as GraphData["DeGreyHaugstrupGraph48"].