Cayleyjeva formula

Cayleyjeva formula jedan je od temeljnih rezultata u teoriji grafova. Moderni iskaz formule nastao je 1889. od strane britanskog matematičara Arthura Cayleya. Formula tvrdi da je broj stabala s $n$ vrhova jednak $n^{n-2}$.

Potpuna lista stabala s dva, tri i četiri vrha.

Ovdje, dakako, ne uzimamo u obzir simetrije, zrcaljenja i slično pa će mnoga stabla biti izomorfna. Primjerice, broj stabala sa šest vrhova je 1296, no među njima samo je šest neizomorfnih.

Povijest

Formulu je otkrio Carl Wilhelm Borchardt 1860. i dokazao ju preko determinante. Formulu je 1889. proširio Cayley, uzevši u obzir stupnjeve grafa pa zato danas formula nosi njegovo ime.