Formule de Cayley

En mathématiques, et plus particulièrement en théorie des graphes, la formule de Cayley est un résultat sur les arbres du théoricien Arthur Cayley.

Elle affirme le résultat suivant :

Théorème — Le nombre d'arbres différents (non orientés) que l'on peut construire sur $n$ sommets numérotés, avec $n>1$ est égal à $n^{n-2}$.

Note : on parle aussi d'arbres décorés ou étiquetés pour dire que l'on identifie les sommets avec des couleurs, des nombres, etc. On parle aussi d'arbres de Cayley.

Liste complète des arbres à 2, 3 et 4 sommets.

Exemple

Pour l'exemple illustré ci-contre, on obtient les résultats suivants, en appliquant le théorème :

• $2^{2-2}=$ 1 arbre avec 2 sommets,
• $3^{3-2}=$ 3 arbres avec 3 sommets,
• $4^{4-2}=$ 16 arbres avec 4 sommets.

Historique

Cette formule a d'abord été découverte par Karl Wilhelm Borchardt en 1860^{[réf. nécessaire]} et prouvée à l'aide d'un déterminant. Dans une brève note en 1889, Arthur Cayley a étendu la formule dans plusieurs directions, en tenant compte du degré des sommets. Bien que Cayley ait mentionné le travail de Borchardt, le nom « formule de Cayley » est resté attaché à cette formule.

Démonstrations

On connaît plusieurs preuves remarquables de la formule de Cayley.

Une démonstration classique utilise le théorème de Kirchhoff, un théorème plus puissant qui donne le nombre d'arbres couvrants pour un graphe quelconque, alors que la formule de Cayley ne donne ce nombre que pour les graphes complets.

Une démonstration élégante est due à André Joyal. Pour compter les éléments de l'ensemble $\scriptstyle \ {\mathcal {C}}_{n}\$ des arbres numérotés à n sommets, il établit une bijection entre $\scriptstyle \ {\mathcal {C}}_{n}\times [\![1,n]\!]^{2}\$ et l'ensemble des applications de $\scriptstyle \ [\![1,n]\!]\$ dans $\scriptstyle \ [\![1,n]\!]\$, noté usuellement $\scriptstyle \ [\![1,n]\!]^{[\![1,n]\!]}\$. On a ainsi

$n^{n}\ =\ {\text{Card}}\ \left([\![1,n]\!]^{[\![1,n]\!]}\right)\ =\ {\text{Card}}\ \left({\mathcal {C}}_{n}\times [\![1,n]\!]^{2}\right)\ =\ n^{2}\,{\text{Card}}\ {\mathcal {C}}_{n}$

.

Une autre démonstration élégante est due à Heinz Prüfer. Le codage de Prüfer établit une bijection de $\scriptstyle \ {\mathcal {C}}_{n}\$ vers l'ensemble des (n-2)-uplets à valeurs prises dans l'intervalle $\scriptstyle \ [\![1,n]\!]\$, or le cardinal de ce dernier vaut $n^{n-2}$.

Une dernière démonstration élégante par double dénombrement a été apportée par Jim Pitman. Il compte de deux façons différentes les suites d'arêtes orientées formant des arbres couvrant les n sommets, et obtient ${\text{Card}}\ {\mathcal {C}}_{n}n!$ et $n^{n-2}n!$ arêtes orientées couvrant les n sommets. Il en déduit la formule de Cayley.

Bibliographie

• Martin Aigner et Günter M. Ziegler, Raisonnements divins, Springer-Verlag, 1998.
• (de) Borchardt, C.W., « Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung », Math. Abh. der Akademie der Wissenschaften zu Berlin,‎ 1860, p. 1–20
• (en) A. Cayley, « A theorem on trees », Quart. J. Math, vol. 23,‎ 1889, p. 376–378 (lire en ligne)
• (en) Alok Shukla, A short proof of Cayley's Tree Formula, 2009.