Chromatic Number and Clique Number Can Diverge
A clique gives a lower bound on the number of colors: the vertices in a clique must all receive different colors. It is tempting to expect that graphs with small cliques therefore need only a small number of colors. The Mycielski construction shows that this expectation fails dramatically. Starting with a single edge and repeatedly applying the construction gives graphs with clique number two and chromatic number as large as desired.
All graphs in this tutorial are finite and simple. A proper coloring assigns colors to vertices so that adjacent vertices have different colors; the chromatic number \(\chi(G)\) is the least number of colors in a proper coloring of \(G\). A clique is a set of pairwise adjacent vertices, and the clique number \(\omega(G)\) is the largest size of a clique. A graph is triangle-free if it contains no cycle of length three. In a triangle-free graph every clique has size at most two.
The Construction and Its Two Properties
- each original edge \(v_iv_j\in E\);
- the two edges \(u_iv_j\) and \(u_jv_i\) for every original edge \(v_iv_j\in E\);
- the edges \(wu_i\) for all \(1\le i\le n\).
The original graph remains as a subgraph, but each old vertex also has a shadow that connects to the old vertex’s former neighbors. The new vertex \(w\) is adjacent to every shadow. These added edges are chosen to make the chromatic number rise, while avoiding the formation of triangles when the starting graph is triangle-free.
Proof. Write \(k=\chi(G)\). First, a proper \(k\)-coloring of \(G\) gives a proper \((k+1)\)-coloring of \(M(G)\): give each original vertex its color in \(G\), give each shadow \(u_i\) the color of \(v_i\), and give \(w\) a new color. Original edges are properly colored. If \(v_iv_j\) is an edge, then \(v_i\) and \(v_j\) have different colors, so each of the cross-edges \(u_iv_j\) and \(u_jv_i\) also has endpoints of different colors. Finally, \(w\) has a new color, different from every shadow’s color. Thus \(\chi(M(G))\le k+1\).
For the reverse inequality, suppose \(M(G)\) has a proper coloring with \(q\) colors. Since \(G\) has at least one vertex, \(M(G)\) has an edge \(wu_i\), so \(q\ge2\). Rename the colors so that \(w\) has color \(q\). No shadow has color \(q\), because every shadow is adjacent to \(w\). Construct a coloring of \(G\) using only colors \(1,\dots,q-1\): keep the color of \(v_i\) if it is not \(q\), and otherwise assign to \(v_i\) the color of \(u_i\). To check this coloring, take any original edge \(v_iv_j\). The two original vertices could not both have had color \(q\), since they are adjacent. If neither had color \(q\), their colors remain different. If, for example, \(v_i\) had color \(q\), then \(v_j\) retains its old color, and \(u_i\) is adjacent to \(v_j\); hence the new color of \(v_i\), which is the color of \(u_i\), differs from the color of \(v_j\). The same argument applies if \(v_j\) had color \(q\). This is a proper coloring of \(G\) with \(q-1\) colors, so \(k\le q-1\). Therefore every coloring of \(M(G)\) uses at least \(k+1\) colors. Combining the bounds proves the equality. \(\square\)
Proof. A triangle containing \(w\) would require two adjacent shadows, but there are no edges between shadows. Consider a triangle not containing \(w\). If all three vertices are original vertices, they would form a triangle in \(G\), which does not exist. If exactly one vertex is a shadow, say \(u_i\), the other two must be original vertices \(v_j,v_\ell\). The required edges \(u_iv_j\) and \(u_iv_\ell\) imply that \(v_iv_j\) and \(v_iv_\ell\) are edges of \(G\), by the definition of \(M(G)\); the edge \(v_jv_\ell\) is also required for the proposed triangle. Thus \(v_i,v_j,v_\ell\) form a triangle in \(G\), a contradiction. If a triangle contains two shadows, it would require an edge between them, which does not exist. All possibilities lead to a contradiction, so \(M(G)\) is triangle-free. \(\square\)
Iterating the Construction
Begin with \(G_2=K_2\), the graph on vertices \(\{a,b\}\) with edge \(ab\). Define \(G_{r+1}=M(G_r)\) for each integer \(r\ge2\). The graph \(G_2\) is triangle-free and has chromatic number two. The lemma shows at each step that triangle-freeness is preserved, and the theorem shows that the chromatic number increases by exactly one.
Proof. We use induction on \(r\). The base graph \(G_2=K_2\) has no triangle, its two adjacent vertices require two colors, and its largest clique has size two. Suppose the assertions hold for \(G_r\). By the triangle-free preservation lemma, \(G_{r+1}=M(G_r)\) is triangle-free. By the chromatic-number theorem, \(\chi(G_{r+1})=\chi(G_r)+1=r+1\). Since \(G_{r+1}\) is triangle-free, it has no clique of size three or more. It has an edge: \(G_r\) has an edge by its clique number, and every original edge is retained in \(M(G_r)\). Therefore \(G_{r+1}\) has a clique of size two and no larger clique, so \(\omega(G_{r+1})=2\). This completes the induction. \(\square\)
In particular, “arbitrarily large chromatic number” means that for each integer \(r\ge2\), one can produce a finite graph with chromatic number \(r\) while keeping the clique number fixed at two. There is no bound on \(\chi(G)\) that depends only on \(\omega(G)\), even among triangle-free graphs.
Worked Example: The First Iterate Is a 5-Cycle
Let \(G_2\) have \(V(G_2)=\{a,b\}\) and \(E(G_2)=\{ab\}\). Its Mycielski graph has vertex set \(\{a,b,u_a,u_b,w\}\). The original edge is \(ab\); the shadow edges are \(u_ab\) and \(u_ba\); and the edges incident to \(w\) are \(wu_a\) and \(wu_b\). Thus \(E(G_3)=\{ab,u_ab,u_ba,wu_a,wu_b\}\).
These edges form the cycle \(a,b,u_a,w,u_b,a\), with five distinct vertices and five edges. Therefore \(G_3\) is \(C_5\). The theorem gives \(\chi(G_3)=\chi(G_2)+1=2+1=3\), and the preservation lemma gives triangle-freeness. Since \(G_3\) has an edge, its clique number is exactly two.
Check: a 3-coloring is \(a=1\), \(b=2\), \(u_a=1\), \(w=3\), \(u_b=2\). The five listed edges have endpoint colors \(1,2\); \(1,2\); \(2,1\); \(3,1\); and \(3,2\), respectively, so each is properly colored. Two colors cannot suffice: along a cycle, a 2-coloring must alternate, and after an odd number of edges the last vertex would need both the same color as the first and a different color from it. This directly confirms \(\chi(G_3)=3\).
Worked Example: The Next Iterate Has 11 Vertices
Use \(G_3=C_5\) with vertices \(x_1,\dots,x_5\) and edges \(x_1x_2,x_2x_3,x_3x_4,x_4x_5,x_5x_1\). Its Mycielski graph \(G_4\) has vertex set \(\{x_1,\dots,x_5,y_1,\dots,y_5,z\}\). Its edge set consists of the five original edges, the ten cross-edges \(y_1x_2,y_2x_1,y_2x_3,y_3x_2,y_3x_4,y_4x_3,y_4x_5,y_5x_4,y_5x_1,y_1x_5\), and the five edges \(zy_1,zy_2,zy_3,zy_4,zy_5\).
The vertex count is \(5+5+1=11\). The chromatic-number theorem gives \(\chi(G_4)=\chi(G_3)+1=3+1=4\), and the triangle-free lemma shows \(G_4\) is triangle-free. It has original edges, so \(\omega(G_4)=2\). For a direct upper-bound check, color the original cycle by \(x_1=1,x_2=2,x_3=1,x_4=2,x_5=3\), give each \(y_i\) the color of \(x_i\), and give \(z\) color \(4\). The five original edges join different colors; each cross-edge joins colors of adjacent vertices of the original cycle, which differ; and each \(zy_i\) joins color \(4\) to one of \(1,2,3\). This is a proper 4-coloring, consistent with the theorem’s lower bound of four.
Check: the edge count from the three construction classes is \(5+10+5=20\). The five original edges and the five edges at \(z\) are distinct; each of the five cycle edges contributes two cross-edges, giving ten distinct cross-edges. Thus the edge list contains exactly 20 edges.
Worked Example: A 23-Vertex Graph Requiring Five Colors
Here is \(G_5=M(G_4)\) specified directly from the preceding edge list. Let \(H=G_4\), with the 11 vertices and 20 edges just given. For each \(v\in V(H)\), introduce vertices \(h_v\) and \(k_v\), and introduce \(q\). Set \(V(G_5)=\{h_v:v\in V(H)\}\cup\{k_v:v\in V(H)\}\cup\{q\}\). Set \(E(G_5)=\{h_vh_t:vt\in E(H)\}\cup\{k_vh_t,k_th_v:vt\in E(H)\}\cup\{qk_v:v\in V(H)\}\). Since \(H\)'s vertex and edge lists are explicitly specified above, these sets specify every vertex and edge of this graph.
The vertex count is \(11+11+1=23\). The original-edge class has 20 edges. Each of the 20 edges of \(H\) contributes two cross-edges, so that class has \(2\cdot20=40\) edges. The last class has 11 edges. These classes are disjoint, giving \(20+40+11=71\) edges. The theorem gives \(\chi(G_5)=\chi(G_4)+1=4+1=5\), while the lemma makes \(G_5\) triangle-free. It has an edge because it retains every edge of \(H\) among the original vertices. Hence \(\omega(G_5)=2\).
Check: the four-coloring of \(H\) described in the previous example extends to a five-coloring of \(G_5\): give \(h_v\) and \(k_v\) the color assigned to \(v\), and give \(q\) color \(5\). The original edges remain properly colored; a cross-edge \(k_vh_t\) joins the colors of adjacent \(v,t\) in \(H\), so its endpoints differ; and \(q\) differs from every \(k_v\). This verifies the upper bound of five colors, while the theorem supplies the matching lower bound.
What the Examples Do—and Do Not—Show
These iterates separate two different constraints on coloring. A clique of size \(s\) forces at least \(s\) colors, but knowing that there is no large clique does not give an upper bound on the number of colors. The construction repeatedly creates a new obstruction to using the old number of colors without creating any triangle.
Common mistake: “Triangle-free means 2-colorable.” This is false. The graph with \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51\}\) is triangle-free, but it is not 2-colorable: alternating colors around its five edges would require the last edge to join vertices of the same color. The correct conclusion from triangle-freeness is \(\omega(G)\le2\), not \(\chi(G)\le2\). In the iterated examples, the chromatic number is determined by the Mycielski theorem, not by the absence of triangles.
The key quantifiers are worth keeping explicit: for every chosen number of colors \(r\ge2\), an iterate \(G_r\) exists with \(\chi(G_r)=r\) and \(\omega(G_r)=2\). Thus small clique number alone cannot control chromatic number. Other graph information may still give useful coloring bounds, but clique size by itself does not.
Check Your Understanding
Use the construction and its two proved properties to answer the following.
- Starting from \(G_2=K_2\), what are \(\chi(G_6)\) and \(\omega(G_6)\)? Give the induction step that justifies each value.
- Explain why a triangle in \(M(G)\) cannot contain the new vertex \(w\).
- In the lower-bound proof for \(\chi(M(G))\), why does recoloring an original vertex \(v_i\) of color \(q\) with the color of \(u_i\) preserve the coloring across each edge incident to \(v_i\)?
- For a triangle-free graph that contains at least one edge, prove that its clique number is exactly two.
- Why does the existence of \(G_r\) for every integer \(r\ge2\) rule out any upper bound on chromatic number that depends only on clique number?