Grötzsch graph
Triangle-free graph requiring four colors / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Grötzsch graph?
Summarize this article for a 10 year old
In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch, who used it as an example in connection with his 1959 theorem that planar triangle-free graphs are 3-colorable.[1]
Grötzsch graph | |
---|---|
Named after | Herbert Grötzsch |
Vertices | 11 |
Edges | 20 |
Radius | 2 |
Diameter | 2 |
Girth | 4 |
Automorphisms | 10 (D5) |
Chromatic number | 4 |
Chromatic index | 5 |
Book thickness | 3 |
Queue number | 2 |
Properties | |
Table of graphs and parameters |
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 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.[2]