Matpic
mathematics, in pictures
Concept

Tree — where it appears

A connected graph with no cycles, so that between any two of its points there is exactly one path. A tree on n points has n minus 1 edges, and trees are what spanning, searching and labelling problems on graphs are built from.

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

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 Four trees on seven points, gracefully labelled. a path: 0 6 1 5 2 4 3; a star: 0 1 2 3 4 5 6; a caterpillar: 0 5 1 6 2 4 3; a spider: 0 1 4 5 3 6 2.

A labelling every tree seems to have

Number the points of a tree 0 to n − 1 and write on each edge the difference of the numbers at its ends. The labelling is graceful if the edges then carry 1 to n − 1, each exactly once. Every tree anyone has ever checked — every one of the 551 trees on twelve points, and every tree up to about thirty-five — has such a labelling, and no one knows why. A graceful tree also tiles a complete graph by rotation, which is why the question was asked.

discrete · Labelled trees The twenty-three trees on eight points. 23 shapes on 8 points by Prüfer search; diameters 2,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,6,6,6,7.

How many shapes a tree can take

There are 262,144 labelled trees on eight points and only twenty-three shapes. Labels make counting easy — Cayley's nⁿ⁻² — and shapes make it hard, because a symmetric shape absorbs labellings. The count of shapes comes instead from a recurrence for trees with a root and a theorem of Richard Otter's for taking the root away: in every tree there is exactly one more class of points than of edges. Run to two hundred points, the counts grow like 0.535 × 2.9558ⁿ ÷ n^(5/2), and the same arithmetic counts the alkanes.

discrete · Labelled trees

Named alongside it

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

AsymptoticsAutomorphismBurnside lemmaCayleys formulaComplete graphConjectureDecompositionDual graphEuler characteristicEuler formulaExhaustive searchGenerating function

All concepts