-
A tree is labelled if each vertex is distinguished from each other.
-
Cayley’s Formula - The number of labelled trees in
vertices is . -
Pitman’s Proof relies on double counting. There are
to permute the number of vertices and say spanning trees on vertices. Another way to count is to add the edges one by one. If we have added
edges, we have a forest of trees. So there are ways to choose the next edge (choose the vertex and the tree to join it with). These two count the same thing to get -
Prufer’s proof establishes a bijection of trees with
vertices and the sequence of vertices. In the forward direction, at each step, choose the leaf with the smallest label, say
and the edge until we get two vertices. The sequence is the sequence of ‘s. In the reverse direction, at the
-th step, let be the smallest number not in the sequence. JJoin it with the vertex labelled . At the last step, join the remaining vertices.
-
-
-
Prufer’s proof gives us the Prufer Sequence, a sequence of
numbers that specify an -vertex labelled tree. -
(Theorem:
if and only if is not a leaf Proof: Eventually
must be connected to the other vertices at least once. By Prufer’s algorithm, it is not connected to any other vertex when it is the smallest number not yet considered that hasn’t appeared in the sequence. So, we know that it must never appear in the sequence, otherwise it will be connected more than once, hence it will no longer be a leaf.
-
Theorem: The probability that a vertex in a labelled tree is a leaf approaches
as . Proof: Apply the previous theorem and Cayley’s Formula. If the given vertex is
, then for it to be a leaf in some tree, it must not appear in the Prufer Sequence. There are such trees, and by Cayley’s Formula, there are trees. So take the limit
-
-
(Wilson e10.7) - Let
be the number of labelled trees on vertices. The following identity holds