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. It is at most four for any map drawn in the plane, and computing it in general means searching rather than evaluating a formula.

Named by 3 essays across one field — 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 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

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