Sandra Hasselgren: Cayleys formel för antalet träd

Abstract.

In this essay we look at different proofs of Cayley’s formula. Cayley’s formula is a formula for the number of labeled trees we can form from \(n\) number of vertices. The proofs has different approaches on how to prove the formula. We use bijection, linear algebra, recursion, a type of double counting, proof using Prüfer sequence and proof using polynomials.