Counting Trees Examples

Graph Theory · Axiom Academy

EXAMPLE Counting Trees Examples Learn to enumerate labeled trees and work with Prüfer sequences Excellent work! You've mastered tree enumeration and Prüfer sequences. Here's what we learned: Complete Enumeration: For small values of n, we can systematically draw all labeled trees by considering different structural patterns (stars, paths, and intermediate forms). Cayley's Formula: The number of labeled trees on n vertices is exactly n n-2 , providing a powerful closed-form count without enumeration. Prüfer Sequences: Every labeled tree on n vertices corresponds to a unique sequence of length n-2 with values in 1, 2, ..., n , establishing a bijection. Encoding Process: Repeatedly remove the smallest leaf and record its neighbor's label until two vertices remain. Decoding Process: Use degree sequence tracking to systematically reconstruct the unique tree from a Prüfer sequence. Prüfer sequences provide both a proof of Cayley's formula and a practical tool for generating random labeled trees!

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