Matpic
mathematics, in pictures
Series

Graph colouring — the series

4 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    part 1 · discrete
  2. 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.

    part 2 · discrete
  3. 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.

    part 3 · discrete
  4. 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.

    part 4 · discrete

All series