Matpic
mathematics, in pictures
Concept

Chromatic number

The fewest colours a graph can be properly coloured with, so that no edge joins two vertices of one colour.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

the mapwho touches whom

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 the chain, before?01234swapped — colour 0 is free0212345 neighbours in 5 colours, so nothing is spare for the middle until a chain is swappedthe 0–2 chain stops before it reaches the far neighbour, so swapping it frees colour 0 for the middlethe two chains cannot both cross the disc, because a crossing point would have to carry two colours at once —and that is where planarity is spent

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 the graphone edge deletedthe same edge contractedcoloursthe graphdeletedcontracted0000100020223618124488436518026080a four-cycle with one chord: every count is made by trying all k^4 assignments and checking each onethe graph needs 3 colours, and below that the count is not small — it is zero, which is what a countingversion of the question says instead of yes or no

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

Named alongside it

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

Graph colouringPlanar graphChromatic polynomialComputer assisted proofCounterexampleCountingDeletion contractionEuler characteristicEuler formulaGraphInductionKempe chain

All concepts