On Prufer codes
Tamás Fleiner · 2005
We give an alternative proof of Cayley's theorem on the number of labelled trees. Essentially, we use the Prufer code, but the method seems to be novel. trees on n labelled vertices. Prufer's proof (2) is based on the so-called Prufer code that describes each tree T by a sequence p(T) of n 2 labels. More precisely, we delete the smallest labelled leaves one by one and the label sequence of the neigbours of the first n 2 leaves is the (unique) Prufer code p(T) of T. From a Prufer-code p(T) of a tree, it is not so dicult to reconstruct T. But it takes some eort to prove that for any sequence s of n 2 labels, the graph G we ,,reconstruct is indeed a tree with p(G) = s. In section 2, we give an alternative coding of labelled trees that turns out to be closely related to the Prufer code and show a formula for the number of labelled trees with prescribed distance between two vertices.