Building a Sequence from \(K_2\)
The Mycielski construction turns a graph into a larger graph while increasing its chromatic number. Starting with \(K_2\), repeated applications produce graphs whose chromatic numbers grow without introducing triangles. To understand an iteration, it helps to track three things separately: which edges are retained, which new edges are added, and how the counts and coloring properties change.
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 graph is triangle-free if it contains no cycle of length \(3\).
- every original edge \(v_iv_j\in E\);
- the two edges \(u_iv_j\) and \(u_jv_i\) for each original edge \(v_iv_j\in E\);
- the edges \(wu_i\) for \(1\le i\le n\).
Write \(n=|V(G)|\) and \(m=|E(G)|\). Each step retains the \(n\) original vertices and adds \(n+1\) vertices. Each original edge generates two edges between an original vertex and a new \(u\)-vertex, and \(w\) contributes one edge to each of the \(n\) vertices \(u_i\). These are distinct edge classes: the original edges have two original endpoints, the generated edges have one \(u\)-vertex endpoint, and the edges incident to \(w\) have endpoint \(w\). Thus no edge is counted twice.
Counts Under Repeated Construction
Proof. There are \(n\) original vertices, \(n\) vertices \(u_i\), and the single vertex \(w\), so \(|V(M(G))|=2n+1\). For the edges, the construction retains \(m\) original edges, adds two edges for each of the \(m\) original edges, and adds \(n\) edges incident to \(w\). Therefore \(|E(M(G))|=m+2m+n=3m+n\).
For the iteration, \(G_0=K_2\) has \(n_0=2\) vertices and \(m_0=1\) edge. The one-step formulas give \(n_{r+1}=2n_r+1\) and \(m_{r+1}=3m_r+n_r\). To solve the first recurrence, add \(1\) to both sides: \(n_{r+1}+1=2(n_r+1)\). Since \(n_0+1=3\), repeated substitution gives \(n_r+1=3\cdot2^r\), hence \(n_r=3\cdot2^r-1\).
We verify the proposed edge formula by induction. At \(r=0\), it gives \((7-6+1)/2=1=m_0\). If it holds at \(r\), then $$ \begin{aligned} m_{r+1} &=3m_r+n_r\\ &=\frac{21\cdot3^r-18\cdot2^r+3}{2} +3\cdot2^r-1\\ &=\frac{21\cdot3^r-12\cdot2^r+1}{2}\\ &=\frac{7\cdot3^{r+1}-6\cdot2^{r+1}+1}{2}. \end{aligned} $$ This is the claimed formula at \(r+1\). Both formulas therefore hold for every \(r\ge0\). \(\square\)
Worked Example: The First Construction from \(K_2\)
Let \(G_0=K_2\), with \(V(G_0)=\{a,b\}\) and \(E(G_0)=\{ab\}\). The new vertices are \(a',b'\), and \(w\). Retain \(ab\); the edge \(ab\) generates \(a'b\) and \(b'a\); and \(w\) is joined to \(a'\) and \(b'\). Thus $$ V(G_1)=\{a,b,a',b',w\},\qquad E(G_1)=\{ab,a'b,b'a,wa',wb'\}. $$
There are \(2\cdot2+1=5\) vertices. The edge formula gives \(3\cdot1+2=5\) edges, agreeing with the displayed list. In the order \(a,b,a',w,b'\), the edges form the cycle \(a,b,a',w,b',a\), so \(G_1\) is a 5-cycle.
Check: the 5-cycle has five distinct edges, exactly as the construction count predicts. Its vertices can be colored with three colors, for example \(a,a'\) with color 1, \(b,w\) with color 2, and \(b'\) with color 3; every listed edge has differently colored endpoints. The chromatic-number result proved below will show that two colors are not enough.
Triangle-Freeness Persists
Proof. Suppose, for a contradiction, that \(M(G)\) contains a triangle. If all three vertices are original vertices, their three edges were already in \(G\), giving a triangle in \(G\), contrary to the hypothesis. If the triangle contains \(w\), its other two vertices must both be among the \(u_i\), because \(w\) is adjacent only to those vertices. But no two \(u_i\) are adjacent, so that cannot be a triangle.
It remains to consider a triangle not containing \(w\) but containing at least one \(u_i\). It cannot contain two \(u\)-vertices, since there are no edges between them. If its vertices are \(u_i,v_j,v_k\), then the edges \(u_iv_j\) and \(u_iv_k\) mean that \(v_i v_j\) and \(v_i v_k\) are edges of \(G\), by the edge-generation rule. The third edge \(v_jv_k\) is also an original edge. Hence \(v_i,v_j,v_k\) form a triangle in \(G\), again a contradiction. These cases exhaust all possible triangles, proving that \(M(G)\) is triangle-free. \(\square\)
The graph \(K_2\) is triangle-free because it has only two vertices. Applying the theorem at each step therefore shows that every \(G_r\) is triangle-free.
Worked Example: Constructing the Next Graph Explicitly
Use the labels \(1=a\), \(2=b\), \(3=a'\), \(4=b'\), and \(5=w\) for \(G_1\). Then $$ V(G_1)=\{1,2,3,4,5\},\qquad E(G_1)=\{12,23,35,45,14\}. $$ Apply the construction with new vertices \(1',2',3',4',5'\) and \(z\). The original edges remain. The five original edges generate, respectively, $$ \begin{array}{c|c} \text{Original edge}&\text{Generated edges}\\ 12&1'2,\ 2'1\\ 23&2'3,\ 3'2\\ 35&3'5,\ 5'3\\ 45&4'5,\ 5'4\\ 14&1'4,\ 4'1 \end{array} $$ and the edges incident to \(z\) are \(z1',z2',z3',z4',z5'\). Thus \(G_2\) has vertex set \(\{1,2,3,4,5,1',2',3',4',5',z\}\) and edge set $$ \begin{aligned} E(G_2)=\{&12,23,35,45,14,\\ &1'2,2'1,2'3,3'2,3'5,5'3,4'5,5'4,1'4,4'1,\\ &z1',z2',z3',z4',z5'\}. \end{aligned} $$
The vertex count is \(2\cdot5+1=11\), and the edge count is \(3\cdot5+5=20\). Independently, the displayed list has five original edges, ten generated edges, and five edges incident to \(z\), for \(5+10+5=20\) altogether. The triangle-freeness theorem applies because \(G_1\) is triangle-free.
Check: the edges in the displayed set fall into the three disjoint classes required by the construction. In particular, the five edges incident to \(z\) are not among the ten generated edges, so none has been counted twice.
Why Each Step Raises the Chromatic Number
Proof. Put \(k=\chi(G)\). First, a coloring of \(M(G)\) with \(k+1\) colors can be made from a proper \(k\)-coloring of \(G\): give each original vertex \(v_i\) its old color, give \(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 both generated edges \(u_iv_j\) and \(u_jv_i\) do too. Each edge incident to \(w\) has endpoints of different colors. Thus \(\chi(M(G))\le k+1\).
For the reverse inequality, take any proper coloring of \(M(G)\) using \(q\) colors. Let \(c\) be the color of \(w\). Every \(u_i\) has a color different from \(c\), because \(wu_i\) is an edge. Construct a coloring of the original graph \(G\) using only colors other than \(c\): keep the color of \(v_i\) if it is not \(c\), and replace it by the color of \(u_i\) if \(v_i\) has color \(c\).
To check that this is proper, take any edge \(v_iv_j\) of \(G\). If neither endpoint originally has color \(c\), their colors remain different because the coloring of \(M(G)\) was proper. They cannot both have color \(c\), since \(v_iv_j\) is an edge. If \(v_i\) has color \(c\), then \(v_j\)'s original color differs from \(c\), and \(u_i\) is adjacent to \(v_j\). Consequently, the replacement color of \(v_i\), namely the color of \(u_i\), differs from the color of \(v_j\). The same reasoning applies if \(v_j\) has color \(c\). Thus the new coloring is proper and uses at most \(q-1\) colors. It follows that \(k=\chi(G)\le q-1\), so every coloring of \(M(G)\) uses at least \(k+1\) colors. Combining the two bounds proves the theorem. \(\square\)
Worked Example: Three Iterations from \(K_2\)
Let \(G_0=K_2\), \(G_1=M(G_0)\), \(G_2=M(G_1)\), and \(G_3=M(G_2)\). The starting graph has \(\chi(G_0)=2\), since its two adjacent vertices require different colors and can be assigned two colors. The chromatic-number theorem gives \(\chi(G_1)=2+1=3\), \(\chi(G_2)=3+1=4\), and \(\chi(G_3)=4+1=5\).
For the counts, \(G_2\) has 11 vertices and 20 edges, as computed in the preceding example. The next construction therefore gives \(2\cdot11+1=23\) vertices and \(3\cdot20+11=71\) edges. The closed formulas independently give, at \(r=3\), $$ |V(G_3)|=3\cdot2^3-1=24-1=23,\qquad |E(G_3)|=\frac{7\cdot3^3-6\cdot2^3+1}{2} =\frac{189-48+1}{2}=71. $$
Thus \(G_3\) is specified by the construction applied to the explicit \(G_2\) above: retain its 20 listed edges, generate two edges from each of them, and join the new vertex to each of the 11 new \(u\)-vertices. The edge classes contribute \(20+40+11=71\) distinct edges. The triangle-freeness theorem applies successively from \(G_0\), so \(G_3\) is triangle-free as well.
Check: the recurrence and closed formulas agree at \(r=3\): both give 23 vertices and 71 edges. The chromatic number is 5 by three applications of the proved increment theorem.
Iteration Summary and a Common Counting Error
The formulas describe a systematic trade-off: each construction more than doubles the number of vertices, adds edges in three identifiable groups, preserves triangle-freeness, and raises the chromatic number by one. For the first few stages, the results are:
| Iteration \(r\) | Vertices | Edges | Chromatic number |
|---|---|---|---|
| 0 | 2 | 1 | 2 |
| 1 | 5 | 5 | 3 |
| 2 | 11 | 20 | 4 |
| 3 | 23 | 71 | 5 |
Common pitfall: counting only one generated edge per old edge. A mistaken edge recurrence is \(m'=2m+n\), on the grounds that each old edge contributes one new edge in addition to itself. But an old edge \(v_iv_j\) contributes both \(u_iv_j\) and \(u_jv_i\). For \(G_1\), this incorrect recurrence would give \(2\cdot1+2=4\) edges, while the actual edge set has \(1+2+2=5\). The correct recurrence is \(m'=m+2m+n=3m+n\).
Another useful check is to keep the three edge classes separate at every step. This prevents both omissions and double-counting, and it makes the recurrence valid even when the input graph has isolated vertices: each such vertex still contributes one new \(u_i\) and one edge \(wu_i\), but no generated edge from an old edge.
Check Your Understanding
Use the construction rules and proved results to answer each question.
- Starting from a graph with 7 vertices and 9 edges, how many vertices and edges does its Mycielski graph have?
- Starting from \(K_2\), compute the vertex count, edge count, and chromatic number after four iterations.
- Explain why the two edges generated from one original edge are distinct, and why neither is an original edge.
- In the chromatic-number proof, why can a vertex \(v_i\) colored like \(w\) be recolored with the color of \(u_i\)?
- Which possible triangle cases are ruled out by the absence of edges between \(u\)-vertices and the fact that \(w\) is adjacent only to \(u\)-vertices?