Trees and Networks - Main Theorem

Cayley's Formula counts the number of labeled trees, revealing a surprising connection between trees and sequences.

Proof via Prüfer Sequences:

We establish a bijection between labeled trees on $\{1, 2, \ldots, n\}$ and sequences of length $n-2$ with elements from $\{1, 2, \ldots, n\}$. There are $n^{n-2}$ such sequences.

Tree to Sequence (Encoding): Given a labeled tree $T$ on $n$ vertices:

1. Find the leaf with smallest label, say $\ell$
2. Add the label of $\ell$'s neighbor to the sequence
3. Remove $\ell$ from the tree
4. Repeat steps 1-3 until only 2 vertices remain

This produces a sequence of length $n-2$ called the Prüfer sequence.

Sequence to Tree (Decoding): Given a sequence $s_1, s_2, \ldots, s_{n-2}$ of elements from $\{1, \ldots, n\}$:

1. Start with isolated vertices $\{1, 2, \ldots, n\}$
2. For $i = 1$ to $n-2$:
   • Find smallest vertex $\ell$ not yet connected and not appearing in $s_i, s_{i+1}, \ldots, s_{n-2}$
   • Connect $\ell$ to $s_i$
3. Connect the two remaining isolated vertices

This produces a unique tree.

Verification: We must show this is a bijection:

Well-defined: The encoding always produces a sequence (we can always find a leaf until 2 vertices remain). The decoding produces a connected acyclic graph (tree).

Inverse: Decoding(Encoding($T$)) = $T$ and Encoding(Decoding($s$)) = $s$. This can be verified by tracking which vertices appear in the sequence (exactly those with degree $\geq 2$, appearing deg$(v) - 1$ times).

Bijection: Since encoding and decoding are inverses, we have a bijection.

Therefore, the number of labeled trees equals $n^{n-2}$. $\square$