Concept

Spanning tree

A set of a graph's edges that reaches every vertex and closes no loop, using one fewer edge than there are vertices. Every connected graph has one, and counting them is Cayley's formula when the graph is complete.

Named by 20 essays across 9 fields — each of them below, with the objects they name alongside it.

All 16 trees on 4 labelled points. Every tree on 4 labelled points, drawn one by one. There are 16 of them, which is 4 to the power 2.

Sixteen trees on four points

How many ways are there to connect n labelled points into a single tree? The answer is n to the power n minus two, which is a strange enough formula to demand an explanation — and the explanation is a code that turns every tree into a short list of numbers, and every short list of numbers back into a tree.

discrete · Labelled trees
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
A wedge of 2 circles. Several circles all passing through one common point, each labelled with a generator, so that a loop is a word in those letters.

The subgroup that is freer than the group

A free group on two letters contains a subgroup of index three that is free on four. Nothing about a group makes that plausible; everything about a graph makes it obvious, and the argument is to stop looking at the group and start looking at the space whose loops it is.

topology · Covering spaces
A determinant counting the 16 spanning trees. A small graph, the minor of its Laplacian, and every one of its spanning trees drawn as thumbnails.

A determinant that counts trees

Write down a graph's Laplacian, strike out one row and its column, take the determinant. The answer is the number of spanning trees — and the minus signs in the determinant are what cancel every subset of edges that is not one.

algebra · Determinant
The shortest tree was already in the triangulation. The Delaunay triangulation of 20 sites in faint lines with the minimum spanning tree drawn over it in heavy ones. Every tree edge is a triangulation edge, and the circles on the longest few tree edges as diameters contain no other site.

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.

geometry · Voronoi
6 vertices folded to 4, and a graph that decides. The graph built from 3 generator words, folded until no vertex has two edges of one label leaving it. Reading a word from the base vertex decides membership, and 6 words are tested.

Folding a graph until it decides

A subgroup of a free group usually arrives as a list of words, and almost nothing about it is readable from the list. Draw the words as loops, merge every pair of edges with the same label leaving one point, and what is left is a machine that decides membership by reading.

topology · Covering spaces
A network of six places and the tree that holds all fifteen of its cheapest cuts. A network with capacities on its roads beside a tree on the same places, whose edge numbers give the cheapest cut between any two places as the smallest number on the path joining them.

One tree for every cut

A network of six places has fifteen pairs, and each pair has its own cheapest cut. All fifteen can be read off a tree with five numbers on it: the cheapest cut between any two places is the smallest number on the tree's path between them. Gomory and Hu proved in 1961 that such a tree always exists, and building it takes five cuts, not fifteen.

discrete · Network flow
A 33 × 32 rectangle cut into 9 unequal squares. A squared rectangle of 9 squares with sides 18, 15, 14, 10, 9, 8, 7, 4, 1, each labelled with its size.

A rectangle made only of squares

A rectangle can be cut into finitely many squares — of any sizes, as many as wanted — exactly when its two sides are in whole-number proportion. Max Dehn proved it in 1903, and the proof that stuck, found by four Cambridge undergraduates in 1940, reads the squares as currents in an electrical circuit.

computation · Scissors congruence
Two different graphs with the same adjacency matrix eigenvalues. a star with four arms: adjacency matrix eigenvalues 2, 0³, −2; a square and a lone point: adjacency matrix eigenvalues 2, 0³, −2. The characteristic polynomials are identical.

Two graphs the eigenvalues cannot tell apart

A graph's matrix has eigenvalues, and they count a surprising amount of the drawing: its edges, its triangles, every closed walk of every length. They do not count everything. A star with four arms and a square beside a lone point have the same eigenvalues exactly, although one of them is in two pieces — and on six points ten of the 156 graphs have a twin of this kind.

algebra · Linear maps
The cheapest tree for a remote user between two near ones, and each user paying for its own link. A source and 3 users with link costs source–A 2, source–B 9, source–C 2, A–B 1, B–C 1, A–C 2; the cheapest tree costs 4 and Bird's rule charges 2, 1, 1.

Each user pays for its own last link

Several users must be connected to a source, and the cheapest network that does it is a tree. Dividing its cost so that no group of users would rather build its own looks like a hard search, and it has a one-line answer: each user pays for the link that joins it to the tree on its way to the source. No group is ever overcharged — while the average over orders of arrival, the rule that settles so much else, can charge a pair more than its own connection costs.

applied · The core
Christofides' algorithm: tree, pairing, tour. 12 cities: tree 2.4441, 6 odd cities paired for 1.5306, tour 3.6069, shortest 3.4606.

Tours within half again of the best

Nobody can find the shortest tour through many cities quickly, but a tour at most half as long again as the best can be built in a few steps: the shortest tree, a cheapest pairing of the cities where the tree branches oddly, an Euler circuit, and shortcuts. Nicos Christofides found it in 1976, and for forty-five years nobody could guarantee better. A strip of cities shows the half is really lost, and Laurence Wolsey's reading of the same argument shows it bounds the linear programme too.

applied · Duality
A function on nine points, and the tree with two marks it becomes. Left: a function on 9 points as arrows, with cycles through 2, 5, 7 and trees hanging into them. Right: the tree Joyal's rule makes from it, a path from head 7 to tail 2 with the same trees hanging below.

Every function is a tree with two marks

There are n to the n functions from n points to themselves, and n to the n − 2 trees on those points. André Joyal noticed in 1981 that the missing factor of n² is a choice of two points — a head and a tail — and that a function, read the right way, simply is a tree with a head and a tail. The reading turns Cayley's formula into one line and hands over a fact about random trees from the birthday problem.

discrete · Labelled trees
Building a spanning tree by keeping every edge that closes no loop. Four stages of a greedy pass over the fourteen edges of an eight-point graph, ending with a spanning tree of 7 edges.

A spanning tree for every graph

Every connected graph has a spanning tree: a set of its edges that joins every point and closes no loop. For a finite graph the proof is a greedy pass over the edges. For an infinite graph the greedy pass has to keep going past the end of every list, and the statement turns out to be exactly as strong as the axiom of choice — Zorn's lemma supplies the tree, and the existence of spanning trees in every graph gives back the whole axiom.

logic · Axiom of choice
Seven towns joined with junctions and without. Seven random points: spanning tree 1.65407, Steiner tree 1.54997 with 2 junctions, ratio 0.93707.

What a junction can save

Join a set of towns by roads that may meet only at towns, and the shortest such network is easy to find. Allow junctions anywhere and the network gets shorter — but never, it is conjectured, by more than 13.4%, the saving the Fermat point makes on an equilateral triangle. Computed exactly on 1,304 random sets of up to seven towns, the average saving is about 3%. An adversarial search drives it down to the bound and no further, and a hexagon with its centre attains it exactly. The proof of the bound that was accepted for twenty years has a gap.

geometry · Triangle centres
Two edges of a small graph, and whether one makes the other less likely. tree: 8 total, 5 with e, 5 with f, 3 with both, ratio 0.9600; forest: 24 total, 10 with e, 10 with f, 4 with both, ratio 0.9600; connected: 14 total, 10 with e, 10 with f, 7 with both, ratio 0.9800.

Edges that crowd each other out

Pick a spanning tree of a graph uniformly at random, and the presence of one edge makes every other edge less likely — a theorem of Kirchhoff's electricity. Pick a forest instead, or a connected subgraph, and the same is believed and unproved. Checking every pair of edges in every labelled graph up to six vertices, 871,926 pairs for forests alone, finds no exception, and comes as close as 0.9994 to one.

probability · Concentration
The zero of a sandpile. Identity of the sandpile group on 128×128: cells with 0,1,2,3 grains: 1664, 568, 5368, 8784; checked by adding it to the all-3 pile.

The zero of a sandpile

Pile grains of sand on a grid, and whenever a cell holds four, let it topple and pass one grain to each neighbour. The order in which cells topple turns out not to matter, and the piles that keep recurring when sand is dropped at random form a group — one whose size is the number of spanning trees of the grid. Its zero is not the empty grid but a fractal picture of nested squares, and sand dropped on a single cell spreads into a round pile with the same kind of pattern inside.

dynamics · Cellular automata
The cheapest tree through forty points. n=40, seed 8: total 1.063675, largest edge 0.0605, ζ(3)=1.2020569.

The cheapest tree costs ζ(3)

Join n towns by every possible road, give each road a cost drawn at random between nought and one, and find the cheapest network of n − 1 roads that connects them all. However many towns there are, the bill tends to 1 + 1/8 + 1/27 + 1/64 + … = 1.2020569. The proof watches the cheap roads arrive one at a time and turns the cost into the area under a curve that counts the pieces of a growing random graph.

applied · Assignment
The forests of a complete graph on four points. K4 forests by size: 1, 6, 15, 16; ratios 2.4000, 2.3438.

The forests a graph can hold

Count the sets of edges in a graph that contain no cycle, sorted by size, and the counts rise and fall in a single peak — more sharply peaked, John Mason conjectured in 1972, than the binomial coefficients with the same number of edges. On every graph with up to six points the strongest of his three inequalities holds, with equality exactly where cycles are too long to matter; on random graphs with nine points it holds with a margin of about one per cent. It was proved for every graph, and every matroid, in 2018.

discrete · Generating functions
What junctions save in space. tetrahedron SMT/MST 0.81305; 12-point helix 0.79472.

A chain of tetrahedra saves more

In the plane, junctions never seem to shorten a network of roads by more than the equilateral triangle's 13.4%. In space the regular tetrahedron allows 18.7%, and the obvious guess — that it is the worst case, as the triangle is in the plane — is wrong. Points spaced along a chain of tetrahedra glued face to face do better with every point added: 20.5% at twelve, 21.4% at sixty, and about 21.6% in the limit. Random points come nowhere near, and a search that only goes downhill does not find the chain.

geometry · Triangle centres
Two arrows in and two out at every point. 9×9 patch from a random height function, seed 3; heights range 1..6.

Two arrows in and two out

An Eulerian circuit enters every point as often as it leaves, so it hands every edge an arrow with the arrows balanced at each point. Count those balanced orientations instead of the circuits and the question turns into the ice in a freezer: on the square grid, where every point has two arrows in and two out, there are about 1.5396 of them per point — Lieb's (4/3)^(3/2), against Pauling's guess of 1.5. Fix the walls of a square of ice and the count becomes 1, 2, 7, 42, 429, 7436: the alternating-sign matrices.

discrete · Eulerian paths

Named alongside it

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

Exhaustive searchGraphGreedy algorithmBijectionCayleys formulaCounterexampleDeterminantConjectureCounting argumentCounting two waysCovering spaceExpectation

All concepts