Trees Reference
Trees and Spanning Trees
Trees are connected graphs without cycles; their simple structure makes them useful for networks, hierarchies, and search procedures.
Solved Examples
Jump directly to a worked example by type.
Fact Table
| Idea | Meaning | Use or Check |
|---|---|---|
| Tree | A connected graph with no cycles. | There is exactly one simple path between any two vertices. |
| Edge count | A tree with $n$ vertices has $n-1$ edges. | Removing any edge disconnects a tree. |
| Rooted tree | A tree with one designated root that organizes vertices into levels. | Every nonroot vertex has one parent. |
| Leaf | A vertex with no children in a rooted tree. | In an unrooted tree, a leaf has degree 1. |
| Spanning tree | A tree containing every vertex of a connected graph. | It connects the vertices with the fewest possible edges. |
A Rooted Binary Tree
The root is A; B and C are its children, and D, E, F, and G are leaves.
Content Formulas
Tree Edge Count
$$|E|=|V|-1$$
Full Binary Tree
$$L=I+1$$
Spanning Tree
$$n\text{ vertices}\quad\Longrightarrow\quad n-1\text{ edges}$$
“Full” means each internal node has exactly two children. “Complete” describes a level-filling arrangement; the terms are not interchangeable.
Classic Examples
Count Tree Edges
A tree has 8 vertices. How many edges does it have?
Solution Steps
- Use the tree edge-count theorem.
$$|E|=|V|-1$$
$$|E|=8-1=7$$
Count Leaves in a Full Binary Tree
A full binary tree has 5 internal vertices. How many leaves and total vertices does it have?
Solution Steps
- Use the relation between leaves and internal vertices.
- Add the two counts.
$$L=I+1=5+1=6$$
$$|V|=I+L=5+6=11$$
Choose a Spanning Tree
A connected graph has four vertices arranged in a square, plus one diagonal. Give a spanning tree.
Solution Steps
- Keep all four vertices.
- Select three edges that connect them without making a cycle.
$$E_T=\{AB,BC,CD\}$$
All four vertices are connected and the selected edges contain no cycle, so these edges form a spanning tree.