Mycielski graph

A Mycielski graph is a graph produced by the Mycielski construction, which raises the chromatic number by at least 1 while keeping the graph triangle-free. In Combinatorics, it is a standard example in vertex coloring problems.

What is Mycielski graph?

A Mycielski graph is a graph made from another graph using the Mycielski construction, a method designed to increase the chromatic number without creating triangles. In Combinatorics, this shows up in graph coloring as a way to build examples that are harder to color than they first look.

The idea is simple in spirit even if the wiring is a little tricky. Start with a graph G, then add a second copy of its vertices in a shifted form and one extra new vertex. The new edges are arranged so the old adjacency pattern is preserved in a controlled way, but the original vertices cannot all be recolored with the same number of colors as before.

The payoff is that if G has chromatic number k, the Mycielski graph built from it has chromatic number at least k + 1. That means every time you apply the construction, you force the coloring problem to need one more color. This is why Mycielski graphs are such a useful source of counterexamples in graph theory.

A famous feature is that the construction preserves triangle-free graphs. So if the original graph has no 3-cycles, the new graph also has no triangles, even though its chromatic number goes up. That combination surprises a lot of people at first, because it shows that having no triangles does not mean a graph is easy to color.

The classic starting point is K3, the complete graph on three vertices. Applying the Mycielski construction to K3 produces a triangle-free graph with chromatic number 4. Repeating the process gives infinite families of triangle-free graphs with arbitrarily large chromatic number, which is one reason the construction matters so much in extremal graph coloring.

Why Mycielski graph matters in COMBINATORICS

Mycielski graphs matter because they separate two ideas that students often want to tie together too tightly: small clique structure and chromatic number. A graph can have no triangles and still require many colors, so the Mycielski construction gives a clean example of that gap.

In graph coloring units, this is a go-to example when you need to see why local structure does not fully control coloring difficulty. A graph can look sparse, avoid triangles, and still resist a low-coloring scheme. That makes Mycielski graphs useful when discussing why chromatic number is a global property, not just a count of local patterns.

They also show up as counterexample material. If a claim sounds like "triangle-free graphs should be 2-colorable" or "low clique number means low chromatic number," the Mycielski family is the kind of construction that breaks the claim. You do not just memorize the result, you use it to test whether a coloring statement is actually true.

The construction is also a nice bridge between pure definitions and proof technique. It gives you a repeatable way to build new graphs from old ones, then track what happens to colors, adjacency, and forbidden subgraphs.

How Mycielski graph connects across the course

Chromatic number

The whole point of a Mycielski graph is that its chromatic number goes up after the construction. If you are asked to compare graphs by coloring difficulty, chromatic number is the value you track. Mycielski graphs are one of the cleanest examples showing that chromatic number can increase even when the graph still avoids triangles.

Vertex coloring

Mycielski graphs are built for vertex-coloring problems, where adjacent vertices cannot share a color. The construction creates new adjacency patterns that force an extra color, so it is a concrete example of why coloring rules can become stricter after adding vertices. It is a good test case for checking whether a proposed coloring really works.

Brooks' Theorem

Brooks' Theorem gives bounds on chromatic number for many connected graphs, but Mycielski graphs are useful when you want to see where simple-looking graphs still need many colors. Comparing the two helps you separate general upper-bound ideas from explicit constructions that push coloring upward. They address the same coloring landscape from different angles.

Greedy coloring algorithm

A greedy coloring algorithm can find a valid coloring, but it may use more colors than the chromatic number. Mycielski graphs are good examples for seeing how a naive coloring order can get stuck using extra colors. They make the difference between a valid coloring and a minimum coloring very visible.

Is Mycielski graph on the COMBINATORICS exam?

A problem set question may ask you to build a Mycielski graph from a given graph, identify its chromatic number, or explain why triangle-freeness is preserved. You may also be asked to use the construction as a counterexample to a false coloring claim. When you see a diagram, focus on the original vertices, the copied vertices, and the extra added vertex, then track which edges force the extra color. On proofs, the move is usually to show that any coloring of the new graph collapses to a coloring of the old one unless you add one more color. That is the whole engine behind the construction.

Key things to remember about Mycielski graph

• A Mycielski graph is built from another graph to increase chromatic number by at least one.

• The construction is especially useful because it can preserve triangle-freeness while making coloring harder.

• Mycielski graphs are a standard source of counterexamples in graph coloring theory.

• The construction can be repeated to produce triangle-free graphs with arbitrarily large chromatic number.

• When you study one, focus on how the added vertices force an extra color without creating triangles.

Frequently asked questions about Mycielski graph

What is a Mycielski graph in Combinatorics?

A Mycielski graph is a graph produced by the Mycielski construction, which turns one graph into another with higher chromatic number. In Combinatorics, it is used to show that a graph can stay triangle-free while still needing more colors.

How does the Mycielski construction increase chromatic number?

It adds new vertices and edges in a pattern that prevents you from reusing the old coloring without introducing another color. The construction is designed so the new graph cannot be properly colored with the same number of colors as the original graph.

Why are Mycielski graphs triangle-free?

The edges are arranged so that the new graph does not create any 3-cycles if the original graph had none. That is what makes the construction so useful, because it gives graphs with no triangles but still high chromatic number.

What is a simple example of a Mycielski graph?

A classic starting example comes from K3, the complete graph on three vertices. Applying the Mycielski construction gives a triangle-free graph with chromatic number 4, which is a good first example to study in a coloring problem.