TOPICS
Search

Grabarchuk Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The Grabarchuk graph is the Euclidean distance graph obtained from the vertices of a 4×4×4 grid graph when two vertices are considered adjacent when the Euclidean distance between them is 3. Since 3^2=9 has two representations as 3 squares:

9=0^2+0^2+3^2
(1)
=1^2+2^2+2^2,
(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.

GrabarchukGraph

Rather surprisingly, the resulting graph is sextic (Knuth 2025, p. 40). It is illustrated above in an order-4 LCF notation due to E. Pegg, Jr. (pers. comm., Apr. 8, 2026).

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 whether the Grabarchuk graph has a Hamilton decomposition. This was answered in the affirmative by E. Weisstein (Aug. 21, 2025; Knuth 2025, p. 71).

See also

Euclidean Distance Graph, Grid Graph, Hamilton Decomposition, Perfectly Hamiltonian Graph, Sextic Graph

Explore with Wolfram|Alpha

References

Grabarchuk, S. "Sticky Chain Puzzle. Age of Puzzles: Puzzle Galleries. San Diego, CA: Puzzlium, Inc., p. 170, 2019.Knuth, D. E. Problem and Solution 370 in "Hamiltonian Paths and Cycles." Volume 4, Pre-Fascicle 8A in The Art of Computer Programming. Draft, pp. 40 and 71, Aug. 19, 2025. https://www-cs-faculty.stanford.edu/~knuth/fasc8a.pdf.Pegg, E. Jr. Mathematical Games. Episode 32: "Unit Distance Graphs." Aug. 21, 2025. https://www.youtube.com/watch?v=xuHr8acIkYs.

Cite this as:

Weisstein, Eric W. "Grabarchuk Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GrabarchukGraph.html

Subject classifications