Formal Tree Theory
Trees: Connected, but with No Loops
A tree is an undirected graph that is connected and has no cycles.
A useful way to think about a tree is: it has just enough edges to keep every vertex connected, but no unnecessary edges.
A tree is minimally connected: remove any edge and something becomes disconnected. But it is also maximally acyclic: add one new edge between existing vertices and you create a cycle.
In the graph above, every vertex can reach every other vertex, so the graph is connected. At the same time, there is no way to follow edges and return to your starting point without reusing an edge — so there are no cycles.
Exactly One Path Between Every Pair
One of the most important properties of a tree is that between any two vertices there is exactly one simple path.
There is exactly one simple route from u to v.
Why can't there be two different paths? Because if two different simple paths connected the same pair of vertices, those paths would eventually join together and form a cycle — which a tree cannot contain.
Why does a tree have \(n-1\) edges?
If a tree has \(n\) vertices, then it always has exactly:
One intuitive way to see this is to build a tree one vertex at a time. Start with one vertex and no edges. Every time you add a new vertex, you need exactly one new edge to connect it to the existing tree.
0 edges
1 edge
2 edges
\(n-1\) edges
Different Ways to Recognize a Tree
These properties may look different, but for an undirected graph with \(n\) vertices they all describe the same structure: a tree.
- DefinitionConnected and acyclic.
- Edge CountConnected with exactly \(n-1\) edges.
- No CyclesAcyclic with exactly \(n-1\) edges.
- Unique PathsExactly one simple path exists between every pair of vertices.
- Remove EdgeRemoving any edge disconnects the graph.
- Add EdgeAdding an edge between two non-adjacent vertices creates exactly one cycle.
Every Edge Matters
Since a tree has no alternative route between two vertices, every edge acts like a bridge.
Remove any one of those edges, and the tree splits into two separate components.
One Extra Edge Creates a Cycle
Suppose vertices u and v are already in a tree. There is already exactly one path connecting them.
If we add a new edge directly between u and v, that new edge together with the existing path forms exactly one cycle.
Leaves: The Ends of a Tree
A leaf is a vertex with degree \(1\): it is connected to the rest of the tree by exactly one edge.
Vertex L has only one incident edge, so \(\deg(L)=1\).
Key Insight: Every Non-Trivial Tree Has at Least Two Leaves
Imagine starting somewhere in a tree and following a simple path as far as possible without repeating a vertex.
Both ends of this maximal path must be leaves. If an endpoint had another unused neighbor, we could extend the path farther — contradicting the fact that the path was maximal. Therefore every tree with at least two vertices has at least two leaves.
Forests: Several Trees
A forest is simply an acyclic graph that does not have to be connected.
In other words, each connected component of a forest is itself a tree.
If BFS or DFS finishes exploring one connected component and then restarts from another unvisited vertex, each traversal produces a tree. Together, those traversal trees form a spanning forest.
Rooted Trees
An ordinary tree has no special starting vertex. A rooted tree chooses one vertex and calls it the root.
Once a root is chosen, the tree naturally gains hierarchical relationships such as: parent, child, ancestor, and descendant.
- RootThe distinguished starting vertex. Here, R is the root.
- Parent / ChildA is a parent of C, and C is a child of A.
- AncestorR is an ancestor of C, while C is a descendant of R.
Directed Trees and Arborescences
If we direct every tree edge away from the root, we obtain an out-tree, commonly called an arborescence.
Every reached vertex except the root has exactly one parent edge, and all tree edges point outward from the root.
BFS and DFS naturally produce this kind of structure on the vertices they reach from a source: whenever a vertex is discovered for the first time, the edge that discovered it becomes its parent edge.
Easy Way to Remember Trees
- ConnectedEverything can reach everything.
- No CyclesThere are no loops.
- Unique PathsExactly one route exists between vertices.
- \(n-1\) EdgesJust enough edges to stay connected.
Spanning Trees: Keep Every Vertex, Remove the Extra Connections
A spanning tree of a connected undirected graph is a subgraph that keeps every vertex of the original graph, but keeps only enough edges to form a tree. In other words, it connects all the vertices without containing a cycle.
What Does “Spanning” Mean?
Spanning does not mean “use every edge.” It means the tree spans all the vertices. If the original graph is \(G=(V,E)\), a spanning tree has the same vertex set \(V\), but uses only a subset of the edges: \(T=(V,E_T)\) where \(E_T \subseteq E\).
Because a spanning tree is still a tree, all the tree properties from the previous section apply immediately. For a graph with \(n\) vertices, any spanning tree must:
- Include all \(n\) vertices from the original graph.
- Be connected — every vertex must still be reachable from every other vertex.
- Be acyclic — none of the retained edges may form a cycle.
- Contain exactly \(n-1\) edges.
One Graph Can Have Many Spanning Trees
Start with the weighted graph on the left. The two graphs to its right keep every vertex but discard different edges. Both remain connected and contain no cycle, so both are valid spanning trees.
The important point is that a spanning tree is usually not unique. The original graph may contain many different ways to choose \(n-1\) edges while preserving connectivity. In the example, \(T_1\) and \(T_2\) are both spanning trees even though they use different edges and have different total weights.
Quick Test: Is It a Spanning Tree?
Ask two questions: (1) Does it include every vertex of the original graph? (2) Do the chosen edges form a tree? If both answers are yes, it is a spanning tree. For a connected graph, the second check can often be shortened to: “is it connected and does it have exactly \(n-1\) edges?”
A connected graph always has at least one spanning tree: repeatedly remove an edge from any cycle. Removing a cycle edge cannot destroy connectivity because the rest of that cycle still provides an alternate route. When no cycles remain, what is left is connected and acyclic — a spanning tree. A disconnected graph has no spanning tree; its analogous structure is a spanning forest, with one tree for each connected component.
This raises the natural question for a weighted graph: if several spanning trees are possible, which one should we choose? The two spanning trees above already hint at the answer — \(T_1\) costs 9 while \(T_2\) costs 6. Choosing the cheapest possible spanning tree leads directly to the minimum spanning tree problem.
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
A minimum spanning tree (MST) is a spanning tree whose total edge weight is as small as possible among all spanning trees of the graph. If \(T=(V,E_T)\), its total weight is \(w(T)=\sum_{e \in E_T} w(e)\), and an MST minimizes this sum while still spanning every vertex.
Spanning Tree vs. Minimum Spanning Tree
A spanning tree asks: “Can I connect every vertex with no cycles?” An MST adds one more requirement: “Among all such trees, which has the smallest total cost?” In the example above, both \(T_1\) and \(T_2\) span the graph, but \(T_2\) has the smaller total weight (6 rather than 9); in fact, it is an MST of that graph.
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. Kruskal's and Prim's algorithms are really two different constructive ways to find that cheapest spanning tree 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.