Grötzsch's theorem

Every planar graph with no cycles of length three can be properly colored with at most three colors. The bound is sharp: some triangle-free planar graphs require three colors.

Connect

Graph coloring: An assignment of labels to graph vertices in which adjacent vertices receive different labels. The theorem guarantees a three-coloring for a restricted class of graphs.
Martin Grötzsch: German mathematician known for proving that every triangle-free planar graph is three-colorable. His 1959 proof established the theorem bearing his name.
Grötzsch graph: The smallest triangle-free planar graph with chromatic number four. It demonstrates why planarity cannot be dropped from the theorem's conditions.
Chromatic number: The minimum number of colors needed to color a graph's vertices so adjacent vertices differ. The theorem bounds this invariant by three for its specified graphs.
Planar graph: A graph that can be drawn in the plane without edges crossing except at shared endpoints. Planarity is the structural condition that makes the three-color bound possible.
Four color theorem: The theorem that every planar graph admits a proper coloring with at most four colors. Grötzsch's result strengthens this bound when triangles are forbidden.
Dodecahedral graph: The graph of the vertices and edges of a regular dodecahedron. It is triangle-free and planar, and requires all three colors.
List coloring: A graph coloring problem in which each vertex has an individual list of allowed colors. The list-coloring analogue asks whether the same three-color guarantee survives restricted color choices.
Triangle-free graph: A graph containing no cycle of length three. This is the theorem's second defining condition, alongside planarity.
Wagner's conjecture: A conjecture that every planar graph without triangles can be colored with three colors. Grötzsch proved the conjecture that motivated his theorem.