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.

Named by 2 essays across 2 fields — 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 every node has at most 3 children and the tree reaches level 416 nodes on the bottom row; the marked walk takes a surviving child at every step

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

Named alongside it

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

Chromatic numberCompactnessComputer assisted proofEuler characteristicFinite branchingGraphInfinite pathKonig lemmaPigeonholePlanar graphPlanaritySatisfiability

All concepts