Grötzsch's theorem

In the mathematical field of graph theory, Grötzsch's theorem is the statement that every triangle-free planar graph can be colored with only three colors. According to the four-color theorem, every graph that can be drawn in the plane without edge crossings can have its vertices colored using at most four different colors, so that the two endpoints of every edge have different colors, but according to Grötzsch's theorem only three colors are needed for planar graphs that do not contain three mutually adjacent vertices. The theorem is named after German mathematician Herbert Grötzsch, who published its proof in 1959. Grötzsch's original proof was complex. attempted to simplify it but his proof was erroneous. In 2003, Carsten Thomassen derived an alternative proof from another related theorem: every planar graph with girth at least five is 3-list-colorable. However, Grötzsch's theorem itself does not extend from coloring to list coloring: there exist triangle-free planar graphs that are not 3-list-colorable. In 2012, Nabiha Asghar gave a new and much simpler proof of the theorem that is inspired by Thomassen's work. In 1989, Richard Steinberg and Dan Younger gave the first correct proof, in English, of the dual version of this theorem. A slightly more general result is true: if a planar graph has at most three triangles then it is 3-colorable. However, the planar complete graph K4, and infinitely many other planar graphs containing K4, contain four triangles and are not 3-colorable. In 2009, Dvořák, Kráľ, and Thomas announced a proof of another generalization, conjectured in 1969 by L. Havel: there exists a constant d such that, if a planar graph has no two triangles within distance d of each other, then it can be colored with three colors. This work formed part of the basis for Dvořák's 2015 European Prize in Combinatorics. The theorem cannot be generalized to all nonplanar triangle-free graphs: not every nonplanar triangle-free graph is 3-colorable.