The Mycielski Construction from Vertex and Edge Lists

From an Input List to a New Graph

The Mycielski construction transforms a finite simple graph into a larger graph by retaining its original vertices and edges, adding one shadow for each original vertex, and adding one new vertex. Its edge list is determined entirely by the input edge list: each input edge creates two edges between original and shadow vertices, and the new vertex is joined to every shadow. Careful labels help keep these edge types separate.

Throughout, the input graph $G=(V,E)$ is finite and simple: it has no loops or multiple edges. Write its vertices as $V=\{v_1,\ldots,v_n\}$, with $n=|V|$, and its edges as unordered pairs $v_iv_j$. The notation $v_i'$ will denote the shadow of $v_i$. Treat all shadows as new labels, distinct from the original vertices, and let $z$ be another new vertex, distinct from both sets.

Definition: The Mycielski graph $M(G)$ has vertex set $$ V(M(G))=V\cup V'\cup\{z\},\qquad V'=\{v_1',\ldots,v_n'\}, $$ where $V$, $V'$, and $\{z\}$ are pairwise disjoint. Its edge set consists of:

every original edge $v_iv_j\in E$;
the two edges $v_iv_j'$ and $v_jv_i'$ for each original edge $v_iv_j\in E$;
the edge $zv_i'$ for each $v_i\in V$.

There are no other edges.

In particular, the construction does not join two shadows to each other, does not join $z$ to an original vertex, and does not join a vertex to its own shadow unless that edge is produced by some other listed rule. In a simple input graph, there is no original edge $v_iv_i$, so the rules never produce an edge $v_iv_i'$.

A Reliable Procedure for Writing the Lists

For an input specified by its vertex and edge lists, use the following procedure. It keeps the three kinds of edges separate so that none are omitted or accidentally added twice.

Copy the vertices.
Write down the original vertex list, a shadow copy of every entry, and the new vertex $z$. Use distinct labels for the three groups.

Retain the original edges.
Copy every edge in $E$ unchanged into $E(M(G))$.

Translate each input edge.
For each $v_iv_j\in E$, write both $v_iv_j'$ and $v_jv_i'$. The endpoints switch roles: each original endpoint is joined to the other endpoint’s shadow.

Join the new vertex to the shadows.
For every original vertex $v_i$, add $zv_i'$. Do not add $zv_i$.

Check the lists.
Confirm that every input edge was translated twice and every vertex has exactly one corresponding edge to $z$ from its shadow.

For clarity, $v_iv_j'$ denotes the unordered edge with endpoints $v_i$ and $v_j'$. Because original vertices and shadows are disjoint, $v_iv_j'$ and $v_jv_i'$ are different edges, even though both come from the same input edge $v_iv_j$.

Theorem: If $G$ has $n$ vertices and $m$ edges, then $M(G)$ has $2n+1$ vertices and $3m+n$ edges. These formulas also hold for the graph with no vertices, where $M(G)$ consists of the single vertex $z$ and no edges.

Proof. The vertex groups $V$, $V'$, and $\{z\}$ are pairwise disjoint, and their sizes are $n$, $n$, and $1$, respectively. Therefore $|V(M(G))|=n+n+1=2n+1$. For the edge count, the construction retains $m$ original edges. Each of the $m$ input edges gives two original-to-shadow edges, for $2m$ edges of that type. Finally, there is one edge $zv_i'$ for each of the $n$ original vertices, giving $n$ edges of the third type. These categories are disjoint: their endpoints are, respectively, original-original, original-shadow, and new-vertex-shadow. Within the original-to-shadow category, no two generated edges coincide: an edge $v_iv_j'$ specifies the original pair $v_i,v_j$, and a simple graph has at most one edge for that pair. Thus the total is $m+2m+n=3m+n$. If $n=0$, then $E$ is empty and the construction has only $z$, so both formulas give the stated counts. $\square$

Worked Lists

Worked Example: Constructing from a Three-Vertex Path

Let $G=(V,E)$ have $V=\{1,2,3\}$ and $E=\{12,23\}$. We list each edge type separately.

The original vertices are $1,2,3$; their shadows are $1',2',3'$; and the new vertex is $z$. Hence $V(M(G))=\{1,2,3,1',2',3',z\}$.

Retain the original edges $12,23$. Translating $12$ gives $12'$ and $21'$; translating $23$ gives $23'$ and $32'$. The new-vertex edges are $z1',z2',z3'$. Therefore the complete edge list is $E(M(G))=\{12,23,12',21',23',32',z1',z2',z3'\}$.

Check: There are $2\cdot3+1=7$ vertices. The input has $m=2$ edges, so the edge-count formula gives $3\cdot2+3=9$ edges. The displayed list has two retained edges, four translated edges, and three edges incident with $z$, giving $2+4+3=9$.

Worked Example: Constructing from a Triangle

Let $G=(V,E)$ have $V=\{a,b,c\}$ and $E=\{ab,ac,bc\}$. Each of the three input edges contributes two original-to-shadow edges.

The vertex set is $V(M(G))=\{a,b,c,a',b',c',z\}$. The retained edges are $ab,ac,bc$. The edge $ab$ contributes $ab',ba'$; $ac$ contributes $ac',ca'$; and $bc$ contributes $bc',cb'$. Finally, add $za',zb',zc'$. Combining these lists gives $E(M(G))=\{ab,ac,bc,ab',ba',ac',ca',bc',cb',za',zb',zc'\}$.

Check: The input has $n=3$ and $m=3$, so the construction gives $2\cdot3+1=7$ vertices and $3\cdot3+3=12$ edges. In the displayed list, the three retained edges, six translated edges, and three edges from $z$ total $3+6+3=12$. The list contains both translated edges for each of $ab,ac,bc$.

Worked Example: An Isolated Vertex and Two Separate Edges

Let $G=(V,E)$ have $V=\{a,b,c,d,e\}$ and $E=\{ab,cd\}$. Thus $e$ is isolated in the input: no edge of $E$ contains $e$.

The output vertex set is $V(M(G))=\{a,b,c,d,e,a',b',c',d',e',z\}$. Retain $ab,cd$. Translate $ab$ to $ab',ba'$, and translate $cd$ to $cd',dc'$. The five edges incident with $z$ are $za',zb',zc',zd',ze'$. Thus $E(M(G))=\{ab,cd,ab',ba',cd',dc',za',zb',zc',zd',ze'\}$.

The original vertex $e$ has no incident edge in the output: it was isolated and is not joined to $z$. Its shadow $e'$, however, is joined to $z$, as required for every shadow. Check: Here $n=5$ and $m=2$, so the output has $2\cdot5+1=11$ vertices and $3\cdot2+5=11$ edges. The list has two retained edges, four translated edges, and five edges from $z$, giving $2+4+5=11$.

Degree Checks

The lists also determine the degrees of all three vertex types. The formulas below are useful for checking a constructed graph, especially when the input includes vertices of different degrees.

Theorem: For each original vertex $v_i$ of $G$, its degrees in the Mycielski graph satisfy $$ \deg_{M(G)}(v_i)=2\deg_G(v_i),\qquad \deg_{M(G)}(v_i')=\deg_G(v_i)+1,\qquad \deg_{M(G)}(z)=n. $$

Proof. Fix an original vertex $v_i$. Its original neighbors contribute $\deg_G(v_i)$ retained edges incident with it. For each neighbor $v_j$ in $G$, the translated edge $v_iv_j'$ contributes one more incident edge. There are exactly $\deg_G(v_i)$ such neighbors, and no other construction rule adds an edge at $v_i$, so its output degree is $2\deg_G(v_i)$. The shadow $v_i'$ is joined to $v_j$ for each original neighbor $v_j$, giving $\deg_G(v_i)$ incident edges, and it is also joined to $z$. It has no other incident edges, so its degree is $\deg_G(v_i)+1$. Finally, $z$ is joined once to each of the $n$ distinct shadows and has no other neighbors, so its degree is $n$. This reasoning includes an isolated $v_i$: its output degree is $0$, its shadow’s degree is $1$, and the formula for $z$ still holds. $\square$

For the path example, the input degrees are $\deg_G(1)=1$, $\deg_G(2)=2$, and $\deg_G(3)=1$. The formulas give output degrees $2,4,2$ at $1,2,3$, degrees $2,3,2$ at $1',2',3'$, and degree $3$ at $z$. Their sum is $2+4+2+2+3+2+3=18$, which corresponds to $18/2=9$ edges because each edge has two endpoints. This agrees with the explicit edge list and the edge-count formula.

Common Mistakes and a Practical Check

A frequent error is to translate an input edge only one way. For example, from the input edge $12$, adding $12'$ but not $21'$ leaves out one of the two required original-to-shadow edges. The correction is to read the rule at both endpoints: $1$ is joined to the shadow of $2$, and $2$ is joined to the shadow of $1$. For the input $E=\{12,23\}$, these translated edges are exactly $12',21',23',32'$.

Another error is to join $z$ to the original vertices instead of to their shadows. The rule is $zv_i'$ for every original vertex $v_i$, not $zv_i$. A third is to add edges between shadows when none are specified. Check the output against the three edge categories in the definition, and use $3m+n$ as a count check. The count is a useful way to find omissions, although matching the count alone does not prove that the listed edges are correct.

The construction is a precise graph transformation: it specifies a new vertex set and every edge of the output without relying on a drawing. This list-based viewpoint makes examples reproducible and provides a basis for studying the properties of the resulting graphs. To construct an output correctly, keep original edges, translated edges, and edges from $z$ visibly separate until the final list is assembled.

Check Your Understanding

For each question, state enough of the vertex or edge list to justify your answer.

If $G$ has $n=4$ vertices and $m=3$ edges, how many vertices and edges does $M(G)$ have?
For an input edge $xy$, which two edges involving shadows are added?
Let $V=\{p,q,r\}$ and $E=\{pq\}$. Write the complete vertex and edge sets of $M(G)$.
If $v_i$ is isolated in $G$, what are the degrees of $v_i$ and $v_i'$ in $M(G)$?
Explain why the two translated edges from one input edge are distinct, and why different edge categories cannot overlap.