Cayley's formula: There are n-2 trees on n distinct vertices. 00 八入.八 38g9 3 63635363 人又 Arthur CayleyCayley’s formula for the number of trees Chapter 30 Arthur Cayley One of the most beautiful formulas in enumerative combinatorics concerns the number of labeled trees. Consider the set N = {1, 2,...,n}. How many different trees can we form on this vertex set? Let us denote this number by Tn. Enumeration “by hand” yields T1 = 1, T2 = 1, T3 = 3, T4 = 16, with the trees shown in the following table: 434 34 34 343434 3 4 3434 34 34 343434 3 4 1 1 12 12 2 1 2 1212 12 1 1 2 3 2 21212 1212 12 12 121212 1 2 1 3 3 3 Note that we consider labeled trees, that is, although there is only one tree of order 3 in the sense of graph isomorphism, there are 3 different labeled trees obtained by marking the inner vertex 1, 2 or 3. For n = 5 there are three non-isomorphic trees: 5 60 60 For the first tree there are clearly 5 different labelings, and for the second and third there are 5! 2 = 60 labelings, so we obtain T5 = 125. This should be enough to conjecture Tn = nn−2, and that is precisely Cayley’s result. Theorem. There are nn−2 different labeled trees on n vertices. This beautiful formula yields to equally beautiful proofs, drawing on a variety of combinatorial and algebraic techniques. We will outline three of them before presenting the proof which is to date the most beautiful of them all. Arthur Cayley There are nn￾2 trees on n distinct vertices. Cayley’s formula: