THE FOLD / LOOT / THE STASH / THE PRUFER
THE PRUFER
a labeled tree ⟷ a short number sequence — Cayley's n^(n-2)
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Cayley’s formula & the Prüfer sequence. How many different trees can you build on n numbered vertices? Cayley’s answer is stunningly clean: exactly nn−2. Five labelled vertices give 125 trees; six give 1296.
The loveliest proof is Prüfer’s bijection — a perfect one-to-one match between trees and short number strings. To encode a tree: repeatedly find the leaf with the smallest label, write down its single neighbour, and prune it; after n−2 steps you hold a sequence of n−2 numbers, each from 1 to n. To decode, run it backwards. Since there are exactly nn−2 possible sequences and each names exactly one tree, Cayley’s formula falls straight out. As a bonus, every vertex’s degree equals how many times its label appears in the sequence, plus one — a whole tree losslessly squeezed into a tiny code.
LIT verified live: encoding then decoding returns the identical sequence for every case, and the nn−2 sequences decode to exactly nn−2 distinct trees for n up to 6 (window.__prufer). FIG no framing; the bijection and Cayley’s count are exact, checked over all sequences.
The loveliest proof is Prüfer’s bijection — a perfect one-to-one match between trees and short number strings. To encode a tree: repeatedly find the leaf with the smallest label, write down its single neighbour, and prune it; after n−2 steps you hold a sequence of n−2 numbers, each from 1 to n. To decode, run it backwards. Since there are exactly nn−2 possible sequences and each names exactly one tree, Cayley’s formula falls straight out. As a bonus, every vertex’s degree equals how many times its label appears in the sequence, plus one — a whole tree losslessly squeezed into a tiny code.
LIT verified live: encoding then decoding returns the identical sequence for every case, and the nn−2 sequences decode to exactly nn−2 distinct trees for n up to 6 (window.__prufer). FIG no framing; the bijection and Cayley’s count are exact, checked over all sequences.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE STASH — the loot domain of packing something away compactly. A Prüfer sequence is a stash: a whole labelled tree folded down to n−2 numbers and unfolded again with nothing lost. AVAN (AI) built the instrument: the prune-and-record encoder, the rebuild decoder, the codec inverse.
The weave: David names the seat (the lossless stash); I make a tree shrink to a sequence and spring back, and count that the codes exhaust every tree — the pruning in 1D, the encode/decode in 2D, the bijection inverse in 3D. The sphere is the seam. Credit: Arthur Cayley (1889, the formula); Heinz Prüfer (1918, the bijection proof).
The weave: David names the seat (the lossless stash); I make a tree shrink to a sequence and spring back, and count that the codes exhaust every tree — the pruning in 1D, the encode/decode in 2D, the bijection inverse in 3D. The sphere is the seam. Credit: Arthur Cayley (1889, the formula); Heinz Prüfer (1918, the bijection proof).
3 ONE DIMENSION
Encoding a tree, one step per column: prune the smallest-labelled leaf, record its neighbour. After n−2 prunings the row of recorded neighbours is the whole Prüfer sequence — the tree, flattened to a line.
4 TWO DIMENSIONS · INTERACTIVE
A labelled tree and its Prüfer sequence, side by side. Step the encoder to watch leaves fall and the code build up; or cycle to a new sequence and watch the tree it decodes to. Encode then decode always returns the same tree.
5 THREE DIMENSIONS + AVAN’S INVERSE
The tree as a turning graph — the green forward step: prune leaves in label order, recording neighbours, until a tree becomes a sequence.
AVAN’s addition (the inverse-companion): the magenta is the decode — rebuilding the tree from the sequence by attaching leaves back in reverse. Encode and decode are exact inverses, a lossless codec: green shrinks n−1 edges to n−2 numbers, magenta expands them back with nothing lost. And that invertibility is Cayley’s proof — because the map is a bijection, the number of trees must equal the number of sequences, nn−2, with no counting argument beyond ‘the codec never collides and never misses.’ The sequence even carries the degrees on its sleeve: a label’s count plus one. Green flattens the tree to a code; magenta lifts the code back to the tree; the fact that they perfectly undo each other is the whole reason there are exactly nn−2 trees. To count a structure, find the code it cannot escape.
LIT Genuine Cayley's formula and Prufer bijection (Arthur Cayley 1889; Heinz Prufer 1918). Verified live: encoding then decoding returns the identical sequence in every case, and the n^(n-2) length-(n-2) sequences decode to exactly n^(n-2) distinct labeled trees for n up to 6 (window.__prufer.bijectionAndCayley true; n=5: 125=125, n=6: 1296=1296). The bijection and Cayley's count are exact, checked over all sequences.
FIG No framing: the tree<->sequence bijection, the lossless round-trip, and Cayley's n^(n-2) count are real and verified exhaustively over every sequence in-browser (not sampled). The AVAN inverse is the genuine mathematical content — the encode/decode being exact inverses IS Cayley's proof, since a bijection forces equal cardinalities, and the degree = count+1 relation is exact.
FIG No framing: the tree<->sequence bijection, the lossless round-trip, and Cayley's n^(n-2) count are real and verified exhaustively over every sequence in-browser (not sampled). The AVAN inverse is the genuine mathematical content — the encode/decode being exact inverses IS Cayley's proof, since a bijection forces equal cardinalities, and the degree = count+1 relation is exact.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE STASH · David Lee Wise (ROOT0), with AVAN