Counting Labeled Trees

How many trees are there with vertex set \([n]=\{1,2,\dots,n\}\)? Let \(T_n\) be this number. For \(n=1\), there is clearly only one tree. Also, for \(n=2\), there is only one tree, which is isomorphic to \(\bfK_2\). In determining \(T_3\), we finally have some work to do; however, there's not much, since all trees on \(3\) vertices are isomorphic to \(\bfP_3\). Thus, there are \(T_3=3\) labeled trees on \(3\) vertices, corresponding to which vertex is the one of degree \(2\). When \(n=4\), we can begin by counting the number of nonisomorphic trees and consider two cases depending on whether the tree has a vertex of degree \(3\). If there is a vertex of degree \(3\), the tree is isomorphic to \(\bfK_{1,3}\) or it does not have a vertex of degree three, in which case it is isomorphic to \(\bfP_4\), since there must be precisely two vertices of degree \(2\) in such a graph. There are four labelings by \([4]\) for \(\bfK_{1,3}\) (choose the vertex of degree three). How many labelings by \([4]\) are there for \(\bfP_4\)? There are \(C(4,2)\) ways to choose the labels \(i,j\) given to the vertices of degree \(2\) and two ways to select one of the remaining labels to be made adjacent to \(i\). Thus, there are \(12\) ways to label \(\bfP_4\) by \([4]\) and so \(T_4=16\).

To this point, it looks like maybe there's a pattern forming. Perhaps it is the case that for all \(n\geq 1\), \(T_n = n^{n-2}\). This is in fact the case, but let's see how it works out for \(n=5\) before proving the result in general. What are the nonisomorphic trees on five vertices? Well, there's \(\bfK_{1,4}\) and \(\bfP_5\) for sure, and there's also the third tree shown in . After thinking for a minute or two, you should be able to convince yourself that this is all of the possibilities. How many labelings by \([5]\) does each of these have? There are \(5\) for \(\bfK_{1,4}\) since there are \(5\) ways to choose the vertex of degree \(4\). For \(\bfP_5\), there are \(5\) ways to choose the middle vertex of the path, \(C(4,2)=6\) ways to label the two remaining vertices of degree \(2\) once the middle vertex is labeled, and then \(2\) ways to label the vertices of degree \(1\). This gives \(60\) labelings. For the last tree, there are \(5\) ways to label the vertex of degree \(3\), \(C(4,2)=6\) ways to label the two leaves adjacent to the vertex of degree \(3\), and \(2\) ways to label the remaining two vertices, giving \(60\) labelings. Therefore, \(T_5=125=5^3=5^{5-2}\).

It turns out that we are in fact on the right track, and we will now set out to prove the following:

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.