Encoding
Repeatedly: find smallest leaf, record its neighbor, remove leaf. Do n-2 times.
Advertisement
Decoding
Available = all vertices. Iterate over sequence: find smallest not in remaining sequence, connect to current sequence element.
Advertisement
Cayley's formula
Number of labeled trees on n vertices = n^(n-2). Prüfer bijection proves it.
Extensions
Weighted Cayley (spanning trees of weighted K_n). Matrix-tree theorem generalizes.