Structural Induction on Trees and Graphs
You'll learn how to prove properties about recursively built structures like trees and graphs using a variation of strong induction.
The Core Idea
Mathematical induction works on natural numbers because each number is built from previous ones. But what about structures like binary trees or connected graphs? These are often defined recursively—a tree is either a leaf or a node with child trees. Structural induction adapts the inductive principle to prove properties about these recursively defined objects.
Instead of proving something for "n" and then "n+1," you prove:
- Base case(s): The property holds for the simplest structures (e.g., a single node, an empty tree)
- Inductive step: If the property holds for all component parts of a structure, it holds for the combined structure
This mirrors strong induction because you assume the property for all smaller sub-structures, not just one predecessor.
How It Works
For a binary tree, you might prove:
- Base: The property holds for a leaf node
- Inductive: Assume it holds for left subtree L and right subtree R (the "smaller" pieces). Now prove it holds for the tree with root connected to L and R.
For graphs, you might build them by adding edges or vertices, proving that if a property holds before the addition, it holds after.
The key insight: just as natural numbers are built by "+1," complex structures are built by recursive construction rules. Structural induction follows those same rules backward.
Example Sketch
Claim: Every binary tree with n nodes has exactly n−1 edges.
- Base: One node, zero edges. ✓
- Inductive: Tree T has root with left subtree (ℓ nodes, ℓ−1 edges) and right subtree (r nodes, r−1 edges). Total nodes: 1+ℓ+r. Total edges: 2 (to children) + (ℓ−1) + (r−1) = ℓ+r = (1+ℓ+r)−1. ✓
Key Takeaway: Structural induction extends strong induction to recursively defined structures by proving base cases and showing that truth for components implies truth for the whole.