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.

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

1234123412341234123412341234123412341234123412341234123412341234all 16 trees on 4 labelled points, found by taking every set of 3 edges and keeping the ones with no cycle4 to the power 2 is 16, which is the count — and the same rule gives 1,296 on six points, which is why they are not all drawn

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 8 − 12 + 6 = 27 edges on the corner tree · 5 on the face treea spanning tree of the 8 corners uses 7 edges; what isleft over joins the 6 faces into a tree and uses 57 + 5 = 12, which is V − E + F = 2 with the termsmoved about — and it holds for whichever vertex thetree is grown from

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

Named alongside it

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

BijectionCatalan numbersCayleys formulaCounting argumentDual graphEncodingEuler characteristicEuler formulaGraphLabelled treeLeafPlanar graph

All concepts