Sitelet https://mathworld.wolfram.com/GroetzschGraph.html
TOPICS
Search

Grötzsch Graph


GrotztschGraph

The Grötzsch graph is the smallest triangle-free graph with chromatic number four. It is identical to the Mycielski graph with index four. It has 11 vertices, 20 edges, and graph crossing number 5. It is Hamiltonian, but nonplanar. It is illustrated above in a number of drawings.

GroetzschGraphMatrices

The plots above show the adjacency matrix, incidence matrix, and graph distance matrices for the Grötzsch graph.

The graph spectrum of the Grötzsch graph is (1/2(1-sqrt(41)))^1(1/2(-3-sqrt(5)))^2(1/2(-3+sqrt(5)))^21^5(1/2(1+sqrt(41)))^1.

GroetztschGraphUnitDistance3D

de Grey (2026) considered a unit-distance embedding of the Grötzsch graph in three dimensions in his construction of a triangle-free graph that is a unit-distance graph in R^3 with chromatic number 5, though ended up using a different graph on 31 vertices. The unit-distance embedding considered by de Grey, together with a similar one based on a pentagram instead of a pentagon, is illustrated above.

The Grötzsch graph is implemented in the Wolfram Language as GraphData["GroetzschGraph"].


See also

Mycielski Graph, Triangle-Free Graph

Explore with Wolfram|Alpha

References

Bondy, J. A. and Murty, U. S. R. Graph Theory. Berlin, Germany: Springer-Verlag, p. 366, 2008.Collins, K. and Tysdal, K. "Dependent Edges in Mycielski Graphs and 4-Colorings of 4-Skeletons." J. Graph Th. 46, 285-296, 2004.de Grey, A. D. N. J. "A 5-Chromatic, Triangle-Free Unit-Distance Graph in R^3 With 61 Vertices." Geombinatorics 35, 2026.House of Graphs. "Groetzsch Graph." https://houseofgraphs.org/graphs/1132.Soifer, A. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators. New York: Springer, pp. 85-86, 2008.Stahl, S. "Note on the nth Chromatic Numbers of the Grötzsch Graph." J. Graph Th. 21, 207-209, 1996.

Referenced on Wolfram|Alpha

Grötzsch Graph

Cite this as:

Weisstein, Eric W. "Grötzsch Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GroetzschGraph.html

Subject classifications