Grötzsch graph

The Grötzsch graph is a triangle-free graph with 11 vertices that has chromatic number 4. It is named after German mathematician Herbert Grötzsch. The Grötzsch graph demonstrates that a triangle-free planar graph can require four colors to properly color its vertices, disproving a conjecture that all triangle-free planar graphs are 3-colorable. It serves as a counterexample in graph coloring theory. The graph is uniquely determined, meaning that there is only one graph with these properties (triangle-free, 11 vertices, chromatic number 4). Its discovery was significant in the development of graph coloring theory and played a role in the eventual proof of the Four Color Theorem.