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.

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. The following table summarizes some properties of the Grötzsch graph.

propertyvalue
automorphism group order10
characteristic polynomial(x-1)^5(x^2-x-10)(x^2+3x+1)^2
chromatic number4
chromatic polynomial(x-3)(x-2)(x-1)x(x^7-14x^6+95x^5-400x^4+1115x^3-2033x^2+2217x-1100)
claw-freeno
clique number2
graph complement name?
cospectral graph names?
determined by spectrumno
diameter2
distance-regular graphno
dual graph name10-quartic graph 55
edge chromatic number5
edge connectivity3
edge count20
edge transitiveno
Eulerianno
girth4
Hamiltonianyes
Hamiltonian cycle count20
Hamiltonian path count980
integral graphno
independence number5
line graphno
line graph name?
perfect matching graphno
planarno
polyhedral graphno
polyhedron embedding names?
radius2
regularno
square-freeno
symmetricno
traceableyes
triangle-freeyes
vertex connectivity3
vertex count11
vertex transitiveno

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

Cite this as:

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

Subject classifications