Jera Stojko (2017) *Counting trees*. Diploma thesis.

| PDF Download (563Kb) |

## Abstract

In graph theory, trees are combinatorial objects usually defined as connected graphs without cycles. In this thesis, the problem of counting different trees with a given number of vertices is presented. Four proofs of a celebrated theorem on the number of labeled trees by A. Cayley are given: by using a bijective construction due to H. Prüfer, by double counting of labeled rooted trees due to J. Pitman, by establishing a recursion on the number of labeled forests, and finally, by applying a relation between determinants and spanning trees due to H. Kirchhoff. In the final part, a recent result by A. Chin et al. is presented on the probability that a randomly picked tree in a complete graph is a spanning tree. In particular, the limit of this value as the number of vertices approaches infinity is observed. The result obtained is both surprising and beautiful.

Item Type: | Thesis (Diploma thesis) | ||||||
---|---|---|---|---|---|---|---|

Keywords: | graph, complete graph, tree, spanning tree, enumerating, Cayley's Theorem, probability | ||||||

Number of Pages: | 43 | ||||||

Language of Content: | Slovenian | ||||||

Mentor / Comentors: |
| ||||||

Link to COBISS: | http://www.cobiss.si/scripts/cobiss?command=search&base=50126&select=(ID=11727689) | ||||||

Institution: | University of Ljubljana | ||||||

Department: | Faculty of Education | ||||||

Item ID: | 4723 | ||||||

Date Deposited: | 22 Sep 2017 10:47 | ||||||

Last Modified: | 22 Sep 2017 10:47 | ||||||

URI: | http://pefprints.pef.uni-lj.si/id/eprint/4723 |

### Actions (login required)

View Item |