 Grötzsch graph

The Grötzsch graph is the Mycielskian of the five-vertex cycle graph. Take original edges $v_i{v}_{i+1}$, with indices interpreted modulo five; add $u_i{v}_{i-1},u_i{v}_{i+1}$ and $w{u}_i$ for every $i$. There are eleven vertices and twenty edges: five original, ten between originals and Mycielski shadow vertices, and five from the Mycielski apex.

Give $v_1,\dots ,v_5$ colours $(1,2,1,2,3)$, give each $u_i$ the colour of $v_i$, and give $w$ colour 4. This is a proper vertex colouring. The Mycielskian chromatic increase proves that three colours are impossible, so the chromatic number is exactly four. The Mycielskian triangle preservation proves that this is a triangle-free graph. In particular its clique number is only two, even though its chromatic number is four.

The Mycielski apex has an independent set as its graph neighbourhood, yet all three old colours are needed there in any three-colour proper vertex colouring of the subgraph obtained by deleting it. Thus a locally easy group of mutually nonadjacent neighbours can carry globally incompatible colour requirements. Absence of triangles in a graph alone cannot bound the chromatic number.

The Grötzsch graph is an important example in graph theory, particularly known for being a minimal example of a triangle-free graph that does not have a 3-coloring. The graph was named after the German mathematician Kurt Grötzsch, who constructed it in 1959. Here are some key characteristics of the Grötzsch graph: 1. **Vertices and Edges**: The Grötzsch graph consists of 11 vertices and 20 edges.