# Cayley’s Theorem

## Cayley’s Theorem

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

## Proof idea: Efficient storage of trees

= = = = = = + 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