Masters Theses

Date of Award

8-2003

Degree Type

Thesis

Degree Name

Master of Science

Major

Mathematics

Major Professor

Reid Davis

Abstract

In 1889 Arthur Cayley stated his well-known and widely used theorem that there are n° - 2 trees on n labeled vertices [6, p. 70]. Since he originally stated it, the theorem has received much attention: people have proved it in many different ways. In this paper we consider three of these proofs. The first is an algebraic . result using Kirchhoff s Matrix Tree theorem. The second proof shows a one-to-one correspondence between trees on labeled vertices and sequences known as Prufer codes. The final proof involves degree sequences and multinomial coefficients. In addition, we extend each of these three proofs to find a result for the number·of spanning trees on the complete bipartite graph, and extend the first two results to count the number of spanning trees on the complete tripartite graph. We conclude with a brief generalization to the number of spanning trees on the complete k-partite graph.

Download
Files over 3MB may be slow to open. For best results, right-click and select "save as..."

Share

COinS