Matpic
mathematics, in pictures
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 6 essays across 4 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

Named alongside it

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

GraphBijectionCounting argumentCovering spaceFree groupPlanar graphRankSubgroupCancellationCatalan numbersCayleys formulaCircumcircle

All concepts