do 10 if degree[j] = 1 then 11 Insert edge[i, j] into T 12 degree[i] ← degree[i] - 1 13 degree[j] ← degree[j] - 1 14 break At the end of this loop two nodes with degree 1 will remain (call them u, v). Lastly, add the edge (u,v) to the tree. 15 u ← v ← 0 16 for each node i in T 17 if degree[i] = 1 then 18 if u = 0 then 19 u ← i 20 else 21 v ← i 22 break 23 Insert edge[u, v] into T 24 degree[u] ← degree[u] - 1 25 degree[v] ← degree[v] - 1 26 return T Cayley's formula The Prüfer sequence of a labeled tree on n vertices is a unique sequence of length n − 2 on the labels 1 to n. For a given sequence S of length n–2 on the labels 1 to n, there is a unique labeled tree whose Prüfer sequence is S. The immediate consequence is that Prüfer sequences provide a bijection between the set of labeled trees on n vertices and the set of sequences of length n − 2 on the labels 1 to n. The latter set has size nn−2, so the existence of this bijection proves Cayley's formula, i.e. that there are nn−2 labeled trees on n vertices. Other applications Cayley's formula can be strengthened to prove the following claim: The number of spanning trees in a complete graph with a degree specified for each vertex is equal to the multinomial coefficient The proof follows by observing that in the Prüfer sequence number appears exactly times. Cayley's formula can be generalized: a labeled tree is in fact a spanning tree of the labeled complete graph. By placing restrictions on the enumerated Prüfer sequences, similar methods can give the number of spanning trees of a complete bipartite graph. If G is the complete bipartite graph with vertices 1 to n1 in one partition and vertices n1 + 1 to n in the other partition, the number of labeled spanning trees of G is , where n2 = n − n1. Generating uniformly distributed random Prüfer sequences and converting them into the corresponding trees is a straightforward method of generating uniformly distributed random labelled trees. References External links Prüfer code – from MathWorld Enumerative combinatorics Trees (graph theory)