Secuencia de Prüfer

, y puede ser generada por un algoritmo iterativo simple.

Las secuencias de Prüfer fueron usadas por primera vez por Heinz Prüfer para probar la fórmula de Cayley en 1918.

[1]​ La secuencia de Prüfer de un árbol etiquetado se puede generar eliminando iterativamente los vértices del árbol hasta que queden solamente dos vértices.

Específicamente, consideremos un árbol etiquetado T con vértices {1, 2, ...,

En el paso i, eliminar la hoja con la menor etiqueta y hacer que el i-ésimo elemento de la secuencia de Prüfer sea la etiqueta del nodo vecino de la hoja eliminada.

La secuencia del árbol etiquetado es claramente única y tiene longitud

Consideremos la ejecución del algoritmo descrito anteriormente sobre el ejemplo mostrado a la derecha.

Inicialmente, el vértice 1 es la hoja con la menor etiqueta, luego es la primera en ser removida y se anota un "4" en la secuencia de Prüfer.

Los vértices 2 y 3 son removidos a continuación, luego se agrega un "4" dos veces más.

El grado de cada nodo será igual al número de veces que éste aparezca en la secuencia más 1.

Por ejemplo, en pseudo-código: Luego, por cada número a[i] en la secuencia, encontrar j, el primer nodo con grado 1 y cuya etiqueta es la menor y agregar la arista (j, a[i]) al árbol.

Decrementar los grados de a[i] y de j. En pseudo-código: Al finalizar este bucle quedan dos nodos con grado 1 (llamémoslos u, v).

Por último, agregar la arista (u,v) al árbol.

existe un único árbol etiquetado cuya secuencia de Prüfer es