IMO (Maths Olympiad) /Combinatorics

Trees and Spanning Trees

Graph Theory · free study notes

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

  1. The procedure produces a sequence ((a_1,\dots,a_{n-2})\in {1,\dots,n}^{n-2}).
  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

Your note

Page 1

Doubt hai is topic me?

Free AI teacher se poocho — 24/7, step by step.