In this thesis we discuss Cayley's formula, which states that there are $n^{n-2}$ labelled trees on $n$ vertices. The versatility of this formula can be seen through the diversity of its proofs. We are introduced to bijection based proofs between sets of the same cardinality, such as Pitman's, Joyal's and Prufer's proof. We get to know recursive tree relations that can be proved by induction on the number of vertices. We learn about links between the branching process and random walks and use them in proofs. Using knowledge of linear algebra as well as introducing the Laplacian matrix and the Matrix-tree theorem we show that Cayley's formula holds. We also present the usability of exponential generating functions for counting labelled trees along with Lagrange's inversion theorem.
|
