Formal Tree Theory
A tree is a connected, acyclic undirected graph. Remarkably, this one definition is equivalent to several others you've already half-proven in earlier parts:
- Connected with exactly \(n-1\) edges (Part 1's induction proof).
- Acyclic with exactly \(n-1\) edges.
- Exactly one simple path exists between every pair of vertices.
- Connected, and removing any single edge disconnects it (Part 1's contrapositive example).
- Acyclic, and adding any single edge creates exactly one cycle.
A forest is a disjoint union of trees — acyclic, but not necessarily connected (exactly what a BFS or DFS traversal restarting from multiple unvisited vertices produces, from Parts 5–6).
Key Insight
Every non-trivial tree has at least two leaves (degree-1 vertices) — a fact used silently in the Part 1 induction proof that trees have \(n-1\) edges. Proof sketch: follow any path as far as it can go in either direction without repeating a vertex (impossible in a tree, since it's acyclic); both ends of that maximal path must be leaves, or the path could be extended further.
Rooted Trees and Arborescences
A rooted tree designates one vertex as the root, inducing parent/child and ancestor/descendant relationships (exactly the vocabulary the DFS Parenthesis Theorem in Part 6 relied on). A directed tree where every edge points away from the root is an out-tree or arborescence — the directed generalization of a spanning tree, and the natural output of BFS/DFS on a directed graph starting from a single source.
Counting Spanning Trees: The Matrix-Tree Theorem
How many distinct spanning trees does a graph have? For \(K_n\), Cayley's formula gives the surprisingly clean answer \(n^{n-2}\) (a fact usually proven via the Prüfer sequence bijection — precisely the encoding used to generate random trees in the Part 1 code example). For a general graph, Kirchhoff's Matrix-Tree Theorem (1847) gives the answer via linear algebra: build the Laplacian \(L = D - A\) from Part 3, delete any one row and the corresponding column, and the determinant of what remains equals the exact number of spanning trees.
Why a Determinant Counts Trees
This is one of the most delightful connections in all of graph theory: a purely combinatorial quantity (how many spanning trees exist) equals a purely algebraic quantity (a matrix determinant) computable in polynomial time via Gaussian elimination — even though naively enumerating spanning trees is exponential. Gustav Kirchhoff originally derived this in 1847 while studying electrical circuits, where spanning trees correspond to independent current loops — physics quietly anticipating a graph-theoretic theorem by nearly a century.
Minimum Spanning Trees in Context
Parts covering Kruskal's and Prim's algorithms already proved the cut property and cycle property and walked through both algorithms end to end — nothing to re-derive here. What's worth adding now that formal tree theory is established: an MST is, by the equivalent-definitions list above, simultaneously "connected with \(n-1\) edges" and "acyclic with \(n-1\) edges" among the spanning subgraphs of minimum total weight — both algorithms are really just two different constructive proofs that such a subgraph exists and can be found greedily.
Directed Minimum Spanning Trees
The directed analogue — a minimum-weight arborescence rooted at a given vertex — is not solved by a direct adaptation of Kruskal's or Prim's algorithm, because the cut property doesn't transfer cleanly to directed graphs. The Chu-Liu/Edmonds algorithm (discovered independently by Yoeng-jin Chu and Tseng-hong Liu in 1965, and by Jack Edmonds in 1967) instead greedily selects the cheapest incoming edge for every non-root vertex, then contracts any cycles this creates and recurses — a genuinely different strategy for a genuinely harder problem.
Classical Tree Algorithms
Several quantities describe a tree's overall shape, all computable in \(O(n)\) with two passes of BFS or DFS: the eccentricity of a vertex is its maximum distance to any other vertex; the diameter is the maximum eccentricity over all vertices (the longest shortest path in the tree); the center is the vertex (or two adjacent vertices) minimizing eccentricity — provably always the middle of a diameter path.
Finding a Tree's Diameter in Two BFS Calls
A classic trick avoiding an \(O(n^2)\) all-pairs computation: run BFS from any vertex \(u\), find the farthest vertex \(v\) it reaches — this \(v\) is provably one endpoint of some diameter path (a non-obvious but well-known lemma for trees, false in general graphs). Run BFS again from \(v\); the farthest vertex found this time is the other endpoint, and the distance between them is the diameter. Two BFS calls, \(O(n)\) total, no all-pairs computation needed.
Lowest Common Ancestor
The lowest common ancestor (LCA) of two vertices in a rooted tree is the deepest vertex that is an ancestor of both. A naive approach walks both vertices up to the root and compares paths, costing \(O(n)\) per query. Binary lifting precomputes each vertex's \(2^k\)-th ancestor for all \(k\) in \(O(n \log n)\), answering each subsequent query in \(O(\log n)\) — and an Euler-tour-plus-range-minimum-query formulation can push this to \(O(1)\) per query after \(O(n \log n)\) preprocessing.
Looking Ahead: Advanced Tree Queries
Beyond LCA, a family of techniques exists for answering complex path- and subtree-queries efficiently on trees: Heavy-Light Decomposition breaks a tree into \(O(\log n)\) contiguous chains, turning tree-path queries into segment-tree range queries; Euler-tour flattening turns subtree queries into array-range queries; rerooting DP computes an answer for every possible root in \(O(n)\) total rather than \(O(n^2)\); and centroid decomposition recursively splits a tree at balanced centroids to answer path-counting queries in \(O(n \log n)\). These become essential once we reach algorithmic optimization problems on trees in later parts.
Exercises
- Prove that a tree with \(n \geq 2\) vertices has at least two leaves, using the "follow a maximal path" argument sketched above.
- Verify Cayley's formula \(n^{n-2}\) by hand for \(n=3\) and \(n=4\) — list every distinct labeled spanning tree of \(K_3\) and \(K_4\).
- Compute the diameter and center of the path graph \(P_7\) (7 vertices in a line) using the double-BFS technique, and confirm the center is the middle vertex.
- Challenge: Implement the Matrix-Tree Theorem's determinant computation for a small graph (e.g., the 4-cycle from Part 3) and verify it correctly counts the number of spanning trees (the 4-cycle has exactly 4 distinct spanning trees — each formed by removing one of its 4 edges).
Conclusion & Next Steps
Trees now have a rigorous, multiply-equivalent definition, a way to count them exactly (the Matrix-Tree Theorem), a directed generalization (arborescences via Chu-Liu/Edmonds), shape-describing quantities (diameter, center), and a fast query structure (LCA via binary lifting) — with a forward look at the heavier machinery (HLD, centroid decomposition) still to come. Next, we look at two of the oldest questions in the entire field: when can you traverse every edge exactly once, and when can you visit every vertex exactly once?
Next in the Series
In Part 12: Eulerian & Hamiltonian Graphs, we return to the very first problem in graph theory's recorded history — the Seven Bridges of Königsberg — and the deceptively similar-sounding question that turns out to be far harder.