Math 240 Discrete Mathematics - Cayley's Theorem

Cayley’s Theorem

Cayley’s Theorem

The number of labelled trees with $n$ vertices is $n^{n-2}$

Proof idea: Efficient storage of trees

Adjacency matrix

.. image:: |filename|/math240res/images/adjascent-list-graph.png

= = = = = = + 1 2 3 4 5 1 0 1 1 0 0 2 1 0 1 0 0 3 1 1 0 1 0 4 0 0 1 0 0 5 0 0 0 0 0 = = = = = =

Labels {0,1,2,…n-1}

Edge list

.. image:: |filename|/math240res/images/edgelist.png

4 1 1 3 0 0

3 3 5 0 2 6

2(n-1) numbers

$(n2){n-1} = n^{2(n-1)} $ ways to write such an “edge list”. so $ {\leq} n^{2(n-1)} labelled trees with $n$ vertices.

Parent code:

Pick 0 as root Each vertex except $0$ has a parent. $p(6)=0$, $p(1)=3$, write down all the parents.

1 2 3 4 5 6

3 0 0 3 1 0

No need to store the top line. So the number of parent codes is $n^{n-1}$

Problem: not every list of $n-1$ numbers from $\{0,1,\dots,n-1\}$ represents a tree, so only get upper bound.

Prufer Code

Like parent but, but instead of taking vertices in order 1,2,3,4,..,n-1, always take the smallest labelled leaf (ignoring 0)

This example is on the textbook page 147

1 3 4 5 6 7 8 9 [2] <–number

6 0 2 6 2 9 9 2 [0] <–parent

Top row: ${\leq}(n-1)! $

Bottom row: ${\leq}n^{n-2}$

Bound: $(n-1)!\cdot n^{n-2}$

Claim: the bottom row determines the top row

Example: Consider a tree whose Prufer code has bottom row::

2 4 0 3 3 1 0

We know automatically that vertex labels are {0,1,2,…,7}

First entry on the top row is not 1,3,4 because they are parents later on. And 5 is a leaf because it doesn’t appear later on in the bottom row.

The first row has entries::

5 2 4 6 7 3 1

Together::

2 4 0 3 3 1 0 5 2 4 6 7 3 1

Theorem

The Prufer code is a bijection between labelled trees with $n$ vertices, and sequences of $n-2$ numbers from {0,1,…n-1}. So the number of such trees is $n^{n-2}$ which is Cayley’s Theorem.