Trees and Spanning Trees – Advanced Study Notes
Intended audience: Graduate students in mathematics or theoretical computer science (MIT‑level).
Prerequisites: Elementary graph theory, linear algebra, basic combinatorics, and a taste for proofs by induction and bijection.
1. Foundations
1.1 Basic Definitions
| Symbol | Meaning |
|---|---|
| (G=(V,E)) | Simple undirected graph |
| ( | V |
| (\deg_G(v)) | Degree of vertex (v) |
| Tree | Connected acyclic graph |
| Spanning tree of (G) | A subgraph (T\subseteq G) that is a tree and contains all vertices of (G) |
| Rooted tree | A tree with a distinguished vertex called the root |
| Directed tree / arborescence | A directed acyclic graph where all edges point away from (or towards) a distinguished root |
Edge cases
• A graph with a single vertex is a tree (trivial).
• A graph with no edges cannot be a tree unless it has one vertex.
• A graph with multiple components cannot have a spanning tree; the concept is only defined for connected graphs.
2. Counting Labeled Trees
2.1 Cayley’s Formula
Theorem (Cayley 1889).
The number of labeled trees on (n) vertices is (n^{,n-2}).
2.1.1 Proof via Prüfer Sequences
A Prüfer sequence of a labeled tree (T) on ({1,\dots,n}) is obtained by repeatedly deleting the leaf of smallest label and recording the label of its neighbor, until only two vertices remain.
Key facts
- The procedure produces a sequence ((a_1,\dots,a_{n-2})\in {1,\dots,n}^{n-2}).
- Every such sequence corresponds to a unique tree.
Outline of bijection
| Step | Description |
|---|---|
| From tree to sequence | Delete the smallest leaf repeatedly; record the neighbor. |
| From sequence to tree | Initialise a multiset (S={1,\dots,n}). For each (a_i) in the sequence, attach a new edge from the smallest vertex in (S\setminus{a_i}) to (a_i); remove that smallest vertex from (S). After processing all (n-2) entries, two vertices remain in (S); connect them. |
The construction is reversible, establishing a bijection. Thus the number of labeled trees equals the number of Prüfer sequences, i.e. (n^{,n-2}).
Edge cases
• For (n=1), the empty sequence counts as the unique tree.
• For (n=2), the unique tree corresponds to the empty sequence as well (since (n-2=0)).
2.1.2 Generating Function Approach
Let (T_n) denote the number of labeled trees on (n) vertices. The exponential generating function
[
T(x)=\sum_{n\ge1} T_n \frac{x^n}{n!}
]
satisfies the functional equation
[
T(x)=x,e^{T(x)}.
]
Solving for (T(x)) via the Lagrange inversion theorem yields (T_n = n^{,n-2}).
2.2 Counting Unlabeled (Free) Trees
The number of non‑isomorphic trees on (n) unlabeled vertices grows much more slowly. Otter’s theorem (1948) gives an asymptotic: [ t_n \sim C ,\alpha^n n^{-5/2}, \quad \alpha \approx 2.955765. ] Exact enumeration up to (n=100) is available in the OEIS sequence A000055.
Edge cases
• For small (n) (≤6), the counts can be verified by hand.
• The difference between labeled and unl