Day 61 — Trees

Updated

July 30, 2026

Day 61 — Trees

Stage VI · concept day
Goal: Master equivalent characterizations of trees with a proof cycle; rooted and binary trees; Catalan link; spanning trees; Cayley’s formula \(n^{n-2}\); Kruskal/Prim correctness idea via the cut property (no coding).

Why this matters

Trees are the minimally connected graphs—unique paths, hierarchical data, spanning backbones of networks, and the structure of recursive computation. Spanning trees and MST algorithms (Kruskal, Prim) are core CS; Cayley counts labeled trees. Binary tree shapes reconnect to Catalan numbers (Day 50).

Theory

Definition and characterizations

A tree is an undirected graph that is connected and acyclic.

Theorem (equivalent conditions). For a simple graph \(G\) with \(n\ge 1\) vertices, TFAE:

  1. \(G\) is a tree (connected + acyclic).
  2. \(G\) is connected and \(|E|=n-1\).
  3. \(G\) is acyclic and \(|E|=n-1\).
  4. Any two vertices are joined by a unique path.
  5. \(G\) is connected, but removing any edge disconnects \(G\) (every edge is a bridge).
  6. \(G\) is acyclic, but adding any missing edge creates exactly one cycle.

Proof cycle (sketch).

  • \((1)\Rightarrow(4)\): connected ⇒ path exists; two distinct paths would form a cycle—contradiction to acyclic.
  • \((4)\Rightarrow(1)\): unique path ⇒ connected; a cycle would give two paths between some pair.
  • \((1)\Rightarrow(2)\): induction on \(n\). \(n=1\): OK. Tree \(n\ge 2\) has a leaf (deg 1)—remove leaf, \(|E|\) drops by 1, IH on \(n-1\).
  • \((2)\Rightarrow(1)\): connected with \(|E|=n-1\) cannot have a cycle (cycle ⇒ can remove edge stay connected ⇒ would have connected spanning with fewer than \(n-1\) edges—contradiction to min \(n-1\)). More carefully: any connected graph has a spanning tree with \(n-1\) edges; if already \(|E|=n-1\) and connected, that spanning tree is \(G\) itself ⇒ acyclic.
  • \((3)\Rightarrow(1)\): acyclic with \(n-1\) edges: number of components in a forest is \(n-|E|=1\) ⇒ connected.
  • \((1)\Leftrightarrow(5),(6)\): standard using unique paths / bridges.

Forest: acyclic graph (components are trees). For a forest with \(n\) verts and \(c\) components: \(|E|=n-c\).

Leaves

Tree \(n\ge 2\) has at least two leaves (deg 1 vertices)—from handshaking: \(\sum\deg=2n-2\), if ≤1 leaf then sum ≥ \(2+2(n-1)\) or similar contradiction.

Rooted trees

Choose a root \(r\); orient edges away from (or toward) the root.
Parent / child / ancestor / descendant / depth / height standard.
Rooted structure is extra data beyond the undirected tree.

Binary trees and Catalan

Plane binary trees with \(n\) internal nodes (or full binary trees with \(n+1\) leaves, conventions vary): counted by Catalan \(C_n\).
Recursive structure: root + left subtree + right subtree gives Catalan convolution recurrence.

Binary search tree shapes on \(n\) keys: \(C_n\) plane binary trees (keys determine embedding once shape + inorder fixed).

Spanning trees

A spanning tree of connected \(G\) is a subgraph that is a tree on all vertices of \(G\) (connects all, \(|E|=n-1\), acyclic).

Existence: \(G\) connected ⇔ \(G\) has a spanning tree (grow acyclic connected subgraph maximally / delete edges on cycles).

Number of spanning trees \(\tau(G)\): Kirchhoff matrix-tree theorem (awareness); special cases below.

Cayley’s formula

Theorem (Cayley). Number of distinct trees on \(n\) labeled vertices is

\[ n^{n-2}. \]

Equivalently: number of spanning trees of \(K_n\) is \(n^{n-2}\).

Examples: \(n=2\): \(1\); \(n=3\): \(3\); \(n=4\): \(16\).
Prüfer code bijects labeled trees with sequences in \([n]^{n-2}\) (awareness).

Minimum spanning tree (MST) idea

Given connected weighted undirected \(G\) with edge weights, an MST is a spanning tree of minimum total weight.

Cut property (idea). For any partition of \(V\) into \(S\) and \(V\setminus S\), a lightest edge crossing the cut is safe to include in some MST (assuming distinct weights for simplicity).

Kruskal idea: sort edges by weight ascending; add next edge if it does not create a cycle (union-find culture). Correct by cut/cycle properties.

Prim idea: grow a tree from a start vertex; always add lightest edge from tree vertices to outside. Correct by cut property.

No coding today—hand-simulate on tiny graphs.

Cycle property (lite)

Heaviest edge on any cycle is not in any MST (distinct weights).

Worked examples

Example 1 — Check tree

Graph: \(n=5\), edges 4, connected, no cycle → tree.

Example 2 — Not tree

\(n=5\), edges 5, connected → has a cycle.

Example 3 — Forest

\(n=10\), \(c=3\) tree components: \(|E|=7\).

Example 4 — Unique path

In a tree, path between two vertices is unique—use to define ancestry in rooted tree.

Example 5 — Cayley

Labeled trees on 4 verts: \(4^{2}=16\).

Example 6 — Spanning trees of \(C_n\)

Any spanning tree of \(C_n\) omits exactly one edge: \(n\) spanning trees.

Example 7 — Spanning trees of \(K_4\)

\(4^{2}=16\) (Cayley).

Example 8 — Kruskal hand

Vertices \(A,B,C,D\). Weights: \(AB1,AC3,BC2,BD4,CD5\).
Order: AB, BC, AC (skip cycle), BD, CD skip. Tree: AB,BC,BD weight \(1+2+4=7\).

Example 9 — Prim hand

Start \(A\): take AB (1); from \(\{A,B\}\) take BC (2); from \(\{A,B,C\}\) take BD (4). Same tree.

Example 10 — Catalan binary trees

\(n=3\) internal: \(C_3=5\) shapes.

Example 11 — Leaf count

Path \(P_n\): 2 leaves. Star: \(n-1\) leaves.

Example 12 — Add edge

Tree + any new edge: unique cycle (along previous unique path + new edge).

Example 13 — Remove edge

Tree − any edge: exactly 2 components.

Example 14 — Rooted depths

Root a path at an end: height \(n-1\); root at center: smaller height.

Example 15 — Cut property

Partition \(\{A\}\) vs rest; lightest edge from \(A\) is in some MST—Prim’s first step.

Exercises

  1. State 4 equivalent characterizations of a tree.
  2. Prove: connected + \(|E|=n-1\) ⇒ acyclic (sketch).
  3. Prove: tree ⇒ unique paths.
  4. Forest: \(n=12\), \(|E|=9\) ⇒ how many components?
  5. Prove tree \(n\ge 2\) has ≥2 leaves.
  6. Cayley: number for \(n=5,6\).
  7. Spanning trees of \(C_6\).
  8. Kruskal on a 5-vertex weighted graph you draw (list edges).
  9. Prim on the same graph from two different starts—same weight?
  10. Why Kruskal rejects an edge: cycle check meaning.
  11. Binary trees: \(C_4=14\) shapes with 4 internal nodes.
  12. True/false: every tree is bipartite. (True—no odd cycle.)
  13. Center of a tree lite: one vertex or two adjacent.
  14. Count labeled stars on \(n\) verts: \(n\) (choose center).
  15. CS: DOM tree / filesystem tree—rooted.
  16. Prove \(|E|=n-c\) for forests.
  17. \(K_{2,3}\) spanning trees count (optional enumeration).
  18. If \(G\) has a cycle, spanning trees omit at least one cycle edge.
  19. MST unique if all weights distinct—true.
  20. Counterexample idea: equal weights, multiple MSTs.
  21. Prüfer: decode a small sequence (optional).
  22. Height vs number of nodes binary tree bounds.
  23. Challenge: Kirchhoff theorem statement for \(K_n\) recovers Cayley.
  24. Connected unicyclic (\(|E|=n\)) : not a tree; removing any cycle edge yields a tree.
  25. Portfolio: prove \((1)\Leftrightarrow(4)\Leftrightarrow(2)\) carefully in writing.

CS connection

  • File systems, DOM, ASTs, call trees.
  • Union-find / Kruskal for clustering and networks.
  • Routing trees / Steiner culture.
  • Decision trees in ML (rooted, not free trees).
  • Spanning tree protocol in networks (name drop).

Common pitfalls

Pitfall What to do instead
Connected ⇔ tree Need acyclic too
\(|E|=n-1\) alone Need connected or acyclic
Cayley for unlabeled trees Cayley is labeled
MST algorithms as black boxes Cut property intuition
Confusing rooted binary with free trees Root + plane embedding

Checkpoint

  • TFAE list for trees
  • Proof sketches unique path + edge count
  • Forest formula \(|E|=n-c\)
  • Cayley \(n^{n-2}\) with small checks
  • Kruskal/Prim hand sim + cut property sentence
  • Catalan–binary tree link
  • Exercises 1–15

Two personal takeaways:

  1. …
  2. …

Selected mini-solutions

  1. \(c=n-|E|=3\).
  2. \(5^3=125\); \(6^4=1296\).
  4. True.
  5. \(n\).
  6. Each component tree: sum \((n_i-1)=n-c\).
  7. Distinct weights ⇒ unique lightest choices—MST unique.

Deepening notes

Proof that trees have ≥2 leaves (\(n\ge 2\))

\(\sum\deg=2n-2\). If ≤1 leaf, then at most one deg-1 and others ≥2: sum ≥ \(1+2(n-1)=2n-1>2n-2\), contradiction. (If zero leaves all ≥2: sum ≥\(2n>2n-2\).)

Cayley small values

\(n\) \(n^{n-2}\)
1 1 (convention)
2 1
3 3
4 16
5 125

Kruskal vs Prim comparison

Kruskal Prim
Grows forest → tree single tree
Edge order global sorted lightest cut edge
Cycle check yes (union-find) automatic if only cut edges
Cut property both rely on it

Extra drills

D1. Prove unique path ⇒ acyclic.
D2. Forest edges for \(n=20\), \(c=5\).
D3. Cayley \(n=6\).
D4. Spanning trees of \(K_5\).
D5. Kruskal on 6 edges weights 1..6 of a graph you draw.
D6. Binary trees \(C_5=42\).
D7. Root path at center vs end—heights.
D8. Add edge to tree: describe the unique cycle.

Flash

Tree ⇔ connected acyclic ⇔ \(|E|=n-1\) connected; Cayley \(n^{n-2}\); MST cut property.

Exam drill block

E1. List 4 TFAE for trees; prove unique path ⇒ acyclic.
E2. Forest formula: \(n=30\), \(c=7\) edges?
E3. Cayley values \(n=2..6\).
E4. Spanning trees of \(C_8\) and of \(K_4\).
E5. Kruskal on weights you invent (5 verts, 7 edges)—trace.
E6. Prim from two starts—same total weight?
E7. Why every edge of a tree is a bridge.
E8. Binary plane trees: \(C_2,C_3,C_4\).
E9. Tree + new edge: prove exactly one cycle.
E10. True/false: (i) Cayley counts unlabeled trees (ii) MST unique if weights distinct (iii) every tree is bipartite.

Mini solutions

E2. \(23\).
E3. \(1,3,16,125,1296\).
E4. \(8\); \(16\).
E8. \(2,5,14\).
E10. F; T; T.

TFAE for trees (keep all four)

For a simple graph \(G\) on \(n\ge 1\) vertices, TFAE:

  1. \(G\) is connected and acyclic.
  2. \(G\) is connected and \(|E|=n-1\).
  3. \(G\) is acyclic and \(|E|=n-1\).
  4. Unique path between every pair of vertices.

Leaf count: \(n\ge 2\) ⇒ at least two leaves (deg-1 vertices).

Spanning tree facts

  • Connected \(G\) has a spanning tree; any spanning tree has \(n-1\) edges.
  • Adding any non-tree edge to a spanning tree creates exactly one cycle.
  • Number of distinct spanning trees of \(K_n\): Cayley \(n^{n-2}\) (labeled).
  • \(C_n\) has exactly \(n\) spanning trees (delete any one edge).

Cut property (idea for MST)

For a cut \((S,V\setminus S)\), a lightest edge across the cut is safe to include in some MST. Kruskal and Prim both rest on this; correctness proofs differ in bookkeeping (union-find vs growing a single tree).

Synthesis

Trees are the minimal connected graphs and the maximal acyclic ones. Characterizations interchange connectivity, acyclicity, edge count, and unique paths. Cayley counts labeled spanning trees of \(K_n\). MST algorithms (Kruskal/Prim) select light safe edges via the cut property. Plane binary trees reconnect to Catalan numbers.

S1. Prove unique path ⇒ acyclic and connected ⇒ tree.
S2. Kruskal trace on a 6-vertex weighted graph of your choice.
S3. Cold: Cayley \(n=5\); spanning trees of \(C_6\); leaves in any tree \(n\ge 2\).

S4. Prove every tree with \(n\ge 2\) has at least two leaves (handshaking).
S5. Why MST is unique when all edge weights are distinct (sketch).

Tomorrow

Day 62 — BFS & DFS: levels; shortest unweighted; discovery/finish; edge types awareness; hand simulation tables.