---
title: "Trees: Six Definitions of One Object"
summary: Equivalent characterisations, why each one is the right tool sometimes, and the leaf/degree counting identities.
difficulty: easy
tags: [trees, counting]
see: [trees/counting, trees/diameter]
---

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.

:::theorem title="Six equivalent statements (for |V| = n \u2265 1)"
For a simple graph $T$:
1. $T$ is connected and acyclic.
2. $T$ is connected and has $n-1$ edges.
3. $T$ is acyclic and has $n-1$ edges.
4. Any two vertices are joined by **exactly one** path.
5. $T$ is connected, but deleting any edge disconnects it.
6. $T$ is acyclic, but adding any missing edge creates exactly one cycle.
:::

:::proof
The cycle of implications is short; each step is one idea.
$(1 \Rightarrow 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 \Rightarrow 3)$ Acyclic, else remove an edge of a cycle and stay connected, contradicting minimality of $m$ for connectedness; formally use $(2\Rightarrow5)\Rightarrow(1)$.
$(3 \Rightarrow 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 \Rightarrow 5)$ connected is free; deleting an edge of the unique $u$–$v$ path separates them.
$(5 \Rightarrow 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 \Rightarrow 1)$ if $T$ had a cycle, delete one of its edges: connectivity is unchanged, contradicting maximality of the acyclic graph. ∎
:::

:::note title="Which one to keep in hand"
- 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
:::props title="For a tree with L leaves and n vertices"
- $\sum_v \deg(v) = 2(n-1)$ (handshaking + (2)),
- $L = 2 + \sum_{v:\deg(v) \ge 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 \le 2$,
- $\Delta \le 2$ forces $T$ to be a path, and $L \le 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 $n^{n-2}$ shapes (@trees/counting).
:::

## 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.

```cpp rooted-tree.cpp
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 \iff$ $\operatorname{tin}(u) \le \operatorname{tin}(v) < \operatorname{tout}(u)$ — is the single most reused fact in tree algorithms; it is why @trees/euler-tour, @lca/binary-lifting and @advanced-tree/hld all work.

:::example title="Subtree queries for free"
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 @structures/fenwick, $O(\log n)$ each, no new algorithm required.
:::

:::problems
- [[SPOJ PT07Z]] Longest path in a tree | https://www.spoj.com/problems/PT07Z/ | easy | diameter
- [[CF 519E]] A and B and Lecture Rooms | https://codeforces.com/problemset/problem/519/E | core | subtree sizes and LCA
- [[CSES 1674]] Subordinates | https://cses.fi/problemset/task/1674 | easy | subtree sizes, counted bottom-up
:::