Cayley's Formula

Graph Theory · Axiom Academy

Counting Labeled Trees Through an Elegant Bijection Cayley's formula states that the number of labeled trees on n vertices is exactly n n-2 . This remarkable result connects tree counting to a simple exponential formula. For example, with 5 vertices, there are 5 5-2 = 5 3 = 125 different labeled trees! Let's verify Cayley's formula with small values of n to build intuition before exploring the general proof. n = 3: Formula predicts 3 1 = 3 trees n = 4: Formula predicts 4 2 = 16 trees Watch the animation to see all possible labeled trees for these small cases! The key to proving Cayley's formula is establishing a bijection (one-to-one correspondence) between labeled trees on n vertices and sequences of length n-2 where each element is from 1, 2, ..., n . Since there are exactly n choices for each of the n-2 positions in the sequence, there are n n-2 possible Prufer sequences, matching Cayley's formula! 4. Encoding a Tree as a Prufer Sequence To convert a labeled tree into its Prufer sequence, we repeatedly remove the leaf with the smallest label and record its neighbor. Find the leaf (degree 1 vertex) with the smallest label Add its unique neighbor to the sequence Repeat until only 2 vertices remain Watch as we encode a tree step by step into its Prufer sequence! 5. Applications and Significance Cayley's formula and Prufer sequences have important applications throughout mathematics and computer science. Network Design: Counting possible network topologies

This is the written version of the interactive lesson above. See the full Graph Theory course.