Formula di Cayley

Lista completa degli alberi etichettati con 2, 3 e 4 vertici.

La formula di Cayley è usata in matematica nella teoria dei grafi. Essa afferma che il numero di alberi ricoprenti che si possono costruire su un grafo con $n$ vertici etichettati (con $n>1$), è uguale a $n^{n-2}$.

Si parla di vertici "etichettati" quando sono identificati tramite numeri, colori, ecc. Gli alberi con vertici etichettati sono chiamati a volte alberi di Cayley.

Per esempio, per alberi con 2, 3 e 4 vertici la formula fornisce i seguenti risultati:

• $A_{2}=2^{2-2}$   (1 albero con 2 vertici);
• $A_{3}=3^{3-2}$   (3 alberi con 3 vertici);
• $A_{4}=4^{4-2}$   (16 alberi con 4 vertici).

Storia

Questa formula fu scoperta dal tedesco Carl Borchardt nel 1860, che la dimostrò tramite un determinante.
Nel 1889 l'inglese Arthur Cayley estese la formula, tenendo conto anche del grado (cioè della molteplicità) dei vertici. Cayley riconobbe a Borchardt la paternità della formula originale, ma in seguito il nome « formula di Cayley » è entrato nell'uso.

Dimostrazioni

Esistono diverse dimostrazioni della formula di Cayley. Un esempio classico utilizza il teorema di Kirchhoff, applicabile ad un grafo qualunque, mentre la formula di Cayley si limita ai grafi completi.

Nel 1918 Heinz Prüfer ne diede una dimostrazione tramite il codice di Prüfer, che fornisce una descrizione compatta e univoca albero con $n$ vertici etichettati tramite una successione del tipo

$P=(x_{1},x_{2},x_{3},\ldots ,x_{n-2}).$

Ad ogni successione $P$ corrisponde uno e un solo albero con $n$ vertici etichettati.