Chapter 2 · Trees
Trees: Six Definitions of One Object
Equivalent characterisations, why each one is the right tool sometimes, and the leaf/degree counting identities.
On trees theorems have one extra hypothesis-free form: "connected and acyclic" appears in six disguises, and a good proof picks whichever is easiest to preserve.
For a simple graph T:
- T is connected and acyclic.
- T is connected and has n-1 edges.
- T is acyclic and has n-1 edges.
- Any two vertices are joined by exactly one path.
- T is connected, but deleting any edge disconnects it.
- T is acyclic, but adding any missing edge creates exactly one cycle.
The cycle of implications is short; each step is one idea. (1 ⇒ 2) Induct on n: a finite acyclic connected graph has a vertex of degree 1 (take a longest path — its endpoint cannot have another neighbour, or you get a cycle or a longer path), so delete it and apply the hypothesis. (2 ⇒ 3) Acyclic, else remove an edge of a cycle and stay connected, contradicting minimality of m for connectedness; formally use (2⇒5)⇒(1). (3 ⇒ 4): n-1 edges and acyclic implies connected (a forest with c components has n-c edges), so paths exist; uniqueness is acyclicity — two distinct paths between u,v would contain a cycle. (4 ⇒ 5) connected is free; deleting an edge of the unique u–v path separates them. (5 ⇒ 6) if T+e had two cycles sharing the new edge, the old graph would already have a cycle… contrapositive of "every edge is a bridge". (6 ⇒ 1) if T had a cycle, delete one of its edges: connectivity is unchanged, contradicting maximality of the acyclic graph. ∎
- Need an induction? Use (1): a leaf always exists.
- Need to count? Use (2)/(3): m = n-1 is the workhorse, e.g. the handshaking identity below.
- Need uniqueness of routes? Use (4): "the path is unique" turns min/max questions into "it must go through this vertex".
- Need a greedy? Use (5): every edge is a bridge, so any edge you delete must be re-added by something else.
#Counting identities
For a tree with L leaves and n vertices
- ∑v deg(v) = 2(n-1) (handshaking + (2)),
- L = 2 + ∑v:deg(v) ≥ 3 (deg(v) - 2) — so many high-degree vertices force many leaves,
- the average degree is 2 - 2/n, so a tree is always sparse: some vertex has degree 1 (a leaf) unless n ≤ 2,
- Δ ≤ 2 forces T to be a path, and L ≤ 2 does the same — these are the two ends of the identity above,
- rooting at r gives n-1 parent pointers; a tree on n labelled vertices has nn-2 shapes (Counting Trees: Cayley and Prüfer).
#Rooted trees and DFS order
Rooting is not extra structure, it is a choice of coordinates: every vertex except the root gets one parent, and subtrees become contiguous intervals in DFS order.
vector<int> par(n, -1), sz(n, 1), tin(n), tout(n), depth(n);
int timer = 0;
void dfs(int u) {
tin[u] = timer++;
for (int v : g[u]) if (v != par[u]) {
par[v] = u; depth[v] = depth[u] + 1;
dfs(v);
sz[u] += sz[v];
}
tout[u] = timer; // [tin, tout) = the subtree of u
}That interval property — v is in the subtree of u ⇔ tin(u) ≤ tin(v) < tout(u) — is the single most reused fact in tree algorithms; it is why Entry/Exit Times and the Euler Tour, LCA by Binary Lifting and Heavy-Light Decomposition all work.
Q: update every vertex in the subtree of u by +x; query the value at v. A: the subtree is an interval in tin order, so this is a range-add + point-query on an array: one Fenwick Tree (Binary Indexed Tree), O(log n) each, no new algorithm required.