Mycielski's construction

In the world of graph theory, some of the most profound insights come from simple, elegant constructions that challenge our fundamental intuitions. One such tool is Mycielski's construction, a clever procedure for expanding a graph. Its significance lies in its paradoxical outcome: it makes a graph more complex to color, yet it avoids creating the dense, interconnected clusters one might expect to be the cause. This article addresses the classic problem of separating a graph's chromatic number (its coloring requirement) from its clique number (the size of its largest complete subgraph).

This exploration is divided into two main parts. First, in "Principles and Mechanisms," we will delve into the blueprint of the construction itself. We'll unpack the step-by-step process of duplicating vertices and weaving new connections, examine its quantitative impact on graph size, and walk through the logical proofs that reveal its core magic: increasing the chromatic number by one while keeping the graph triangle-free. Following this, the "Applications and Interdisciplinary Connections" section will broaden our perspective. We will see how this construction serves as a powerful tool for generating counterexamples, how it interacts with other critical graph properties like planarity and regularity, and how its influence extends into advanced topics like list coloring and spectral graph theory, bridging abstract concepts to fields like computer science and physics.

Imagine you are a builder, but instead of using bricks and mortar, you work with nodes and connections—the vertices and edges of a graph. You have a simple structure, say a network of friends, and you want to make it more complex in a very specific, almost mischievous way. You want to increase its "coloring complexity"—the minimum number of colors needed so no two connected friends have the same color—without creating any tight-knit, three-person-cliques, or triangles. How would you do it? This is precisely the puzzle that the Polish mathematician Jan Mycielski solved with his beautifully clever construction.

Let's unpack this process, not as a dry recipe, but as a blueprint for sophisticated architectural expansion.

Mycielski's construction begins with an existing graph, let's call it $G$. Think of $G$ as the "foundation" of our new structure. The process unfolds in a few logical steps:

1. ​​Duplicate and Elevate:​​ For every vertex $v$ in your original foundation $G$, you create a "shadow" copy, which we'll call $u$. This gives us a whole new set of vertices, $U$, floating above the original set $V$. Then, you add a single, special vertex, $w$, which we can call the "apex" or "pinnacle," positioned to oversee the entire new layer. So, our new graph, $\mu(G)$, now has three kinds of vertices: the original 'foundation' vertices in $V$, the new 'shadow' vertices in $U$, and the lone apex $w$.

2. ​​Inherit and Weave:​​ The new structure must be connected to the old.

   • First, all the original connections (edges) in the foundation $G$ remain. The old structure is preserved.
   • Next comes the crucial weaving step. How do you connect the shadow layer $U$ to the foundation $V$? Here is the ingenious rule: a shadow vertex $u_i$ is connected to all the neighbors of its original counterpart $v_i$. Notice that $u_i$ is not connected to $v_i$ itself. It's as if your professional profile ($u_i$) is linked not to you, but to all your personal friends (the neighbors of $v_i$). This rule is the secret sauce of the whole construction.
   • Finally, the apex $w$ establishes its command. It connects to every shadow vertex in the set $U$, but to none of the original vertices in $V$. The apex can only see the new scaffolding, not the original foundation.

This set of rules gives us a new, much larger graph. For instance, if you start with a simple path of three vertices, $P_3$, which is just $v_1-v_2-v_3$, applying the construction results in a new graph with $2 \times 3 + 1 = 7$ vertices. Its chromatic number jumps from 2 to 3, as you can discover by trying to color it yourself.

This construction isn't just adding a few bits and pieces; it triggers a significant growth spurt. Let's quantify it. If our original graph $G$ has $n$ vertices and $m$ edges, the new graph $\mu(G)$ will have:

• ​​Vertices:​​ $n$ (original) + $n$ (shadows) + $1$ (apex) = $2n+1$ vertices.
• ​​Edges:​​ $m$ (original) + $2m$ (from the weaving rule) + $n$ (from the apex) = $3m+n$ edges.

Why $2m$ new edges from the weaving rule? The handshaking lemma tells us that the sum of degrees in a graph is $2m$. Each edge $(v_i, v_j)$ in $G$ means $v_j$ is a neighbor of $v_i$, and $v_i$ is a neighbor of $v_j$. The construction rule adds edges $(u_i, v_j)$ and $(u_j, v_i)$. So, for every original edge, we add two new "cross" edges.

The iterative application of this process leads to an explosion in size. The famous sequence of Mycielski graphs starts with $G_2 = K_2$ (a single edge, with 2 vertices and 1 edge).

• Applying the construction gives $G_3 = \mu(K_2)$, which turns out to be the 5-cycle, $C_5$. It has $n=2(2)+1=5$ vertices and $m=3(1)+2=5$ edges.
• Applying it again gives $G_4 = \mu(C_5)$, a graph known as the Grötzsch graph. It has $n=2(5)+1=11$ vertices and $m=3(5)+5=20$ edges,. In just two steps, we've gone from a simple line to a complex network of 11 nodes and 20 connections.

The changes are also reflected in the local neighborhood of each vertex. The degree of an original vertex $v_i$ exactly doubles in the new graph. The degree of a shadow vertex $u_i$ becomes one more than the degree of its original counterpart $v_i$. And the apex $w$, connecting to all $n$ shadow vertices, has a degree of exactly $n$.

Here we arrive at the heart of the matter, the paradox that makes this construction so fascinating. The graphs get bigger and harder to color, yet they remain just as "sparse" locally as they were before, in the sense that we don't create any new triangles.

Keeping it Triangle-Free

Let’s say we start with a graph $G$ that is triangle-free. Why is $\mu(G)$ also guaranteed to be triangle-free? We can convince ourselves with a simple argument. A triangle is a cycle of three vertices. If a new triangle were formed, it must involve at least one of the new vertices from $U$ or $w$. Let's check the possibilities:

• Could the triangle involve the apex $w$? No. The neighbors of $w$ are all in the set $U$. But by construction, there are no edges between any vertices in $U$, so no two neighbors of $w$ are connected.
• Could the triangle involve two shadow vertices, say $u_i$ and $u_j$? No, for the same reason. The set $U$ is an independent set.
• The only remaining possibility is a triangle with one shadow vertex, $u_i$, and two original vertices, $v_j$ and $v_k$. For this to be a triangle, $(v_j, v_k)$ must be an edge, and $u_i$ must be connected to both $v_j$ and $v_k$. But the construction rule says $u_i$ is connected to the neighbors of $v_i$. So, for $(u_i, v_j)$ and $(u_i, v_k)$ to be edges, both $v_j$ and $v_k$ must be neighbors of $v_i$. But if that's the case, then the vertices $\{v_i, v_j, v_k\}$ form a triangle back in the original graph $G$!

So, we've found that a new triangle can appear in $\mu(G)$ only if a triangle already existed in $G$. If you start clean, you stay clean. This insight can be stated more generally: the size of the largest clique (a set of mutually connected vertices) in the new graph is simply the maximum of 2 and the clique number of the old graph, $\omega(\mu(G)) = \max(2, \omega(G))$. The construction never creates a $K_3$ (a triangle) on its own. It does, however, readily create 4-cycles, so the girth (the length of the shortest cycle) of the new graph is often 4.

The Inevitable Color Increase

Now for the magic trick. Even though we aren't creating any new triangles, the chromatic number, $\chi(G)$, is guaranteed to increase by exactly one. That is, $\chi(\mu(G)) = \chi(G)+1$.

Why must we need one extra color? The proof is a beautiful argument by contradiction, a kind of logical judo. Let's say the chromatic number of our original graph $G$ is $k$ (so $\chi(G)=k$). Now, suppose, for the sake of argument, that we could get away with coloring the larger graph $\mu(G)$ with just $k$ colors.

Let's pick one of these hypothetical $k$-colorings for $\mu(G)$. The apex $w$ has some color, let's call it "Color #$k$". Since $w$ is connected to all the shadow vertices $u_i$, none of them can be colored with Color #$k$. They must all be colored using the first $k-1$ colors.

Now, here is the brilliant move. Let's use this coloring of $\mu(G)$ to try and create a new coloring for the original, smaller graph $G$.

• For any vertex $v_i$ in $G$ whose color in the $\mu(G)$ coloring was not Color #$k$, we'll just keep its color.
• For any vertex $v_j$ in $G$ that was assigned Color #$k$, we'll change its color. What will we change it to? We'll give it the color of its corresponding shadow vertex, $u_j$. We know for sure this color is not Color #$k$.

We have just defined a new coloring for all the vertices in $G$. And this new coloring only uses the first $k-1$ colors! But is it a valid coloring? Let's check any two adjacent vertices in $G$, say $v_i$ and $v_j$.

• If neither was originally Color #$k$, their colors are unchanged and were different to begin with, so they are still different.
• What if one, say $v_i$, was Color #$k$, and the other, $v_j$, was not? The new color of $v_i$ is the color of its shadow, $c(u_i)$. The new color of $v_j$ is its old color, $c(v_j)$. Are these two colors different? Yes! Because $(v_i, v_j)$ is an edge in $G$, the construction dictates there must be an edge $(u_i, v_j)$ in $\mu(G)$. Since our coloring of $\mu(G)$ was assumed to be valid, the colors of $u_i$ and $v_j$ must be different.

So, our new coloring for $G$ is perfectly valid, and it only uses $k-1$ colors. But this is impossible! We started from the fact that $G$ is a $k$-chromatic graph, meaning the minimum number of colors it requires is $k$. Our assumption—that $\mu(G)$ could be colored with $k$ colors—has led us to a logical absurdity. Therefore, that assumption must be false. The graph $\mu(G)$ must require at least $k+1$ colors.

To complete the picture, we can easily show that $k+1$ colors are sufficient. We can take a valid $k$-coloring of $G$, assign each shadow vertex $u_i$ the same color as its original $v_i$, and then assign the apex $w$ a brand new $(k+1)$-th color. This coloring scheme works perfectly.

Thus, the conclusion is inescapable: $\chi(\mu(G)) = \chi(G)+1$. The construction is a veritable machine for cranking up the chromatic number, one step at a time, providing a definitive and constructive proof that graphs can require an arbitrarily large number of colors even without containing a single triangle. This resolves a fundamental question in graph theory, not with an abstract theorem, but with a blueprint you can follow yourself.

Now that we have grappled with the gears and levers of the Mycielski construction, we can step back and ask the most important question a scientist or mathematician can ask: "What is it good for?" To simply have a recipe for making larger graphs is a fine thing, but the true beauty of a mathematical tool lies in the new worlds it opens up, the stubborn questions it helps us answer, and the unexpected bridges it builds between seemingly distant ideas. Mycielski's construction is not just a curiosity; it is a lens, a prism that separates the properties of graphs in surprising ways, and a powerful engine for exploration.

Perhaps the most celebrated application of Mycielski's construction is in its original role: to build mathematical "monsters." In mathematics, a monster, or counterexample, is often more valuable than a dozen proofs of expected results. It's the thing that doesn't fit, the object that challenges our intuition and forces us to refine our theories.

A very natural, almost common-sense, intuition about graph coloring is that to need many colors, a graph must have a large, densely interconnected "clique"—a group of vertices all mutually connected. A graph with a $K_k$ (a complete graph on $k$ vertices) as a subgraph certainly needs at least $k$ colors. But is the reverse true? Must a graph with a high chromatic number contain a large clique?

For decades, this was a central question. Mycielski's construction provides a stunningly elegant "no." Starting with the simple edge graph $K_2$, which has chromatic number 2 and clique number 2, we can apply the construction iteratively. The resulting graph, $\mu(K_2)$, is the 5-cycle, $C_5$. It has no triangles (its clique number is still 2), but its chromatic number has jumped to 3. If we apply the construction again, we get a graph with chromatic number 4, still with no triangles. This process can be continued indefinitely, giving us a family of graphs where the chromatic number can be arbitrarily large, even though the largest clique is, and always will be, a single edge ($K_2$).

The magic lies in how the construction introduces "oddness" into the graph. When applied to a triangle-free graph, it cleverly avoids creating any new triangles. However, it does create new cycles, and specifically, it can introduce a 5-cycle where none existed before. This new odd cycle—for example, the 5-cycle $v_i - v_j - u_i - w - u_j - v_i$ created from an edge $(v_i, v_j)$—is what drives the chromatic number up, even without creating dense cliques. These newly formed 5-cycles are often "induced," meaning they have no pesky shortcuts or "chords". The existence of such an induced odd cycle (an "odd hole") is a profound structural property, certifying that the graph is not a "perfect graph"—a well-behaved class of graphs where the chromatic number is always determined by the size of the largest clique for every induced subgraph. Mycielski's construction, therefore, is a veritable factory for generating graphs that are beautifully, stubbornly imperfect.

Once we have a tool that modifies a graph, a natural line of inquiry is to see how it interacts with other fundamental properties. Does it preserve them? Destroy them? Transform them in predictable ways? The answers reveal the construction's unique "personality."

Imagine trying to build a complex, layered network. You might be concerned with keeping it "simple" in some sense. For instance, can it still be drawn on a piece of paper without any edges crossing? This is the property of planarity. The Mycielski construction, with its profusion of new edges, tends to quickly destroy planarity. While the Mycielskian of a simple path graph like $P_4$ can, with some care, be drawn flat, the construction applied to even a simple 4-cycle $C_4$ already produces a non-planar graph. The construction's tendency to double up connections makes it fundamentally three-dimensional in spirit.

What about a property like regularity, where every node in a network has the same number of connections? This kind of balance is often desirable. However, the Mycielski construction is an inherently unbalancing operation. The original vertices, their new "shadow" counterparts, and the universal apex vertex all end up with different degree calculations. It turns out that this balance can almost never be maintained. In fact, the only non-empty regular graph whose Mycielskian is also regular is the simplest one of all: a single edge, $K_2$. This striking result shows that the construction's growth pattern is fundamentally asymmetric.

The construction's impact extends to properties crucial in computer science and network optimization. Consider the ​​vertex cover problem​​: finding the smallest set of vertices to "guard" all edges in a graph. This is related to the ​​independence number​​, the largest set of vertices with no edges between them. The Mycielski construction transforms these properties in a fascinating, recursive way. For the sequence of graphs starting with $G_0=K_2$ and defined by $G_{k+1}=\mu(G_k)$, one can precisely track the growth of the independence and vertex cover numbers, revealing a deep structural relationship between the size of a graph and the independence number of its predecessor.

Similarly, in network security or logistics, we often want to find a minimal ​​dominating set​​—a small set of nodes from which all other nodes can be reached in one step. How does the size of this set, the dominating number $\gamma(G)$, change when we expand the network using the Mycielski construction? It turns out that $\gamma(\mu(G))$ is intimately linked not just to $\gamma(G)$, but to a related concept called the total dominating number of $G$. This reveals a subtle but powerful predictive link between the properties of a network before and after this complex expansion.

The richness of the Mycielski construction is not limited to just the chromatic number. It also informs our understanding of more nuanced aspects of graph coloring.

Instead of just asking if a graph can be colored with $k$ colors, we can ask how many ways it can be done. This count, as a function of $k$, is a polynomial known as the chromatic polynomial. Applying the construction to even a simple path like $P_3$ results in a graph whose chromatic polynomial is significantly more complex, a testament to the intricate web of new constraints the construction introduces.

A more robust and practical model of coloring is ​​list coloring​​. Imagine that instead of having a common pool of colors, each vertex has its own specific list of permissible colors. The choice number, $\text{ch}(G)$, is the minimum list size $k$ required to guarantee a valid coloring, no matter what the lists contain. This is a much stronger condition than standard coloring. Remarkably, the elegant property of the Mycielski construction holds even for this stronger type of coloring in many important cases. For a complete graph $K_k$, where $\chi(K_k) = \text{ch}(K_k) = k$, its Mycielskian also has a choice number of exactly $k+1$. The "+1" property is not a fluke of simple coloring but reflects a deeper structural change that persists under more stringent conditions. By studying variations of the construction, for instance by changing which vertices the apex $w$ connects to, we can probe exactly which components of the construction are essential for this chromatic number increase, refining our understanding of the underlying mechanism.

Perhaps the most profound interdisciplinary connection is to the field of ​​spectral graph theory​​, which bridges graph theory with linear algebra and has deep ties to physics and computer science. One can represent a graph as a matrix, such as the Laplacian matrix, and study its eigenvalues (its "spectrum"). These eigenvalues correspond to the vibrational modes of the network; they tell a story about the graph's connectivity, its bottlenecks, and its overall shape.

The second-smallest Laplacian eigenvalue, $\lambda_2$, is famously known as the algebraic connectivity. It measures how well-connected the graph is—a higher $\lambda_2$ implies a more robust and harder-to-break-apart network. What happens to the spectrum when we apply the Mycielski construction?

For a highly symmetric graph like the complete graph $K_n$, the incredible happens. The symmetries of the construction—the three distinct classes of vertices (original, shadow, and apex)—allow us to decompose the massive Laplacian matrix of $\mu(K_n)$ into small, manageable blocks. By analyzing these blocks, we can precisely calculate the entire spectrum of the new graph. This allows us to determine the new algebraic connectivity, revealing exactly how the graph's robustness has been altered by the construction. This is a beautiful instance of symmetry simplifying a complex problem, a principle that lies at the heart of physics. The geometric act of constructing the Mycielskian is mirrored perfectly in the algebraic structure of its spectrum, a testament to the profound unity of mathematics.

In the end, Mycielski's construction is far more than a clever trick. It is a fundamental tool for the curious mind, a gateway to understanding the intricate dance between local structure and global properties, and a shining example of how a simple idea can ripple outwards, connecting diverse fields of science and deepening our appreciation for the hidden architecture of the world.