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 2 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

Named alongside it

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

Complete graphConjectureDecompositionDual graphEuler characteristicEuler formulaExhaustive searchGraph labellingPlanar graphPlanaritySpanning tree

All concepts