The Construction and the Claim
A graph can require many colors even when it has no large complete subgraph. The Mycielski construction gives a systematic way to raise a graph’s chromatic number while retaining its original vertices and edges. The key point is that the new vertices are arranged so that one extra color always suffices, but using only the original number of colors would produce a coloring of the original graph with fewer colors.
All graphs here are finite and simple. A proper coloring assigns colors to vertices so that adjacent vertices receive different colors. The chromatic number \(\chi(G)\) is the least number of colors in a proper coloring of \(G\). We consider graphs with at least one vertex, so their chromatic number \(k\) is at least \(1\).
Thus each clone \(u_j\) is adjacent to the original neighbors of \(v_j\), not to \(v_j\) itself. The apex \(w\) is adjacent to every clone. These details are essential: the coloring argument depends on precisely which pairs are adjacent.
The Upper Bound: One Extra Color Suffices
First, we show \(\chi(M(G))\le k+1\). Take a proper \(k\)-coloring of \(G\), and give each clone \(u_i\) the same color as its original vertex \(v_i\). Give \(w\) a new color not used on \(G\).
Original edges remain properly colored because the original coloring was proper. If \(v_i u_j\) is a new edge, then \(v_iv_j\) was an edge of \(G\), so \(v_i\) and \(v_j\) have different colors; consequently \(v_i\) and \(u_j\) have different colors as well. Clones are pairwise nonadjacent, and \(w\) has a color different from every clone. Hence this is a proper \((k+1)\)-coloring.
Worked Example: The Mycielski Graph of a Four-Cycle
Let \(G=C_4\) have \(V(G)=\{a,b,c,d\}\) and \(E(G)=\{ab,bc,cd,da\}\). Use \(A,B,C,D\) for the clones of \(a,b,c,d\), respectively, and \(z\) for the apex. The construction gives
\(V(M(G))=\{a,b,c,d,A,B,C,D,z\}\), with edge set
\(E(M(G))=\{ab,bc,cd,da,\ aB,aD,bA,bC,cB,cD,dA,dC,\ zA,zB,zC,zD\}\).
The original cycle has a proper 2-coloring: assign color 1 to \(a,c\) and color 2 to \(b,d\). Give \(A,C\) color 1, give \(B,D\) color 2, and give \(z\) color 3. Each original edge joins colors 1 and 2. Each cross-edge listed above also joins those colors: for example, \(aB\) joins 1 to 2, and \(bA\) joins 2 to 1. The four edges incident with \(z\) join color 3 to either 1 or 2. This verifies a proper 3-coloring.
Check: \(C_4\) has chromatic number 2: the displayed coloring uses 2 colors, and its edge \(ab\) prevents a 1-coloring. The theorem therefore predicts \(\chi(M(C_4))=3\); the coloring just checked achieves that upper bound.
The Lower Bound: Why \(k\) Colors Cannot Suffice
The original graph is present in \(M(G)\), so any coloring of \(M(G)\) uses at least \(k\) colors. That observation alone does not establish the stronger lower bound \(k+1\). We now prove that a \(k\)-coloring of \(M(G)\) would force a \((k-1)\)-coloring of \(G\).
Proof. Suppose first that \(k\ge2\), and assume for contradiction that \(M(G)\) has a proper coloring with at most \(k\) colors. If it uses fewer than \(k\), it also uses at most \(k\), so it suffices to analyze this case. Relabel the colors, if necessary, so that the apex \(w\) has color \(k\). Because every clone \(u_i\) is adjacent to \(w\), no clone has color \(k\); every clone therefore has one of the colors \(1,\dots,k-1\).
Define a coloring of the original vertices as follows: if \(v_i\) has a color other than \(k\), keep that color; if \(v_i\) has color \(k\), give \(v_i\) the color of its clone \(u_i\). We verify that every original edge \(v_iv_j\) has differently colored endpoints. If neither endpoint originally had color \(k\), their colors remain different because the assumed coloring of \(M(G)\) was proper. They cannot both have had color \(k\), since they are adjacent. If, for example, \(v_i\) had color \(k\), then \(v_j\) had a different color. By the construction, \(u_i\) is adjacent to \(v_j\), so \(u_i\) and \(v_j\) have different colors. The new color of \(v_i\), which is the color of \(u_i\), is therefore different from the unchanged color of \(v_j\). This gives a proper coloring of \(G\) using only colors \(1,\dots,k-1\), contradicting \(\chi(G)=k\).
If \(k=1\), then \(G\) has at least one vertex, say \(v_i\), and \(M(G)\) contains the edge \(wu_i\). Thus \(M(G)\) cannot be colored with one color. In every case, \(M(G)\) cannot be colored with \(k\) or fewer colors, so \(\chi(M(G))\ge k+1\). Together with the upper bound, this proves the theorem. \(\square\)
Worked Example: The Mycielski Graph of a Triangle
Let \(G=K_3\), with \(V(G)=\{a,b,c\}\) and \(E(G)=\{ab,ac,bc\}\). Let \(A,B,C\) be the corresponding clones and \(z\) the apex. Then
\(V(M(G))=\{a,b,c,A,B,C,z\}\), and
\(E(M(G))=\{ab,ac,bc,\ aB,aC,bA,bC,cA,cB,\ zA,zB,zC\}\).
Color the original vertices \(a,b,c\) with colors 1, 2, 3, respectively, and give \(A,B,C\) the same colors as \(a,b,c\), respectively. Every original edge joins distinct colors. Each cross-edge also joins distinct colors; for instance, \(aB\) joins colors 1 and 2, and \(cA\) joins colors 3 and 1. Give \(z\) color 4, which differs from the color on each of its neighbors. This verifies a proper 4-coloring.
For the lower bound, suppose \(M(K_3)\) had a coloring with at most 3 colors. Relabel so that \(z\) has color 3. Then \(A,B,C\) all have colors 1 or 2. The proof’s recoloring rule replaces any original vertex of color 3 with the color of its clone and leaves the other original colors unchanged. The rule produces a proper coloring of the triangle using only colors 1 and 2. That is impossible: its three pairwise adjacent vertices must receive three different colors. Therefore \(\chi(M(K_3))\ge4\), and the exhibited coloring shows \(\chi(M(K_3))=4\).
Check: \(K_3\) has chromatic number 3 because its three vertices are pairwise adjacent and can be assigned three different colors. The construction’s lower-bound argument rules out 3 colors on \(M(K_3)\), while the explicit coloring uses 4.
Worked Example: The Mycielski Graph of a Three-Vertex Path
Let \(G=P_3\) have \(V(G)=\{p,q,r\}\) and \(E(G)=\{pq,qr\}\). Use \(P,Q,R\) for the clones and \(z\) for the apex. The resulting graph has
\(V(M(G))=\{p,q,r,P,Q,R,z\}\), and
\(E(M(G))=\{pq,qr,\ pQ,qP,qR,rQ,\ zP,zQ,zR\}\).
The path is properly colored by giving \(p,r\) color 1 and \(q\) color 2. Give \(P,R\) color 1, \(Q\) color 2, and \(z\) color 3. The original edges \(pq,qr\) join 1 to 2. The cross-edges \(pQ,rQ\) join 1 to 2, while \(qP,qR\) join 2 to 1. Each edge from \(z\) joins color 3 to a clone of color 1 or 2. Thus the coloring is proper.
The path has chromatic number 2 because it has an edge, so one color is not enough, and the coloring above uses two. The theorem gives the matching lower bound \(\chi(M(P_3))\ge3\), while the displayed coloring gives \(\chi(M(P_3))\le3\). Therefore \(\chi(M(P_3))=3\).
Check: The edge list contains the two original edges, the four cross-edges obtained from the two original edges in both directions, and the three apex-to-clone edges. These are exactly the edge categories in the definition; the displayed coloring checks each category.
Common Pitfall and Why the Proof Matters
A frequent error is to reason that the original graph is a subgraph of \(M(G)\), so \(\chi(M(G))\ge k\), and then conclude that \(\chi(M(G))=k+1\). The inequality only gives a lower bound of \(k\); it does not rule out a \(k\)-coloring. For example, in the triangle example, the subgraph argument alone says only that at least 3 colors are needed. The separate recoloring argument is what rules out 3 colors and raises the lower bound to 4.
Another tempting but invalid coloring attempt is to give the original vertices of \(K_3\) colors 1, 2, 3, give their clones the matching colors, and try to color the apex with color 1. This fails because \(z\) is adjacent to \(A\), which has color 1. The construction’s upper-bound coloring deliberately reserves a new color for the apex. More importantly, the lower-bound proof does not depend on this particular attempted coloring: it shows that any coloring with only \(k\) colors would lead to the forbidden \((k-1)\)-coloring of \(G\).
The two bounds have different roles. Copying the original colors onto the clones proves that \(k+1\) colors are enough. Recoloring original vertices that use the apex’s color proves that \(k\) colors are not enough. Together they give an exact value, not merely a bound. This exact increase is useful when applying the construction to graphs whose chromatic number is known.
Check Your Understanding
Use the definition and the two bounds to answer the following questions.
- In \(M(G)\), which original vertices are adjacent to a clone \(u_j\)? Is \(u_j\) adjacent to \(v_j\)?
- Explain why assigning each clone the color of its corresponding original vertex is valid on every cross-edge.
- In the lower-bound proof, why can the color of the apex be relabeled as \(k\), and why can no clone then use color \(k\)?
- For \(G=P_3\), verify directly from the edge list that the coloring in the worked example is proper.
- Why does knowing only that \(G\) is a subgraph of \(M(G)\) fail to prove \(\chi(M(G))\ge k+1\)?