Matpic
mathematics, in pictures
Series

Labelled trees — the series

4 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    part 1 · discrete
  2. Pollak's circle: one rotation in every n + 1 parks on the line. Several circles of numbered spots, each showing where cars park when every preference in a list is rotated by a fixed amount, with the one rotation that leaves the last spot empty highlighted.

    Cars that park, and trees that grow

    Three cars arrive at a one-way street with three spaces; each has a favourite space, drives to it, and takes the first free one from there on. Of the 27 lists of favourites, exactly 16 let every car park — the same 16 as the labelled trees on four points. The reason is a circular street with one extra space, on which every list parks and exactly one rotation of it leaves the extra space empty.

    part 2 · discrete
  3. A random labelled tree on 60 points. A tree drawn in horizontal layers by distance from a root point, with the leaves coloured differently from the internal points.

    A random tree is one part in e leaves

    Choose a labelled tree on n points uniformly at random. A point is a leaf exactly when its label never appears in the tree's Prüfer code, so the share of leaves is (1 − 1/n)^(n − 2) — half the points for a tree on four, 36.8% for a large one, the reciprocal of e. The whole degree distribution follows the same way: one plus a Poisson count with mean one.

    part 3 · discrete
  4. 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.

    part 4 · discrete

All series