Forest

Definition

A forest is a disjoint union of trees, meaning it is a graph without cycles where each connected component is a tree. Forests are acyclic and can consist of one or more isolated trees.

5 Must Know Facts For Your Next Test

1. 1. A forest is an undirected graph with no cycles.
2. 2. Every tree is a type of forest, but not all forests are single trees.
3. 3. The number of edges in a forest with \( n \) vertices and \( k \) components is \( n - k \).
4. 4. A forest with \( n \) vertices has at most \( n-1 \) edges.
5. 5. Each connected component of a forest must be a tree.

Review Questions

• 1. What distinguishes a forest from other types of graphs?
• 2. How can you determine the number of edges in a forest given the number of vertices and components?
• 3. Why is every tree considered a forest?

Related terms

Tree: A connected acyclic graph with \( n \) vertices and \( n-1 \) edges

Graph: A collection of vertices (or nodes) and edges (connections between pairs of vertices)

Cycle: A path in which the first and last vertices are the same, forming a closed loop