Matpic
mathematics, in pictures
Concept

Planarity

The property of a graph that it can be drawn in the plane with no two edges crossing. Kuratowski's theorem says exactly two graphs obstruct it, so failing is always failing for one of two reasons.

Named by 8 essays across 3 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 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 Two trees, sharing every edge between them. The cube flattened into a planar graph, with a spanning tree of its corners drawn solid and the leftover edges drawn dashed; the leftover edges join the faces into a second tree, and the two counts add to the number of edges.

Two trees, and every edge in exactly one of them

Euler's formula is usually proved by deleting things until nothing is left. There is a better argument that deletes nothing — a tree through the corners and a tree through the faces, which between them use every edge once and can therefore be counted.

topology · Euler characteristic 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 Nineteen circles, one per vertex. A circle packing of a triangulation with seven interior vertices and twelve on the boundary: two circles touch exactly when their vertices are joined, and the radii were solved for rather than chosen.

Every flat graph is a pile of circles

A graph that can be drawn without crossings can be drawn in one particular way: as circles, one per vertex, touching exactly when their vertices are joined. The picture is not a choice — it is determined, up to the group two inversions generate.

geometry · Inversion The Petersen graph, which a five-edge count rules off the plane. The Petersen graph drawn as an outer pentagon, an inner pentagram and five spokes: ten points, fifteen edges, girth five, and more edges than the 13.33 a flat drawing with five-edge faces allows.

Five spokes squeezed into K5

The Petersen graph has no point with four neighbours, so no stretched copy of K5 can sit inside it. Contract its five spokes and K5 appears anyway. Kuratowski's theorem forbids stretched copies and Wagner's forbids squeezed ones, the two notions disagree on this graph — and they still name exactly the same planar graphs.

discrete · Planarity Breadth-first levels in a planar triangulation. A Delaunay triangulation of 160 random points with each point coloured by whether it is inside, on or outside the level 4 steps from the centre; that level of 23 points separates 31 from 106.

The few points that cut a flat graph

Any graph that can be drawn without crossings, however large, falls into pieces of at most two thirds once a few points are removed — about the square root of its size, never more than 2.83 times it. A grid shows the square root cannot be beaten, a ring of breadth-first neighbours comes close, and a cycle through a shallow tree finishes the job.

discrete · Planarity Six points in space and the triangles that link, seed 48. A projection of K₆ with straight edges, the under-strands broken at crossings. 1 of the ten pairs of disjoint triangles are linked; the pair 126 and 345 is coloured.

Six points in space and a pair that must link

Put six points anywhere in space and join every pair with a straight segment. Split the six into two triangles — there are ten ways — and at least one of the ten pairs of triangles is linked like two rings of a chain. No placement avoids it. The reason is a parity: moving an edge through another changes exactly two of the ten linking numbers, so their sum stays odd whatever is done.

topology · Linking number

Named alongside it

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

Planar graphComplete graphEuler formulaGraphGraph colouringEuler characteristicExhaustive searchSubdivisionChromatic numberCircle packingComputer-assisted proofConformal map

All concepts