This chapter considers a class of graphs called trees and their construction. Trees are connected graphs containing no cycles. When dealing with trees, a vertex of degree 1 is called a leaf rather than an end-vertex. The chapter first provides an overview of trees and their leaves, along with the relevant theorems, before discussing a tree-counting problem, introduced by British mathematician Arthur Cayley, involving saturated hydrocarbons. It shows that counting the number of saturated hydrocarbons is the same as counting the number of certain kinds of nonisomorphic trees. It then revisits another Cayley problem, one that involved counting labeled trees, and describes Cayley's Tree Formula and the corresponding proof known as the Prüfer code. It also explores decision trees and concludes by looking at the Minimum Spanning Tree Problem and its solution, Kruskal's Algorithm.
Princeton Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.
If you think you should have access to this title, please contact your librarian.
To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us.