Why Mycielski Graphs Preserve Triangle-Freeness

The Construction and the Question

The Mycielski construction changes a graph by adding a shadow of each original vertex and one additional vertex. It preserves triangle-freeness: if the original graph has no triangle, the constructed graph has none either. The key is to check all possible ways a triangle might use the new types of vertices. The new edges connect originals to shadows and the additional vertex to shadows, but they do not connect two shadows.

All graphs in this tutorial are finite and simple: they have no loops or multiple edges. A triangle is a set of three distinct vertices such that each pair is joined by an edge. A graph is triangle-free if it contains no triangle.

Definition: Let \(G=(V,E)\), with \(V=\{v_1,\dots,v_n\}\). Its Mycielski graph \(M(G)\) has the original vertices \(v_1,\dots,v_n\), one shadow vertex \(u_i\) for each \(v_i\), and one new vertex \(w\). Its edges are:

the original edges \(v_iv_j\in E\);
the edges \(u_iv_j\) and \(u_jv_i\) for every original edge \(v_iv_j\in E\);
the edges \(wu_i\) for all \(i\).

There are no other edges. In particular, there are no edges between two shadows and no edges from \(w\) to an original vertex.

The original graph is retained as a subgraph of \(M(G)\). A shadow \(u_i\) is adjacent to exactly the original vertices that were adjacent to \(v_i\), and to \(w\). It is not adjacent to its own original vertex \(v_i\), because \(G\) has no loop at \(v_i\). If \(G\) has no vertices, the construction produces the one-vertex graph \(\{w\}\), which is triangle-free.

Classifying the Possible Triangles

First consider a triangle containing \(w\). The only neighbors of \(w\) are shadows, but no two shadows are adjacent. A triangle containing \(w\) would require two adjacent neighbors of \(w\), so no such triangle exists.

Now consider a triangle not containing \(w\). Its vertices must be originals or shadows. There are three possible numbers of original vertices:

Three originals: all three required edges are original edges, so these vertices form a triangle in \(G\).
Two originals and one shadow: write the originals as \(v_j,v_k\) and the shadow as \(u_i\). The edge \(v_jv_k\) must belong to \(E\). The edges from \(u_i\) to the two originals exist only if \(v_iv_j\) and \(v_iv_k\) belong to \(E\). Since \(u_i\) is not adjacent to \(v_i\), the indices \(i,j,k\) must be distinct. Thus \(v_i,v_j,v_k\) form a triangle in \(G\).
One or zero originals: at least two of the vertices would be shadows. Since there are no edges between shadows, these vertices cannot form a triangle.

This classification accounts for every triangle: it either contains \(w\), or it does not; without \(w\), it has three, two, one or zero original vertices. In the only cases where the required edges could exist, a triangle in \(M(G)\) would force a triangle in \(G\).

Theorem: For every finite simple graph \(G\), the Mycielski graph \(M(G)\) is triangle-free if and only if \(G\) is triangle-free.

Proof. First suppose \(G\) is triangle-free. A triangle in \(M(G)\) cannot contain \(w\), because \(w\)'s neighbors are pairwise nonadjacent shadows. If it contains no \(w\), the classification shows that it either would consist of three originals forming a triangle in \(G\), or would consist of two originals and a shadow whose required edges also give a triangle in \(G\). The other cases cannot be triangles because they contain two shadows. Each possibility contradicts triangle-freeness of \(G\). Thus \(M(G)\) is triangle-free.

Conversely, suppose \(M(G)\) is triangle-free. Every edge of \(G\) remains an edge between original vertices in \(M(G)\). Therefore, any triangle in \(G\) would also be a triangle in \(M(G)\). There can be no triangle in \(G\), so \(G\) is triangle-free. This proves both directions. \(\square\)

Worked Constructions

Worked Example: Applying the Construction to a Three-Vertex Path

Let \(G=(V,E)\) have \(V=\{a,b,c\}\) and \(E=\{ab,bc\}\). The graph is triangle-free: the only edges are \(ab\) and \(bc\), and the pair \(a,c\) is not adjacent.

Introduce shadows \(a',b',c'\) and the new vertex \(w\). Retain the original edges \(ab,bc\). From \(ab\), add \(a'b\) and \(b'a\); from \(bc\), add \(b'c\) and \(c'b\). Finally, add \(wa',wb',wc'\). Thus \(M(G)\) has vertex set \(\{a,b,c,a',b',c',w\}\) and edge set \(\{ab,bc,a'b,b'a,b'c,c'b,wa',wb',wc'\}\).

The number of edges is \(2+2(2)+3=9\): two original edges, two shadow-to-original edges per original edge, and three edges from \(w\). Independently, the degrees in the displayed graph are \(2,4,2,2,3,2,3\), in the vertex order \(a,b,c,a',b',c',w\). Their sum is \(18\), so the number of edges is \(18/2=9\), as required by the handshake lemma.

Check: the original path has no triangle. A triangle using \(w\) would need an edge between two shadows, but none is present. Without \(w\), any triangle with two originals and one shadow would require the three corresponding original edges, while three originals would also require a triangle in the path. Neither is possible. This agrees with the theorem.

Worked Example: Applying the Construction to a Four-Cycle

Let \(G=(V,E)\) have \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,cd,da\}\). This is a cycle of length four. It has no triangle: each vertex has exactly two neighbors, and those two neighbors are not adjacent to each other.

Add shadows \(a',b',c',d'\) and \(w\). The original edges are \(ab,bc,cd,da\). The edges created from these four edges are, respectively, \(a'b,b'a\); \(b'c,c'b\); \(c'd,d'c\); and \(d'a,a'd\). Add \(wa',wb',wc',wd'\). Therefore \(M(G)\) has vertex set \(\{a,b,c,d,a',b',c',d',w\}\) and edge set \(\{ab,bc,cd,da,a'b,b'a,b'c,c'b,c'd,d'c,d'a,a'd,wa',wb',wc',wd'\}\).

The edge count from the construction is \(4+2(4)+4=16\). As an independent check, each original vertex has degree \(4\): two original neighbors and two neighboring shadows. Each shadow has degree \(3\): two neighboring originals and \(w\). The vertex \(w\) has degree \(4\). The degree sum is \(4\cdot4+4\cdot3+4=32\), which gives \(32/2=16\) edges.

Check: the only possible triangle with two originals and one shadow would require three original edges forming a triangle. The four-cycle has no such triple. A triangle with \(w\) is impossible because the shadows have no edges between them, and a triangle with fewer than two originals and without \(w\) is impossible for the same reason. Thus the constructed graph is triangle-free.

Worked Example: An Isolated Vertex and Its Shadow

Let \(G=(V,E)\) have \(V=\{p,q,r\}\) and \(E=\{pq\}\). The graph consists of one edge and an isolated vertex \(r\), so it is triangle-free. Add \(p',q',r'\) and \(w\). The original edge is \(pq\); it creates \(p'q\) and \(q'p\); the new vertex is joined to every shadow. Hence \(M(G)\) has vertex set \(\{p,q,r,p',q',r',w\}\) and edge set \(\{pq,p'q,q'p,wp',wq',wr'\}\).

The edge count is \(1+2(1)+3=6\). For an independent check, the degrees in the order \(p,q,r,p',q',r',w\) are \(2,2,0,2,2,1,3\). Their sum is \(12\), giving \(12/2=6\) edges. The isolated original \(r\) remains isolated, while its shadow \(r'\) is adjacent to \(w\).

Check: there are only two original vertices that are incident with any edges, so no triangle can consist of three originals. A triangle with two originals and a shadow would require three original edges, which do not exist. The remaining cases require two adjacent shadows, and there is no such edge. In particular, the new edge \(wr'\) does not create a triangle: \(r'\) has no other neighbor.

Why the Case Analysis Matters

The construction adds many edges, so it is not enough to observe that the original graph had no triangles and assume the new graph remains triangle-free. The new edges could, in principle, complete a triangle. The proof rules this out by checking which vertex types each triangle would have to use, then translating the required edges back to the original graph.

This type of reasoning is useful whenever a graph is built from several classes of vertices. Rather than inspect every triple individually, identify which pairs of types can be adjacent and rule out each possible combination. Here the absence of shadow-to-shadow edges rules out several cases at once, and the remaining case translates directly into a forbidden triangle in \(G\).

Common Mistake

Wrong calculation: in the construction from the path \(a,b,c\), one might list \(a'b'\) as an edge because both \(a'\) and \(b'\) are shadows of adjacent original vertices. Then \(w,a',b'\) would appear to form a triangle.

Correction: an original edge creates edges from each endpoint's shadow to the other original vertex. From \(ab\), the added edges are \(a'b\) and \(b'a\), not \(a'b'\). The construction contains no edges between shadows. Although \(w\) is adjacent to both \(a'\) and \(b'\), those two vertices are not adjacent, so they cannot complete a triangle with \(w\).

Check Your Understanding

Use the definition of \(M(G)\) and the triangle classification to answer these questions.

Let \(G\) have \(V=\{x,y,z\}\) and \(E=\{xy,yz\}\). List all edges added from \(xy\), from \(yz\), and from the new vertex.
Why can a triangle in \(M(G)\) not contain \(w\), regardless of whether \(G\) is triangle-free?
If a triangle in \(M(G)\) contains exactly two originals and one shadow, which three edges must exist in \(G\)?
Suppose \(G\) contains a triangle. Explain why that same triangle remains in \(M(G)\).
Let \(G\) have \(V=\{x,y\}\) and \(E=\varnothing\). Write the vertex and edge sets of \(M(G)\), and explain why it is triangle-free.