The Grabarchuk graph is the Euclidean distance graph obtained from the vertices of a 
grid graph when two vertices are considered
adjacent when the Euclidean distance between them is 3. Since 
has two representations as 3 squares:
 |  |  |
(1)
|
 |  |  |
(2)
|
edges correspond to points in the grid that are either distance 3 apart along a line parallel to a Cartesian axis, or else distances 1, 2, and 2 apart along the Cartesian axes.
Rather surprisingly, the resulting graph is sextic (Knuth 2025, p. 40).
The graph is named after Serhiy Grabarchuk, who communicated it to D. Knuth in 2018 (D. Knuth, pers. comm., Jul. 11, 2025).
The Grabarchuk graph will be implemented in a future version of the Wolfram Language as GraphData["GrabarchukGraph"].
D. Knuth (pers. comm., Jul. 11, 2025) posed the question if the Grabarchuk graph has a Hamilton decomposition. This was answered in the affirmative by E. Weisstein (Aug. 21, 2025; Knuth 2025, p. 71). The natural next question (whose answer is apparently not known) is if it (and other sextic graps having many Hamiltonian cycles) are perfectly Hamiltonian (D. Knuth, pers. comm., Jul. 22, 2025).
