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.
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 . The following table summarizes some properties of the Grötzsch graph.
property | value |
automorphism group order | 10 |
characteristic polynomial | |
chromatic number | 4 |
chromatic polynomial | |
claw-free | no |
clique number | 2 |
graph complement name | ? |
cospectral graph names | ? |
determined by spectrum | no |
diameter | 2 |
distance-regular graph | no |
dual graph name | 10-quartic graph 55 |
edge chromatic number | 5 |
edge connectivity | 3 |
edge count | 20 |
edge transitive | no |
Eulerian | no |
girth | 4 |
Hamiltonian | yes |
Hamiltonian cycle count | 20 |
Hamiltonian path count | 980 |
integral graph | no |
independence number | 5 |
line graph | no |
line graph name | ? |
perfect matching graph | no |
planar | no |
polyhedral graph | no |
polyhedron embedding names | ? |
radius | 2 |
regular | no |
square-free | no |
symmetric | no |
traceable | yes |
triangle-free | yes |
vertex connectivity | 3 |
vertex count | 11 |
vertex transitive | no |