From One Edge to a Five-Cycle
The Mycielski construction transforms a graph into a larger graph by adding a shadow of each vertex and one new apex. Applying it to the smallest complete graph with an edge, \(K_2\), gives a compact example in which every part of the construction can be checked directly. The point here is to keep track of exactly which edges are added: the result has five vertices, five edges, and is a cycle of length five.
All graphs in this tutorial are finite and simple. In the construction, the original vertices retain their names, each original vertex receives a distinct shadow vertex, and a separate apex is added. These three types of vertices are kept distinct even when their labels are related.
Thus the original edges stay between original vertices. The new edges associated with an original edge connect an original vertex to the other endpoint’s shadow, and the apex is adjacent to all shadows. In particular, the apex is not joined to any original vertex by this definition.
Counting the Vertices and Edges
The construction gives a useful count before we work out the individual edges. Write \(n=|V|\) and \(m=|E|\). There are \(n\) original vertices, \(n\) shadows and one apex. The original edges contribute \(m\) edges. Each original edge contributes two distinct original-to-shadow edges, for \(2m\) such edges altogether. Finally, the apex contributes \(n\) edges.
Proof. The original vertices and their shadows are disjoint sets, each of size \(n\), and the apex is one additional vertex. Hence \(|V(M(G))|=n+n+1=2n+1\). The three edge types are disjoint: original edges have two original endpoints, the cross-edges have one original endpoint and one shadow endpoint, and apex edges have the apex as an endpoint. There are \(m\) original edges, \(2m\) cross-edges, and \(n\) apex edges, so \(|E(M(G))|=m+2m+n=3m+n\). Distinct original edges give distinct cross-edges because their endpoint pairs are distinct; the simplicity of \(G\) rules out loops or repeated original edges. \(\square\)
This count also covers the empty graph: if \(n=m=0\), the construction consists of the single apex and has no edges, in agreement with \(2n+1=1\) and \(3m+n=0\). For \(K_2\), the count predicts five vertices and five edges. We now identify them explicitly.
Worked Example: Constructing \(M(K_2)\) from Its Edge List
Let \(G=K_2\) have vertex set \(V(G)=\{a,b\}\) and edge set \(E(G)=\{ab\}\). Create shadows \(a'\) and \(b'\), and apex \(z\). Therefore
First retain the original edge \(ab\). Next, the one original edge \(ab\) contributes the two cross-edges \(ab'\) and \(a'b\). Finally, join the apex to both shadows, adding \(za'\) and \(zb'\). The complete edge set is
There are \(1+2+2=5\) listed edges: one original edge, two cross-edges and two apex edges. The general count gives the same result: here \(n=2\) and \(m=1\), so \(|V(M(G))|=2(2)+1=5\) and \(|E(M(G))|=3(1)+2=5\).
Check: the five displayed edges are all distinct, and each has two different endpoints. The vertex and edge counts therefore agree with the construction and with the formula.
Verifying the Five-Cycle
Having five vertices and five edges does not by itself show that a graph is a five-cycle. We must check that the edges connect the vertices in one cycle, with no extra or missing edge. In the displayed edge set, the following order uses consecutive edges:
Proof. The five vertices \(a,b,a',z,b'\) are distinct. The consecutive pairs in the closed sequence \(a,b,a',z,b',a\) give, in order, the edges \(ab\), \(ba'\), \(a'z\), \(zb'\), and \(b'a\). These are precisely the five edges in \(E(M(G))\), with \(ba'=a'b\) and \(b'a=ab'\) because the graph is undirected. Thus the sequence is a cycle of length five. It visits every vertex exactly once before returning to \(a\), and the edge list contains no edges beyond those five cycle edges. Hence the graph is exactly \(C_5\). \(\square\)
Worked Example: Checking by Degrees and Edge Count
Use \(V=\{a,b,a',b',z\}\) and \(E=\{ab,ab',a'b,za',zb'\}\). List the neighbors of every vertex directly from the edge set:
- \(a\) is adjacent to \(b\) and \(b'\), so \(\deg(a)=2\).
- \(b\) is adjacent to \(a\) and \(a'\), so \(\deg(b)=2\).
- \(a'\) is adjacent to \(b\) and \(z\), so \(\deg(a')=2\).
- \(b'\) is adjacent to \(a\) and \(z\), so \(\deg(b')=2\).
- \(z\) is adjacent to \(a'\) and \(b'\), so \(\deg(z)=2\).
Each vertex has degree two, and the previously listed order \(a,b,a',z,b',a\) connects all five vertices. As a separate count check, the sum of the degrees is \(2+2+2+2+2=10\). Each edge contributes one to the degree of each endpoint, so the edge count is \(10/2=5\), matching the explicit edge list. This check confirms the count; the cycle order confirms that all five vertices lie in one cycle.
A Coloring Check
Since the construction has produced \(C_5\), its coloring can also be checked directly. 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 of \(G\).
Worked Example: Finding the Chromatic Number
For \(M(K_2)\), use the explicit edge set \(\{ab,ab',a'b,za',zb'\}\). A proper coloring with three colors is given by
Check the edges one by one: \(ab\) has colors \(1,2\); \(ab'\) has \(1,3\); \(a'b\) has \(1,2\); \(za'\) has \(2,1\); and \(zb'\) has \(2,3\). Each edge has differently colored endpoints, so \(\chi(M(K_2))\leq 3\).
Two colors cannot suffice. Along the cycle order \(a,b,a',z,b'\), a proper two-coloring would have to alternate. If \(a\) receives one color, then \(b\) receives the other, \(a'\) receives the color of \(a\), \(z\) receives the color of \(b\), and \(b'\) receives the color of \(a\). But \(b'a\) is an edge, so its endpoints would have the same color, a contradiction. Thus \(\chi(M(K_2))\geq 3\), and the two bounds give \(\chi(M(K_2))=3\).
Check: the coloring uses three colors, and the edge \(b'a\) rules out every two-color assignment by the alternation argument. Therefore the computed value is exactly \(3\).
Common Mistake: Adding Only One Cross-Edge
For each original edge, the construction requires two cross-edges, not one. With \(V=\{a,b,a',b',z\}\), a mistaken list that adds \(ab'\) but omits \(a'b\) is \(\{ab,ab',za',zb'\}\). It has only four edges. Its degrees, in the order \(a,b,a',b',z\), are \(2,1,1,2,2\), whose sum is \(8\); dividing by two gives four edges, confirming the list’s count. In particular, this mistaken graph is not a five-cycle.
The correction is to process the original edge \(ab\) in both directions: add \(ab'\) and \(a'b\). Then the full edge list is \(\{ab,ab',a'b,za',zb'\}\), with five edges. Each vertex has degree two, and the cycle order is \(a,b,a',z,b',a\). Keeping the edge types separate is a reliable way to avoid this omission: retain original edges, add two cross-edges per original edge, then join the apex to every shadow.
The same care prevents a different error: joining the apex to the original vertices instead of to the shadows. In this construction the apex edges are exactly \(za'\) and \(zb'\). The original vertices \(a\) and \(b\) are not adjacent to \(z\).
Check Your Understanding
Use the definition and the explicit edge-list method to answer the following.
- For \(K_2\) with vertices \(1,2\) and edge \(12\), name the two cross-edges and the two apex edges in \(M(K_2)\).
- Write the five vertices in an order that traces the cycle in \(M(K_2)\), returning to the starting vertex.
- Use the degree sum to verify that the five vertices of \(M(K_2)\), each of degree two, give five edges.
- Why does adding only one cross-edge for the original edge fail to produce the Mycielski graph of \(K_2\)?
- Give a proper three-coloring of \(M(K_2)\), and explain why two colors cannot suffice.