Planar graph
Named by 17 essays across 3 fields — each of them below, with the objects they name alongside it.
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.
Every corner pays for itself
Count the corners of any solid, subtract the edges, add the faces. The answer is two. It is two for a cube, for a pyramid, for a football, for anything squashed or stretched — and the number is measuring the shape it is wrapped around rather than the shape itself.
The plane, divided by whoever is nearest
Scatter some points and colour every other point of the plane by which one is closest. The result is a tiling nobody designed, and its dual triangulation has a property that no part of the construction mentions.
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.
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.
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.
The tree inside the triangulation
The shortest network joining a set of points is built from edges chosen by length, and the triangulation is built from edges chosen by an emptiness condition about circles. The two constructions share no step, and every edge of the first is an edge of the second.
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.
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.
The order decides the colours
The simplest way to colour a graph is to take the vertices one at a time and give each the first colour its neighbours are not already using. It never needs more than one colour beyond the largest degree — and on a graph that needs only two colours it can be made to use as many as there are vertices on a side, depending on nothing but the order it is handed.
Every count a solid can have
Euler's formula ties the corners, edges and faces of a convex solid together, but it does not say which numbers are possible. Ernst Steinitz answered in 1906: V corners and F faces occur together exactly when neither is more than twice the other less four. The proof in one direction is two lines of counting; in the other it is two moves — cut off a corner, glue on a tetrahedron — that walk from the pyramids to every allowed pair.
The crossings a graph cannot avoid
Five points all joined need one crossing, six need three, seven need nine. Euler's formula gives a lower bound that grows like the square of the number of points and is badly wrong; a sampling trick turns the same formula into a bound that grows like the fourth power and is right to within a constant. And for drawings with straight edges the count turns out to be something else entirely: the number of quadrilaterals the points make.
Every point at the average of its neighbours
A planar graph can be drawn without crossings, but finding such a drawing looks like a search. Tutte found in 1963 that it is not: pin one face to a convex polygon, put every other point at the average of its neighbours, and the drawing that results has straight edges, convex faces and no crossings at all — provided no two points can cut the graph apart. It is the position a network of equal springs settles into, and it is also where a random walk expects to leave.
Every edge on exactly two cycles
Draw a graph on paper without crossings and its faces are cycles, each edge on exactly two of them. George Szekeres and Paul Seymour asked in the 1970s whether every graph without a bridge has such a set of cycles, drawn on paper or not. The Petersen graph needs five, the flower snark on twenty points five as well, every random graph tried has one, and nobody has proved it — though a minimal counterexample would have to be a snark.
Signs that make a determinant count
Hall's theorem says whether a board can be covered by dominoes. How many ways it can be covered is a different question, and for a general graph a hopeless one — the count is a permanent, and nobody expects an efficient way to compute permanents. On a flat board it is a determinant. Put a minus sign on the vertical pairs in every second column and the thirty-six coverings of a four-by-four board stop cancelling and add up; the chessboard has 12,988,816. A hole in the board breaks the rule in a way a cut repairs, and on K₃,₃, which cannot be drawn flat, no choice among its 512 signings works at all.
Pairs of trees that count planar maps
Give every flip of a triangulation a direction and the triangulations become an order, the Tamari lattice. Counting the pairs that are in order — 1, 3, 13, 68, 399, 2,530, 16,965, 118,668, 857,956 — gives 2(4n + 1)!/((n + 1)!(3n + 2)!), which is exactly Tutte's 1962 count of planar triangulations. Chapoton noticed the match in 2006; a pair of trees and a map on a sphere turn out to be the same thing.
How many ways a curve can cross itself
A closed curve that crosses itself three times can be drawn in exactly six essentially different ways on a sphere, and twenty in the plane. Four crossings give nineteen and eighty-two; six give 376 and 2,645. Every one of them is a word — the order in which the crossings are met — and a choice of direction at each crossing, and the whole census comes from asking which of those choices close up on a sphere.
Named alongside it
The objects these essays reach for when they reach for this one.
Euler characteristicEuler formulaExhaustive searchGraphGraph colouringPlanarityConvexityChromatic numberComplete graphPolyhedronConjectureCounting argument