From the Five-Cycle to the Grötzsch Graph
The Grötzsch graph is a useful example of a graph whose chromatic number is larger than its clique number: it has no triangles, yet it needs four colors. Its structure comes from applying the Mycielski construction to the five-cycle. We will name every vertex and edge so that both its coloring and its triangle-free property can be checked directly.
Start with the cycle \(C_5\), whose vertices are \(v_1,\ldots,v_5\), with indices understood cyclically. Thus \(v_0=v_5\) and \(v_6=v_1\). The Mycielski construction adds a shadow \(u_i\) for each \(v_i\). The shadow \(u_i\) is adjacent to the two cycle-neighbors of \(v_i\), namely \(v_{i-1}\) and \(v_{i+1}\). It also adds a new vertex \(w\), adjacent to every shadow. There are no other edges.
A proper coloring assigns colors to vertices so that the endpoints of every edge receive different colors. The chromatic number \(\chi(G)\) is the least number of colors in a proper coloring. A triangle is a cycle of length three. The central facts to establish are that this particular graph has eleven vertices, contains no triangle, and has chromatic number four.
Counting the Vertices and Edges
The construction keeps the five original vertices, adds five shadows, and then adds the single vertex \(w\). The three groups are disjoint, so their sizes add. For the edges, there are five cycle edges, two edges from each of the five shadows to the original cycle, and five edges incident with \(w\). These are disjoint groups of edges, so this count does not count any edge twice.
Worked Example: Counting the Grötzsch Graph
Use the explicitly defined simple graph \(G=(V,E)\) with \(V=\{v_1,v_2,v_3,v_4,v_5,u_1,u_2,u_3,u_4,u_5,w\}\) and \(E=\{v_1v_2,v_2v_3,v_3v_4,v_4v_5,v_5v_1,u_1v_2,u_1v_5,u_2v_1,u_2v_3,u_3v_2,u_3v_4,u_4v_3,u_4v_5,u_5v_4,u_5v_1,wu_1,wu_2,wu_3,wu_4,wu_5\}\).
The vertex count is \(5+5+1=11\). For the edge count, the original cycle contributes \(5\) edges. The shadows contribute \(2+2+2+2+2=10\) edges to the cycle, and \(w\) contributes \(5\) edges to the shadows. Therefore \(|E|=5+10+5=20\).
Check the edge count independently by degrees. Each original vertex \(v_i\) has two neighbors on the cycle and is adjacent to the two shadows belonging to its cycle-neighbors, so its degree is \(4\). Each \(u_i\) has two original neighbors and the neighbor \(w\), so its degree is \(3\). The degree of \(w\) is \(5\). The degree sum is \(5\cdot4+5\cdot3+5=20+15+5=40\). By the handshake lemma, the number of edges is half the degree sum, \(40/2=20\), agreeing with the direct count.
Why the Graph Has No Triangle
Proof. Consider a triangle, if one exists. If it contains \(w\), its other two vertices must be shadows, since \(w\) is adjacent only to shadows. But no two shadows are adjacent, so such a triangle cannot exist. Now consider a triangle that does not contain \(w\). The shadows have no edges between them, so the triangle contains at most one shadow. If it contains no shadow, it would have to be a triangle within the original cycle \(C_5\), which has only the five listed consecutive edges and no three pairwise adjacent vertices. If it contains exactly one shadow \(u_i\), the other two vertices must be its neighbors \(v_{i-1}\) and \(v_{i+1}\). Those two vertices are not adjacent: in the five-cycle they are separated by \(v_i\), and the edge list contains no edge between them. In every case a triangle is impossible. Thus \(G\) is triangle-free. \(\square\)
Worked Example: Checking the Triangle Cases
For this check, the graph is \(G=(V,E)\), where \(V=\{v_1,v_2,v_3,v_4,v_5,u_1,u_2,u_3,u_4,u_5,w\}\) and \(E=\{v_1v_2,v_2v_3,v_3v_4,v_4v_5,v_5v_1,u_1v_2,u_1v_5,u_2v_1,u_2v_3,u_3v_2,u_3v_4,u_4v_3,u_4v_5,u_5v_4,u_5v_1,wu_1,wu_2,wu_3,wu_4,wu_5\}\).
For example, \(u_3\) has exactly the two original neighbors \(v_2\) and \(v_4\), and \(v_2v_4\notin E\). So \(u_3\) cannot be part of a triangle with two original vertices. The same check for all five shadows gives the pairs \((v_5,v_2)\), \((v_1,v_3)\), \((v_2,v_4)\), \((v_3,v_5)\), and \((v_4,v_1)\); none is an edge of the five-cycle. A triangle through \(w\) would require an edge between two shadows, but the edge list has none. The original cycle itself has no triangle. These checks cover every possible type of triangle.
Check: the argument excludes triangles by the type of vertices they would have to contain, rather than by inspecting only a few selected triples. In particular, checking only the original \(C_5\) would not be enough: triangles involving shadows or \(w\) must also be ruled out.
A Four-Coloring
To show that \(\chi(G)\leq 4\), it is enough to give a proper coloring with four colors. The table below records a coloring. The original cycle uses three colors; the shadows use these same three colors; and the extra vertex \(w\) receives a fourth color.
Worked Example: Coloring the Grötzsch Graph with Four Colors
Take \(G=(V,E)\) with \(V=\{v_1,v_2,v_3,v_4,v_5,u_1,u_2,u_3,u_4,u_5,w\}\) and \(E=\{v_1v_2,v_2v_3,v_3v_4,v_4v_5,v_5v_1,u_1v_2,u_1v_5,u_2v_1,u_2v_3,u_3v_2,u_3v_4,u_4v_3,u_4v_5,u_5v_4,u_5v_1,wu_1,wu_2,wu_3,wu_4,wu_5\}\). Assign colors as follows.
| Vertices | Color |
|---|---|
| \(v_1,v_3,u_1,u_3\) | 1 |
| \(v_2,v_4,u_2,u_4\) | 2 |
| \(v_5,u_5\) | 3 |
| \(w\) | 4 |
Check the five cycle edges in order: \(v_1v_2\) has colors \(1,2\); \(v_2v_3\) has \(2,1\); \(v_3v_4\) has \(1,2\); \(v_4v_5\) has \(2,3\); and \(v_5v_1\) has \(3,1\). Each pair differs.
Now check the shadow-to-cycle edges. The neighbors of \(u_1\) are \(v_2,v_5\), colored \(2,3\), while \(u_1\) has color \(1\). The neighbors of \(u_2\) are \(v_1,v_3\), both colored \(1\), while \(u_2\) has color \(2\). The neighbors of \(u_3\) are \(v_2,v_4\), both colored \(2\), while \(u_3\) has color \(1\). The neighbors of \(u_4\) are \(v_3,v_5\), colored \(1,3\), while \(u_4\) has color \(2\). The neighbors of \(u_5\) are \(v_4,v_1\), colored \(2,1\), while \(u_5\) has color \(3\). Thus every edge of this type has differently colored endpoints. Finally, \(w\) has color \(4\), while each of \(u_1,\ldots,u_5\) has color \(1\), \(2\), or \(3\), so all five edges incident with \(w\) also have differently colored endpoints.
Check: the color classes have sizes \(4,4,2,1\), respectively, and \(4+4+2+1=11\), accounting for every vertex. The edge checks above cover all \(5+10+5=20\) edges, so this is a proper four-coloring.
Why Three Colors Cannot Suffice
The coloring gives an upper bound, but determining the chromatic number also requires a lower bound. Suppose there were a proper coloring with at most three colors. We may label the color of \(w\) as color \(3\). Since every shadow is adjacent to \(w\), each shadow must then have color \(1\) or \(2\). That restriction forces a condition on the original cycle that cannot be satisfied.
Proof. The coloring above proves \(\chi(G)\leq4\). For the reverse inequality, suppose, to obtain a contradiction, that \(G\) has a proper coloring with at most three colors. Label the color of \(w\) as \(3\), and label the other available colors \(1\) and \(2\). Because \(wu_i\in E\) for every \(i\), each \(u_i\) has color \(1\) or \(2\).
The shadow \(u_i\) is adjacent to both \(v_{i-1}\) and \(v_{i+1}\). If those two original vertices had colors \(1\) and \(2\) in either order, then neither available color for \(u_i\) would differ from both neighbors. Properness therefore requires that at least one of \(v_{i-1}\) and \(v_{i+1}\) have color \(3\), for each \(i\).
The pairs \(v_{i-1}v_{i+1}\) form a five-cycle: in order, its vertices are \(v_1,v_3,v_5,v_2,v_4\), and its final edge returns from \(v_4\) to \(v_1\). The preceding condition says that the color-\(3\) vertices among \(v_1,\ldots,v_5\) meet every edge of this five-cycle; in other words, they form a vertex cover of it. A vertex cover of a five-cycle has at least three vertices, because each selected vertex is incident with at most two cycle edges, so covering all five edges requires \(2|S|\geq5\), hence \(|S|\geq3\).
On the other hand, the vertices of color \(3\) among \(v_1,\ldots,v_5\) are pairwise nonadjacent on the original cycle: a proper coloring cannot give the same color to adjacent vertices. An independent set in a five-cycle has at most two vertices. Indeed, each selected vertex has a following vertex around the cycle that is not selected, and these following vertices are distinct, so the number selected is at most the number not selected; with five vertices, this gives at most two. Thus the color-\(3\) vertices among the original cycle cannot both be a vertex cover of the other five-cycle and have size at most two. This contradiction rules out a coloring with three or fewer colors. Therefore \(\chi(G)\geq4\), and combining the two bounds gives \(\chi(G)=4\). \(\square\)
Common Counting and Coloring Errors
A common edge-counting error is to count only one edge from each shadow to the original cycle. That gives the incorrect total \(5+5+5=15\): five cycle edges, five supposed shadow edges, and five edges from \(w\). But each shadow \(u_i\) is adjacent to two cycle vertices, not one. The correct count is \(5+2\cdot5+5=5+10+5=20\), independently confirmed by the degree sum \(40\).
A separate coloring pitfall is to color each shadow the same as its corresponding original vertex. A shadow \(u_i\) is not adjacent to \(v_i\); it is adjacent to \(v_{i-1}\) and \(v_{i+1}\). Its color must be checked against those two vertices, as well as against \(w\). For instance, in the coloring above \(u_3\) has color \(1\), while both its neighbors \(v_2\) and \(v_4\) have color \(2\). The check is determined by the actual edge list, not by matching a shadow to its name.
The graph is a concrete demonstration that having no triangle does not guarantee a three-coloring. The triangle-free proof rules out a clique of size three, while the coloring proof establishes that four colors are still necessary. These are distinct checks: ruling out triangles concerns sets of pairwise adjacent vertices, whereas ruling out a three-coloring concerns all possible assignments of three colors to the whole graph.
Check Your Understanding
Use the stated vertex and edge lists when checking your answers.
- List the neighbors of \(u_4\), and explain why they cannot form a triangle with \(u_4\).
- Verify the degree of \(v_5\) directly from the edge set. Which four vertices are its neighbors?
- In the four-coloring, which colors appear on the neighbors of \(u_2\), and why is \(u_2\)'s assigned color valid?
- Explain why the neighbors of \(w\) cannot include two vertices that complete a triangle with \(w\).
- In the proof that three colors are insufficient, why must the color-\(3\) vertices on the original cycle cover the cycle with edges \(v_{i-1}v_{i+1}\)?