Graph Colouring

Imagine you are running the exam timetable for a whole university. Two exams must never share a time slot if a single student is sitting both of them. Slots are expensive, so you want as few as possible. Draw a dot for every exam, and join two dots with a line whenever some student takes both — you have just built a graph. Now hand out time slots so that no two joined exams get the same slot. That is graph colouring, and the fewest slots you can get away with is the heart of this page.

The word "colour" is just a vivid name for the slots — a label, a frequency, a register, a shift. Colour the dots, keep neighbours different, use as few colours as possible. One idea, and it shows up everywhere.

Proper colourings and the chromatic number

A proper vertex colouring of a graph G assigns a colour to every vertex so that adjacent vertices always get different colours. (Vertices that share no edge may match freely — only neighbours are forced apart.)

The chromatic number \chi(G) is the smallest number of colours in any proper colouring of G.

So proving \chi(G) = k is really two jobs: an upper bound (show a colouring that works with k colours) and a lower bound (show that k-1 colours could never work). Exhibiting a colouring is the easy half; arguing that fewer is impossible is the interesting half.

The same idea, wearing four hats

Colouring is one of those ideas that quietly runs the world. Whenever things must be kept apart and a shared resource must be shared sparingly, you are colouring a graph:

A few graphs whose colour count we know exactly

Before hunting \chi in the wild, learn the landmarks. These four facts cover a surprising amount of ground:

Watch a colouring being built

Here is the pentagon A\!-\!B\!-\!C\!-\!D\!-\!E\!-\!A — a 5-cycle, and 5 is odd. Step through as the vertices are coloured one class at a time. Each new colour class is a set of vertices that share a colour; watch how the odd loop refuses to close on just two colours and demands a third.

Two colours would go red, green, red, green as you walk round — but after four steps you arrive back at A needing E to differ from both its red and green neighbours. Only a third colour escapes the trap. That is exactly why every odd cycle has \chi = 3.

Worked example: finding χ of the pentagon

Let us prove \chi = 3 for that 5-cycle properly — both halves of the argument.

Upper bound (3 is enough). The colouring you just watched uses three colours and keeps every pair of neighbours different. So \chi \le 3.

Lower bound (2 is not enough). Suppose only two colours were available. Start at A with colour 1. Then B must be colour 2, C colour 1, D colour 2, and E colour 1. But E is adjacent to A, which is also colour 1 — a clash. Two colours are impossible, so \chi \ge 3.

Both bounds meet: \chi(C_5) = 3. A quick way to find an upper bound in practice is the greedy algorithm: run through the vertices in some order, giving each the lowest-numbered colour not already used by a neighbour. It never uses more than \Delta + 1 colours (where \Delta is the largest number of neighbours any vertex has) — though it does not always hit the true minimum.

// Greedy colouring of the 5-cycle A-B-C-D-E-A. const vertices = ["A", "B", "C", "D", "E"]; const adj: Record<string, string[]> = { A: ["B", "E"], B: ["A", "C"], C: ["B", "D"], D: ["C", "E"], E: ["D", "A"], }; const colour: Record<string, number> = {}; for (const v of vertices) { const used = new Set(adj[v].map((n) => colour[n])); let c = 0; while (used.has(c)) c++; // lowest colour no neighbour is using colour[v] = c; } for (const v of vertices) console.log(v + " -> colour " + colour[v]); console.log("colours used: " + (Math.max(...Object.values(colour)) + 1));

The four-colour theorem

Maps are special: no country can reach four mutually-bordering neighbours without one being boxed in. That geometric fact tames the colouring problem completely for anything you can draw flat without crossing edges — a planar graph.

Every planar graph is 4-colourable: the regions of any map drawn in the plane can be coloured with at most 4 colours so that no two regions sharing a border get the same colour.

Four is also genuinely needed — plenty of maps cannot be done with three. So for planar graphs, \chi \le 4 always, and that bound is tight.

The four-colour theorem was conjectured in 1852 by a student idly colouring a map of England, and then it defeated the world's best mathematicians for over a century. Kempe published a celebrated "proof" in 1879 that stood for eleven years before a fatal gap was found in it.

The real proof arrived in 1976, from Kenneth Appel and Wolfgang Haken — and it was unlike any before it. They reduced the whole infinite problem to checking 1,834 special configurations, then let a computer grind through the cases for over a thousand hours. It was the first time a major theorem was proved with essential help from a machine, and it split the community: can a proof be true if no human can read it end to end? You cannot check it in your head, or even in a lifetime. Today computer-assisted proofs are routine, but this was the one that started the argument — and it is still going.

It feels like piling on edges should force more colours — but it doesn't have to. The complete bipartite graph K_{100,100} has 10{,}000 edges and yet \chi = 2: it is bipartite, so two colours suffice no matter how dense it gets. A single tiny odd cycle, with just a handful of edges, already needs three. What drives \chi is the structure of the clashes, not the raw count of edges.

And do not over-read the four-colour theorem. "Four colours are enough" is a promise about planar graphs only — maps you can draw flat with no crossings. General graphs can need as many colours as you like. The complete graph K_5 needs \chi = 5, precisely because it is not planar (you cannot draw K_5 without edges crossing). Four colours cover every map on Earth, and fail on a graph with only five vertices.