Matpic
mathematics, in pictures
Concept

Graph colouring

An assignment of colours to a graph's vertices in which no edge joins two of the same colour. The fewest colours needed is the chromatic number, and four suffice for every graph that can be drawn without crossings.

Named by 6 essays across 2 fields — each of them below, with the objects they name alongside it.

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.

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 · Graph colouring A tree branching at most 3 ways, to depth 4, and the path through it. A tree drawn level by level, with the nodes that die out faint and a highlighted path that always steps to a node with descendants at the bottom.

An infinite tree has an infinite path

A tree that goes on forever, in which every node has only finitely many children, must contain a single branch that goes on forever. The proof is a rule for walking, and the rule is the whole of why finite information can decide an infinite question.

logic · Models Two graphs that will not lie flat, and one that will. K4, K5 and K3,3 in the best straight-line drawings a search could find. K4 has no crossings; the other two have one each, and Euler's formula shows that none can have none.

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.

discrete · Planarity One swap frees a colour. A vertex of degree five whose neighbours carry five different colours, before and after a Kempe chain is recoloured. The swap frees one colour for the middle vertex.

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 · Graph colouring Counting the colourings, by deleting and contracting. A graph beside the two smaller graphs its edge deletion and contraction produce, with the number of proper colourings of each at every number of colours up to 5.

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 · Graph colouring Seven regions on a doughnut, each touching all six others. A brick pattern of seven labelled regions on a torus, drawn as a rectangle whose opposite edges are identified. Every pair of regions shares a border, so no two may take the same colour.

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 · Graph colouring

Named alongside it

The objects these essays reach for when they reach for this one.

Chromatic numberPlanar graphPlanarityComplete graphEuler characteristicEuler formulaGraphChromatic polynomialCompactnessComputer-assisted proofCounterexampleCounting

All concepts