Fórmula de Cayley

Lista completa de todos los árboles con 2,3 y 4 vértices etiquetados: $2^{2-2}=1$ árboles con 2 vértices, $3^{3-2}=3$ árboles con 3 vértices y $4^{4-2}=16$ árboles con 4 vértices.

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 $n^{n-2}$.

Equivalentemente, la fórmula cuenta el número de árboles de expansión de un grafo completo con vértices etiquetados.

Demostración

Se conocen muchas demostraciones para esta fórmula. Una demostración clásica utiliza el teorema de Kirchhoff. Las secuencias de Prüfer otorgan una demostración biyectiva de la fórmula de Cayley. 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 [pseudobosque]]s dirigidos.

Historia

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. Aunque Cayley referenció el artículo original de Borchardt, es el nombre de "fórmula de Cayley" el que se convirtió en estándar dentro del campo.

Referencias

• Aigner, Martin; Ziegler, Günter M. (1998). Proofs from THE BOOK. Springer-Verlag. pp. 141-146. .
• Borchardt, C.W. (1860). «Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung». Math. Abh. der Akademie der Wissenschaften zu Berlin: 1-20. 
• A. Cayley (1889). «A theorem on trees». Quart. J. Math 23: 376-378. 
• Shukla, Alok (2009). «A short proof of Cayley's Tree Formula». .