Encode a labeled tree reversibly

Try

A tree on four labeled vertices can be a path or a star, with many labelings of each. Cayley’s formula counts all labeled trees at once: n^(n−2) for n≥2. The proof uses a reversible code of length n−2 with entries from the n labels. Establishing that every such word decodes to exactly one tree is essential; merely producing a word from each tree would only give one side of a counting argument.

Predict

Predict why a leaf is the right object to remove. Deleting a leaf preserves connectedness and absence of cycles on the remaining vertices. To make the code deterministic, always delete the smallest labeled leaf and record its unique neighbor. Continue until two vertices remain. The labels of deleted leaves need not be recorded because the decoder can recover them from the remaining word.

Experiment

Encode the tree with edges 12, 23, 24, 45.

Smallest leaf removed	Recorded neighbor	Remaining code prefix
1	2	2
3	2	2, 2
2	4	2, 2, 4

The last edge is 45. Decode the word (2, 2, 4) independently. At the first step, label one is the smallest label absent from the word; after removing its first entry, label three becomes the smallest available absent label.

Understand

For decoding, maintain the unused vertex labels and the remaining word. Choose the smallest unused label not appearing in that word, join it to the first word entry, remove the chosen label and that entry, and repeat. Such a label exists because the word is two shorter than the current label set. Finally join the two remaining labels. Each added edge attaches a vertex that is then removed from future consideration, so the resulting graph is connected and acyclic. In an encoded tree, a label appears once for each incident edge removed before its own final removal; hence it occurs degree minus one times. The labels absent from the remaining code are exactly the current leaves, making encoding and decoding inverse.

Apply

There are n choices for each of n−2 code positions, proving Cayley’s formula. The occurrence identity also gives a refinement: for positive degrees d_i summing to 2n−2, the number of labeled trees with those degrees is (n−2)! divided by product (d_i−1)!. The formula counts words with prescribed multiplicities. For n=4, a fixed star center has code consisting of that label twice, giving one tree for that center; the four choices of center account for four of the sixteen trees. Other words produce paths.

Continue

The labels matter: sixteen labeled trees on four vertices do not mean sixteen unlabeled shapes. Forgetting labels creates unequal orbit sizes because different trees have different automorphism groups, so division by n! is invalid. For n=2 the code is empty and describes the unique edge; n=1 is handled separately. Use the code as an implementation exercise with invariant checks for degrees and edge count, then verify decoding by an independent connectivity and cycle test rather than only re-encoding the same output.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with count spanning trees with a determinant.