Cayley's formula

Cayley's formula states that the number of trees on a fixed set of n labeled vertices is n^(n−2), for n ≥ 2.

Tree (graph theory): A connected undirected graph with no cycles. Cayley's formula counts trees, with each vertex carrying a distinct label.
Prüfer encoding: A procedure that converts a labeled tree into a sequence by repeatedly deleting its smallest-labeled leaf. Each deletion records one label, producing the sequence used to count trees.
Arthur Cayley: A British mathematician whose work included early enumeration of trees. The formula bears his name and appeared in his work on tree enumeration.
Random labeled tree: A tree chosen uniformly from all trees on a fixed labeled vertex set. Cayley's formula gives the size of the sample space for this model.
Unlabeled tree: A tree considered up to isomorphism, without distinct vertex labels. Cayley's formula distinguishes labels, whereas unlabeled-tree counts identify relabeled copies.
Labeled graph: A graph whose vertices are assigned distinct labels. Distinct vertex labels make different assignments count as different trees.
Prüfer decoding: A procedure that reconstructs a labeled tree from its Prüfer sequence. Unique reconstruction ensures that different sequences represent different trees.
Carl Wilhelm Borchardt: A German mathematician who published an early proof of the labeled-tree counting formula. His determinant-based proof preceded the familiar Prüfer-sequence argument.
Spanning tree: A subgraph that is a tree and includes every vertex of its connected graph. Trees counted by Cayley's formula are spanning trees of the complete graph.
Pólya enumeration theorem: A method for counting objects up to symmetry using group actions and cycle indices. It addresses symmetry-identified counts rather than Cayley's labeled count.

Linked from 3 pages