Tree (Graph Theory) — Definition, Formula & Examples
A tree is a connected graph that contains no cycles. Every pair of vertices is linked by exactly one path.
A tree is an undirected graph that is connected and acyclic. Equivalently, is connected and satisfies .
Key Formula
Where:
- = Number of edges in the tree
- = Number of vertices in the tree
How It Works
To determine whether a graph is a tree, check two conditions: the graph must be connected (every vertex is reachable from every other vertex), and it must contain no cycles. A useful shortcut is to verify that a connected graph on vertices has exactly edges — if so, it is necessarily a tree. Removing any single edge from a tree disconnects it, and adding any edge between two existing vertices creates exactly one cycle.
Worked Example
Problem: A connected graph G has 6 vertices and the edge set {(1,2), (1,3), (2,4), (3,5), (3,6)}. Is G a tree?
Check edge count: A tree on 6 vertices must have exactly 5 edges.
Check connectivity: Starting from vertex 1, you can reach 2 and 3 directly; from 2 you reach 4; from 3 you reach 5 and 6. All 6 vertices are reachable.
Check for cycles: No vertex can be reached by two distinct paths. For instance, the only path from 4 to 5 is 4-2-1-3-5. No cycle exists.
Answer: Yes, G is a tree because it is connected, has 5 edges on 6 vertices, and contains no cycles.
Why It Matters
Trees are the backbone of algorithms in computer science — binary search trees, spanning trees in network design, and decision trees in machine learning all rely on this structure. In a discrete mathematics or algorithms course, nearly every topic on graphs eventually references trees.
Common Mistakes
Mistake: Assuming any graph with is a tree.
Correction: The edge-count condition alone is not sufficient. The graph must also be connected. A disconnected graph with vertices and edges (a forest plus an extra edge forming a cycle in one component) is not a tree.