TOPICS
Search

Grötzsch Graph


GrotztschGraph

The Grötzsch graph is smallest triangle-free graph with chromatic number four. It is identical to the Mycielski graph of order four, and is implemented as GraphData["GrotztschGraph"]. It has 11 vertices and 20 edges. It is Hamiltonian, but nonplanar. It is illustrated above in a number of embeddings.

GroetzschGraphMatrices

The plots above show the adjacency, incidence, 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 5-chromatic, triangle-free, unit-distance graph in R^3, though ended up using a different graph on 31 vertices. The embedding considered by de Grey, together with a similar one based on a pentagram instead of a pentagon, is illustrated above.


See also

Mycielski Graph, Triangle-Free Graph

Explore with Wolfram|Alpha

References

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.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