Generator

A wheel of 5 rim regions needs 4 colours

A generator in the discrete library, called 38 times across 8 essays. Below: what it draws with nothing chosen and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

map-colour is one function. Everything below came out of it during this build, at parameters taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and if the generator changes, this page changes with it.

With nothing chosen

A wheel of 5 rim regions needs 4 colours. A hub touching 5 rim regions arranged in a ring. The rim is odd, so the whole map needs 4 colours and no fewer.

Counting the colourings, by deleting and contracting

One swap frees a colour

The Moser spindle: 7 points, every edge one unit, and no three-colouring

Why three colours cannot colour the plane: rhombi forcing a whole circle to one colour

Seven colours enough for the plane: hexagons just under one unit across

What it checks while it draws

Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.

region 0 touches region 1 ×21
deleting and contracting account for the count at 0 colours ×6
a colour has been freed for the middle ×1
a greedy colouring is a proper colouring ×1
a planar graph always has a vertex of degree at most five left ×1
after: no edge joins two regions of one colour ×1
alternating between the rows needs four ×1
an odd rim needs four and an even rim three ×1
and has no triangle ×1
and it has one with four ×1
and so is its short diagonal ×1
and twenty edges ×1
and two is the true answer ×1
and two points of one hexagon are less than one apart ×1
before: no edge joins two regions of one colour ×1
between 3 and 6 rows are drawn ×1
both are triangle-free ×1
Brooks: at most Δ colours ×1
colours are counted up to between 3 and 7 ×1
every edge has length exactly one ×1
every greedy colouring uses between χ and Δ + 1 colours ×1
every one of the seven regions touches every other ×1
every other connected graph needs at most Δ ×1
four colours are enough ×1
greedy in the reverse order uses at most one more colour than the largest remaining degree ×1
Grötzsch's graph has eleven vertices ×1
inside the window both conditions hold ×1
it has 3·2^(k−2) − 1 vertices ×1
it has no triangle ×1
its chromatic number is four ×1
Mycielski's k-th graph needs exactly k colours ×1
no graph with an edge can be coloured with no colours ×1
no two neighbouring regions share a colour ×1
nor with one, when it has an edge ×1
outside it one fails ×1
removing any single edge lets one colour fewer suffice ×1
same-coloured hexagons' centres are √21 sides apart ×1
so points of two same-coloured hexagons are more than one apart ×1
the case is the one where the chain reaches or the one where it does not ×1
the chain reaches the far neighbour exactly in the blocked case ×1
the chain that is swapped does not reach the other neighbour of its pair ×1
the chromatic number is where the count first becomes positive ×1
the circle of radius √3 holds two points one unit apart ×1
the colourings come in families of 24, one for each relabelling of the four colours ×1
the construction shown is the seven-region one ×1
the exceptions need Δ + 1 ×1
the five neighbours use five different colours, which is the only hard case ×1
the fractional chromatic numbers begin 2, 5/2, 29/10 ×1
the Golomb graph has no proper colouring with three colours ×1
the graph is one the family draws ×1
the graph is one this family knows ×1
the graph is the spindle or Golomb's ×1
the hexagons are small enough and large enough ×1
the icosahedron has thirty edges ×1
the map can be coloured with at most five ×1
the map has between 4 and 24 regions ×1
the Moser spindle has no proper colouring with three colours ×1
the rhombus's sides are one unit ×1
the vertical step is 2, 3 or 4 ×1
the view is one the family draws ×1
the wheel has between 3 and 23 rim regions ×1
the window is not empty ×1
their squares stay between 2k and 2k + 2 ×1
three colours do not suffice and four do ×1
top row first needs two colours ×1
with the middle coloured: no edge joins two regions of one colour ×1

Where it is called

Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.

Discrete

Counting the colourings

Asking whether a graph can be coloured with four colours gives a yes or a no. Asking how many ways there are gives a polynomial — and the polynomial answers the first question, and several others nobody asked.

Discrete

Five colours, and a chain that can be followed

The four-colour theorem cannot be checked by a person. The five-colour theorem can, in a page, and the argument that does it is the one Kempe thought had settled four — with the exact step where it fails visible in the picture.

Discrete

Four colours, and a proof nobody can read

Every map on a plane can be coloured with four colours so that no two neighbours match. The statement is understandable by a child, it resisted a century of attempts, and the proof that settled it cannot be checked by a human being.

Discrete

How many colours the plane needs

Colour every point of the plane so that no two points exactly one unit apart share a colour. Seven colours are enough, by a tiling with hexagons, and four are necessary, by a graph of seven points. For sixty-eight years nothing better was known on either side; then in 2018 a graph of 1,581 points showed four is not enough — and the answer is still somewhere from five to seven.

Discrete

No triangle, and four colours

A graph that contains four mutually joined points needs four colours. The converse looks obvious — a graph needing four colours should contain something like that — and it is false. Grötzsch's graph has eleven points, no three of them mutually joined, and needs four colours. Mycielski found a step that adds one colour to any graph without creating a triangle, so graphs with no triangle can need any number of colours, and their need is spread through the whole graph, with no part to point at.

Discrete

Seven regions on a doughnut

A map on a torus can need seven colours, and the proof is a picture — seven regions, each sharing a border with all six others. The plane needed a computer and eighty-six years; the harder surface was settled in 1890 by drawing something.

Discrete

The order decides the colours

The simplest way to colour a graph is to take the vertices one at a time and give each the first colour its neighbours are not already using. It never needs more than one colour beyond the largest degree — and on a graph that needs only two colours it can be made to use as many as there are vertices on a side, depending on nothing but the order it is handed.

Discrete

Two graphs that will not lie flat

Five points, every pair joined: no matter how the points are placed or how the lines are drawn, two of the lines cross. The proof is not about drawing at all — it counts edges against faces and finds one edge too many.

The whole library · What the figures prove