Lesson 3

Theorem (Cayley, 1889). The number of different trees on \(n\) vertices is equal to \(n^{n-2}\).

Cayley's formula has many different proofs, both combinatorial and algebraic. Below we provide an algorithmic proof: we construct a bijection between all spanning trees and simple objects, the number of which is easy to count.