Networks and Spanning Trees

In 1857 Arthur Cayley (1821–1895) published a paper [8] that introduces the term “tree” to describe the logical branching that occurs when iterating the fundamental process of differentiation. Of composing four symbols that involve derivatives, Cayley writes “But without a more convenient notation, it would be difficult to find [their] corresponding expressions . . . . This, however, can be at once effected by means of the analytical forms called trees . . . ” [8]. Without defining the term “tree,” Cayley has identified a certain structure that occurs today in quite different situations, from networks in computer science to representing efficient delivery routes for transportation. Cayley wishes to count trees with certain properties, which suggests that they can be organized according to patterns, studied, and classified. What properties distinguish trees as different for the purpose of counting depends, in part, on their application. In the paper “On the Theory of the Analytical Forms Called Trees” [8], every tree represents a sequence of derivatives applied in a very specific order, beginning at a base or root term denoted U . Cayley actually uses the word “root” in reference to the point corresponding to U in the physical representation of the tree. The remainder of the paper enumerates what today are called “rooted trees.” However, in a later paper “A Theorem on Trees” [9], published in 1889, Cayley makes a finer distinction when counting trees, so that no one point is considered as the root, but all points carry fixed labels α, β, γ, etc. The British mathematician counts these trees with fixed labels, arriving at a result that today is called “Cayley’s formula.” His proof is a bit incomplete, and we read only a short excerpt from “A Theorem on Trees.” The reader is encouraged is note how Cayley associates certain polynomials to trees in order to help in the counting process. The German mathematician Heinz Prüfer (1896–1934) offers a quite clever and geometrically appealing method for counting what today are called labeled trees. He uses no modern terminology, not even the word “tree” in his work. Instead, the problem is introduced via an application [19]: Given a country with n-many towns, in how many ways can a railway network be constructed so that