Fórmula de Cayley

En teoría de grafos, la fórmula de Cayley es un resultado llamado así en honor a Arthur Cayley, que establece que para cualquier entero positivo n, el número de árboles en n vértices etiquetados es

Una demostración clásica utiliza el teorema de Kirchhoff.

Otra demostración biyectiva, de André Joyal, encuentra una demostración uno-a-uno entre árboles de n vértices con dos nodos distinguibles y pseudobosques dirigidos.

La fórmula fue descubierta por Carl Wilhelm Borchardt en 1860, y demostrada a través de un determinante.

En una pequeña nota de 1889, Cayley extendió la fórmula en muchas direcciones, tomando en cuenta el grado de los vértices.