Graph Coloring Explorer

Drag vertices, draw edges, and color the graph by hand or with a greedy algorithm — watch the clique lower bound reveal how many colors you truly need.

Worked example — Graph Coloring Explorer

Vertices	3
Edges	3
Colors used	0
Conflicts	0

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

how many colors do you really need? 🖖

The chromatic number χ(G) is the minimum number of colors needed so that no edge joins two same-colored vertices. Finding it exactly is NP-hard — the best general guarantee sits between a clique lower bound (any clique of size k forces at least k colors) and a greedy upper bound (Welsh-Powell coloring by descending degree never uses more than Δ+1 colors, where Δ is the maximum degree). For planar graphs — those drawable without crossing edges — the four color theorem guarantees 4 colors always suffice; it was first proved by computer in 1976 and remains one of the few major theorems requiring exhaustive computer case-checking. Graph coloring underlies real scheduling problems: register allocation in compilers, exam timetabling, and radio frequency assignment all reduce to coloring a conflict graph.

neighbors must differ — that's the whole game 🖖

Graph coloring boils down to one rule: no edge may join two vertices of the same color, and you want to get by with as few colors as possible. That single constraint decides everything. A handy test: every cycle of even length can be done with 2 colors, but every cycle of odd length needs 3 — so a triangle (the smallest odd cycle) can never be 2-colored. Build both in the tool and watch the conflict count.

greedy coloring can fail spectacularly 🖖

Coloring vertices one at a time, always grabbing the lowest free color, feels safe — but the order you pick matters enormously. On a family called crown graphs — 2n vertices that need only 2 colors — a cruel ordering forces the greedy method to use n colors instead. Its worst case is unbounded, which is exactly why the tool's auto-color sorts vertices by descending degree (Welsh-Powell) to sidestep such traps.

Problems solved in full

The real chromatic number of the Petersen graph 5 steps
The Petersen graph has 10 vertices, 15 edges and no triangle. The panel therefore reports χ ≥ 2. Find the real chromatic number. This is the Petersen graph state.
1. Two bounds come free from any graph: it needs at least as many colours as its largest clique, and never more than one above its maximum degree.
  
  $ω (G) \leq χ (G) \leq Δ (G) + 1 : Petersen has ω = 2, Δ = 3 ⟹ 2 \leq χ \leq 4$
2. Petersen's girth is 5, so there is no triangle anywhere in it and the clique bound collapses to the trivial 2. That is the number the panel reports.
  
  $girth = 5 ⟹ no triangle ⟹ ω = 2, yet the graph is not bipartite$
3. Two colours are possible only when the graph is bipartite, and bipartite means no odd cycle. The outer pentagon is a 5-cycle, so two colours are out.
  
  $bipartite ⟺ no odd cycle; the outer 5-cycle is odd ⟹ χ \geq 3$
4. Three colours can be achieved, and exhibiting one arrangement is a complete proof of the upper half. Colour the outer pentagon 1, 2, 1, 2, 3 going round, then the five inner vertices 2, 1, 3, 3, 2 in the same order, each paired to the outer vertex on its own spoke. Walk all fifteen edges and no two ends match.
  
  $a 3-colouring exists ⟹ χ = 3, strictly above the clique bound ω = 2$
5. Brooks' theorem says the same thing from above: a connected graph that is neither complete nor an odd cycle needs at most Δ colours, and Δ is 3 here.
  
  $∣ V ∣ = 10, ∣ E ∣ = 15, Δ = 3 : Brooks’ theorem gives χ \leq 3 for a connected non-complete graph$
Answer

3, which is strictly above the bound the panel can prove. The largest clique in Petersen is a single edge, so the clique bound gives only χ ≥ 2, and it is wrong by one. The gap matters more than it looks: Petersen is the standard counterexample to the intuition that colouring difficulty comes from cliques, and there are triangle-free graphs needing four colours, five, any number you like — Mycielski's construction produces them to order. So the clique number is a lower bound that can be arbitrarily far off, which is why chromatic number is NP-hard while finding a triangle is not. What settles Petersen at exactly 3 is an odd cycle for the lower end and Brooks' theorem for the upper.

$χ (Petersen) = 3 > ω = 2 : the clique bound is not tight$
Comparing bounds for χ on the complete K4 graph 5 steps
Now K₄ — four vertices, all six edges present. Work out χ and compare the bounds with what they did on Petersen. This is the Complete K4 state.
1. Count the edges rather than trust the picture: every pair of four vertices is joined, and there are six pairs.
  
  $K_{4} : ∣ V ∣ = 4, ∣ E ∣ = (2 4) = 6, every pair adjacent$
2. Every vertex is adjacent to every other, so no two may share a colour. That is a lower bound of 4 and it needs no argument beyond the definition.
  
  $all four vertices are mutually adjacent ⟹ ω = 4 ⟹ χ \geq 4$
3. Four colours obviously suffice, so the bound is met. The same reasoning gives χ(Kₙ) = n for every n, which makes complete graphs the easy case.
  
  $four colours suffice trivially ⟹ χ (K_{n}) = n$
4. Set the two graphs side by side. Same question, same two bounds, and the gap between them is the whole subject.
  
  $here ω = χ = 4 : the bound is tight, and Petersen showed it need not be$
5. Note where Brooks' theorem stands here. Its bound of Δ = 3 would be wrong for K₄, which is why complete graphs are carved out of it by name.
  
  $Δ + 1 = 4 as well — Brooks’ theorem excludes complete graphs for exactly this reason$
Answer

4, and here every bound is tight at once. The clique number is 4 because the whole graph is a clique, Δ + 1 is 4 because every vertex meets the other three, and the true answer is squeezed between them with nowhere to go. That is the case people build their intuition on, and it is exactly the case Brooks' theorem excludes — his bound of Δ applies to every connected graph except complete graphs and odd cycles, and these two problems are the reason for both exceptions. Petersen and K₄ mark the two ends: one where the clique bound misses by one, one where it cannot miss at all.

$χ (K_{4}) = ω (K_{4}) = Δ + 1 = 4$

References (2)

Insight block 1 — the four colour theorem, and the computer proof it needed: K. Appel and W. Haken, "Every planar map is four colorable. Part I: Discharging." Illinois Journal of Mathematics 21(3), 429–490, 1977.
And the descending-degree ordering the auto-colour button uses: D. J. A. Welsh and M. B. Powell, "An upper bound for the chromatic number of a graph and its application to timetabling problems." The Computer Journal 10(1), 85–86, 1967.

By the 42Math team · Updated 2026-06-16

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Computing lessons →

Graph Coloring Explorer

how many colors do you really need? 🖖

neighbors must differ — that's the whole game 🖖

greedy coloring can fail spectacularly 🖖

Example problems