Networks and Spanning Trees

Abstract

This curricular module offers insight into the origin and use of the structure in graph theory known today as a “labeled tree.” Beginning with Arthur Cayley's 1889 publication “A Theorem on Trees,” the reader is led to a counting argument for certain trees on n vertices, although Cayley's use of the term “tree” is intuitive, without a formal definition.  Almost thirty years later, Heinz Prüfer offered a rigorous proof of Cayley's formula. Prüfer himself never used the term “tree” in his proof; instead he counted all possible railway networks connecting n-many towns so that the least number of segments are used, foreshadowing a characterization of labeled trees.  Several years after Prüfer's publication, as a striking application of trees, Otakar Borůvka presented an algorithm for finding a network of least total length connecting n-many towns with an electrical network.  Borůvka also did not use the term “tree," although his work is seen today as representing an algorithm for finding a minimal spanning tree among all labeled trees on n vertices. Nowadays, this type of algorithm is also known in computer science as a greedy algorithm.  The project is designed for a course in graph theory, advanced undergraduate discrete mathematics, or algorithm design.