Cayley's Theorem

We will now look a very important theorem which tells us the number of different tree graphs on $n$ labelled vertices.

Theorem 1 (Cayley's Theorem): For each $n ≥ 1$, there are precisely $n^{n-2}$ tree graphs (graphs that are acyclic and connected) on $n$ labelled vertices.

• Proof: Suppose that $n = 1$. Trivially there is $1$ tree on $1$ labelled vertex, so Cayley's theorem is true. Now suppose $n = 2$. Once again, trivially there is only $1$ tree on $2$ labelled vertices.

• Now suppose $n \geq 3$. We know that the Prüfer sequence for each of these trees is unique, and in general, any Prüfer sequence for a tree on $n$-vertices can be represents as $\left\{a_1, a_2, ..., a_{n-2} \right\}$. Each $a_i$ can be exactly one of $1, 2, ..., n$. Since there are $n-2$ terms in the Prüfer sequence, then the number of unique Prüfer sequences on $n$-vertices is $n^{n-2}$, which is the number of labelled trees on $n$ vertices. $\blacksquare$

Let's look at an example. Suppose we want to list all of the possible trees on $3$ labelled vertices. By Cayley's Theorem, there will be precisely $3^{3-2}$ trees, or simply $3$ trees to consider as shown below:

Unfortunately, the number of labelled trees on more vertices becomes very large fast. For example, the number of trees of $8$ labelled vertices is $8^6 = 262144$, which is too many to show as an example.