Counting Vertices and Edges in Trees
What You'll Learn
You'll learn to prove and apply the fundamental relationship between vertices and edges in any tree: a tree with n vertices always has exactly n - 1 edges.
The Core Idea
Imagine building a tree by starting with a single vertex (a lone point). To add another vertex to your tree, you must connect it with exactly one edge—otherwise it wouldn't be connected, or you'd create a cycle (violating the tree definition). Each new vertex requires exactly one new edge to join the existing structure.
This pattern holds universally: every tree with n vertices contains precisely n - 1 edges.
Why This Works: Proof by Induction
Base case: A tree with 1 vertex has 0 edges. ✓ (1 - 1 = 0)
Inductive step: Assume any tree with k vertices has k - 1 edges. Now consider a tree T with k + 1 vertices. Since trees are connected and acyclic, they must have at least one leaf (a vertex of degree 1). Remove this leaf and its single edge to get a smaller tree T' with k vertices and k - 1 edges (by our assumption). When we restore the leaf and its edge, we have k + 1 vertices and (k - 1) + 1 = k edges. ✓
Practical Applications
- Verification: If someone claims a structure is a tree with 10 vertices but 11 edges, you immediately know it contains a cycle.
- Network design: Connecting n computers in a tree topology (no redundant paths) requires exactly n - 1 cables.
- Data structures: A binary search tree with 100 nodes contains exactly 99 parent-child links.
Key Takeaway: In any tree, the number of edges is always one less than the number of vertices (E = V - 1), a fundamental invariant that helps identify and analyze tree structures.