Spanning tree
Named by 20 essays across 9 fields — each of them below, with the objects they name alongside it.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
Exhaustive searchGraphGreedy algorithmBijectionCayleys formulaCounterexampleDeterminantConjectureCounting argumentCounting two waysCovering spaceExpectation