View source for Grötzsch graph

{{Short description|Triangle-free graph requiring four colors}}
{{infobox graph
 | name = Grötzsch graph
 | image = [[Image:Groetzsch-graph.svg|180px]]
 | namesake = [[Biography:Herbert Grötzsch|Herbert Grötzsch]]
 | vertices = 11
 | edges = 20
 | diameter = 2
 | radius = 2
 | girth = 4
 | chromatic_number = 4
 | chromatic_index = 5
 | crossing_number = 5
 | automorphisms = 10 ([[Dihedral group|D]]<sub>5</sub>)
 | properties = {{plainlist|1=
*Hamiltonian
*[[Projective plane|Projective planar]]
*[[Triangle-free graph|Triangle-free]]
}}
|queue number=2|book thickness=3}}
In the [[Mathematics|mathematical]] field of [[Graph theory|graph theory]], the '''Grötzsch graph''' is a [[Triangle-free graph|triangle-free graph]] with 11 vertices, 20 edges, [[Chromatic number|chromatic number]] 4, and [[Crossing number (graph theory)|crossing number]] 5. It is named after German mathematician [[Biography:Herbert Grötzsch|Herbert Grötzsch]], who used it as an example in connection with his 1959 theorem that planar triangle-free graphs are 3-colorable.{{sfnp|Grötzsch|1959}}

The Grötzsch graph is a member of an infinite sequence of triangle-free graphs, each the [[Mycielskian]] of the previous graph in the sequence, starting from the one-edge graph; this sequence of graphs was constructed by {{harvtxt|Mycielski|1955}} 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.{{sfnp|Chvátal|1974}}

==Properties==
The full automorphism group of the Grötzsch graph is [[Group isomorphism|isomorphic]] to the [[Dihedral group|dihedral group]] D<sub>5</sub> of order 10, the group of symmetries of a regular pentagon, including both rotations and reflections.{{sfnp|Joyner|Melles|2017}} These symmetries have three orbits of vertices: the degree-5 vertex (by itself), its five neighbors, and its five non-neighbors. Similarly, there are three orbits of edges, distinguished by their distance from the degree-5 vertex.

The [[Characteristic polynomial|characteristic polynomial]] of the Grötzsch graph is{{sfnp|Joyner|Melles|2017}}
<math display=block>(x-1)^5 (x^2-x-10) (x^2+3 x+1)^2.</math>

Although it is not a [[Planar graph|planar graph]], it can be embedded in the [[Projective plane|projective plane]] without crossings. This embedding has ten faces, all of which are quadrilaterals.{{sfnp|Youngs|1996}}

==Applications==
The existence of the Grötzsch graph demonstrates that the assumption of planarity is necessary in [[Grötzsch's theorem]] that every triangle-free [[Planar graph|planar graph]] is 3-colorable.{{sfnp|Grötzsch|1959}} It has odd girth five but girth four, and does not have any [[Graph homomorphism|graph homomorphism]] to a graph whose girth is five or more, so it forms an example that distinguishes odd girth from the maximum girth that can be obtained from a homomorphism.{{sfnp|Galluccio|Goddyn|Hell|2001}}

{{harvtxt|Häggkvist|1981}} used a modified version of the Grötzsch graph to disprove a conjecture of {{harvs|txt|first1=Paul|last1=Erdős|first2=Miklos|last2=Simonovits|year=1973}} on the chromatic number of triangle-free graphs with high degree. Häggkvist's modification consists of replacing each of the five degree-four vertices of the Grötzsch graph by a set of three vertices, replacing each of the five degree-three vertices of the Grötzsch graph by a set of two vertices, and replacing the remaining degree-five vertex of the Grötzsch graph by a set of four vertices. Two vertices in this expanded graph are connected by an edge if they correspond to vertices connected by an edge in the Grötzsch graph. The result of Häggkvist's construction is a 10-[[Regular graph|regular]] triangle-free graph with 29 vertices and chromatic number 4, disproving the conjecture that there is no 4-chromatic triangle-free <math>n</math>-vertex graph in which each vertex has more than <math>n/3</math> neighbours.{{sfnp|Häggkvist|1981}} Every such graph contains the Grötzsch graph as an [[Induced subgraph|induced subgraph]].{{sfnp|Brandt|1999}}

==Related graphs==
The Grötzsch graph shares several properties with the [[Clebsch graph]], a [[Distance-transitive graph|distance-transitive graph]] with 16 vertices and 40 edges: both the Grötzsch graph and the Clebsch graph are triangle-free and four-chromatic, and neither of them has any six-vertex [[Induced path|induced path]]s. These properties are close to being enough to characterize these graphs: the Grötzsch graph is an [[Induced subgraph|induced subgraph]] of the Clebsch graph, and every triangle-free four-chromatic <math>P_6</math>-free graph is likewise an induced subgraph of the Clebsch graph that in turn contains the Grötzsch graph as an induced subgraph.{{sfnp|Randerath|Schiermeyer|Tewes|2002}} The [[Chvátal graph]] is another small triangle-free 4-chromatic graph. However, unlike the Grötzsch graph and the Clebsch graph, the Chvátal graph has a six-vertex induced path.

==Notes==
{{reflist}}

==References==
*{{citation
 | last = Brandt | first = Stephan
 | doi = 10.1017/S0963548399003831
 | issue = 3
 | journal = Combinatorics, Probability and Computing
 | mr = 1702550
 | pages = 237–245
 | title = On the structure of dense triangle-free graphs
 | volume = 8
 | year = 1999| s2cid = 120967754
 }}
*{{citation
 | last = Chvátal | first = Vašek
 | contribution = The minimality of the Mycielski graph
 | title = Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973)
 | date = 1974
 | pages = 243–246
 | publisher = Lecture Notes in Mathematics, Vol. 406, Springer-Verlag
 | location = Berlin
 | mr = 0360330}}
*{{citation
 | title = On a valence problem in extremal graph theory
 | journal = Discrete Mathematics
 | volume = 5
 | year = 1973
 | pages = 323–334
 | mr = 0342429
 | doi = 10.1016/0012-365X(73)90126-X | doi-access = free
 | issue = 4}}
*{{citation
 | last1 = Galluccio | first1 = Anna
 | last2 = Goddyn | first2 = Luis A.
 | last3 = Hell | first3 = Pavol
 | doi = 10.1006/jctb.2000.2009
 | issue = 1
 | journal = Journal of Combinatorial Theory
 | mr = 1855793
 | pages = 1–14
 | series = Series B
 | title = High-girth graphs avoiding a minor are nearly bipartite
 | volume = 83
 | year = 2001| doi-access = free
 }}
*{{citation
 | title = Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel
 | journal = Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe
 | volume = 8
 | year = 1959
 | pages = 109–120
 | mr = 0116320}}
*{{citation
 | last = Häggkvist | first = R.
 | chapter = Odd cycles of specified length in nonbipartite graphs
 | title = Graph Theory (Cambridge, 1981)
 | date = 1981
 | pages = 89–99
 | mr = 0671908}}
*{{citation
 | last1 = Joyner | first1 = W. David
 | last2 = Melles | first2 = Caroline Grant
 | contribution = 5.12 Grötzsch graph
 | doi = 10.1007/978-3-319-68383-6
 | isbn = 978-3-319-68381-2
 | mr = 3753658
 | pages = 229–231
 | publisher = Birkhäuser/Springer, Cham
 | series = Applied and Numerical Harmonic Analysis
 | title = Adventures in Graph Theory
 | year = 2017}}
*{{citation
 | last = Mycielski | first = Jan
 | title = Sur le coloriage des graphs
 | journal = Colloq. Math.
 | volume = 3
 | year = 1955
 | issue = 2
 | pages = 161–162
 | mr = 0069494
 | doi=10.4064/cm-3-2-161-162 | doi-access = free}}
*{{citation
 | last1 = Randerath | first1 = Bert
 | last2 = Schiermeyer | first2 = Ingo
 | last3 = Tewes | first3 = Meike
 | doi = 10.1016/S0012-365X(01)00335-1 | doi-access = free
 | issue = 1–3
 | journal = Discrete Mathematics
 | mr = 1904597
 | pages = 137–153
 | title = Three-colourability and forbidden subgraphs. II. Polynomial algorithms
 | volume = 251
 | year = 2002}}
*{{citation
 | last = Youngs | first = D. A.
 | doi = 10.1002/(SICI)1097-0118(199602)21:2<219::AID-JGT12>3.0.CO;2-E
 | issue = 2
 | journal = Journal of Graph Theory
 | mr = 1368748
 | pages = 219–227
 | title = 4-chromatic projective graphs
 | volume = 21
 | year = 1996}}

== External links ==
*{{mathworld | title = Grötzsch Graph | urlname = GroetzschGraph | mode=cs2}}

{{DEFAULTSORT:Grotzsch graph}}

[[Category:Individual graphs]]

{{Sourceattribution|Grötzsch graph}}