When a Tree Becomes a Graph
Minimal Change from Tree to Graph
A tree is a special type of graph. To convert a tree into a general graph, you just need to make a small change:
- Add one edge that creates a cycle.
Example:
Tree:
10
/ \
5 15
Graph (after adding edge 5 → 15):
10
/ \
5────15
Now there is a cycle (10 → 5 → 15 → 10), so it is a graph.
Benefits of Graphs over Trees
| Feature | Tree | Graph | Benefit of Graph |
|---|---|---|---|
| Cycles | Not allowed | Allowed | Models networks like roads, social connections |
| Multiple paths | One unique path between nodes | Many paths possible | Flexible routing and connectivity |
| Connectivity | Must be connected | Can be disconnected | Represents multiple separate networks |
| Root | Single root | No root required | Represents more general relationships |
| Edge directions / weights | Usually implicit / unweighted | Can have weights and directions | Models costs, priorities, traffic, etc. |
When to Convert a Tree into a Graph
- Network design – adding redundancy to avoid single points of failure.
- Social networks – friendships are not hierarchical, so a graph is better.
- Maps & routing – trees cannot model multiple routes; graphs can.
Example
Tree:
A
/ \
B C
Graph (add edge B → C):
A
/ \
B───C
Now there is a cycle: A → B → C → A. Not a tree anymore, but a graph.
Summary
- Minimal change to make a tree a graph: add an edge that creates a cycle.
- Graphs are more general than trees and can model real-world networks that trees cannot.