In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, the Grötzsch graph is a
triangle-free graph
In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with ...
with 11 vertices, 20 edges,
chromatic number
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
4, and
crossing number 5. It is named after German mathematician
Herbert Grötzsch
Camillo Herbert Grötzsch (21 May 1902 – 15 May 1993) was a German mathematician. He was born in Döbeln and died in Halle. Grötzsch worked in graph theory. He was the discoverer and eponym of the Grötzsch graph, a triangle-free graph that ...
, who used it as an example in connection with his 1959 theorem that planar triangle-free graphs are 3-colorable.
The Grötzsch graph is a member of an infinite sequence of triangle-free graphs, each the
Mycielskian
In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph is a larger graph formed from it by a construction of . The construction preserves the property of being triangle-free but increases the chroma ...
of the previous graph in the sequence, starting from the one-edge graph; this sequence of graphs was constructed by to show that there exist triangle-free graphs with arbitrarily large chromatic number. Therefore, the Grötzsch graph is sometimes also called the Mycielski graph or the Mycielski–Grötzsch graph. Unlike later graphs in this sequence, the Grötzsch graph is the smallest triangle-free graph with its chromatic number.
Properties
The full automorphism group of the Grötzsch graph is
isomorphic to the