Forests and Their Components

Forests and Connected Components

A forest may consist of several separate pieces rather than one connected structure. To describe it precisely, we need to identify which vertices belong to the same piece. Those pieces are the graph’s connected components. Once the components are identified, a basic structural fact follows: each component of a forest is a tree. This lets us study a disconnected acyclic graph one connected piece at a time.

All graphs in this tutorial are finite and simple. A walk is a sequence of vertices \(v_0,v_1,\ldots,v_k\) in which consecutive vertices are adjacent; vertices may repeat. A path is a walk whose vertices are all distinct. A cycle of length \(k\ge 3\) is a sequence \(v_0,v_1,\ldots,v_k\) such that \(v_0=v_k\), the vertices \(v_0,\ldots,v_{k-1}\) are distinct, and consecutive vertices are adjacent. Thus, a cycle is not a path: its first and last vertices are the same.

Under these conventions, a single isolated vertex is a tree: it is nonempty and connected, and it has no cycle. The graph with no vertices has no connected components. It is a forest, since it contains no cycle.

Reachability Gives the Components

For vertices \(u\) and \(v\), say that \(u\) and \(v\) are connected by a path if there is a path from \(u\) to \(v\). This relation groups together exactly the vertices that can be reached from one another. A walk can be used in place of a path when checking reachability: if a walk repeats a vertex, the part between two occurrences can be removed, shortening the walk while keeping its endpoints. Repeating this deletion finitely many times gives a path.

Proof. Every vertex is related to itself by the path of length zero. If there is a path from \(u\) to \(v\), reversing its vertex sequence gives a path from \(v\) to \(u\), so the relation is symmetric. If there is a path from \(u\) to \(v\) and one from \(v\) to \(w\), joining the sequences gives a walk from \(u\) to \(w\). Removing repeated portions gives a path from \(u\) to \(w\), so the relation is transitive. It is therefore an equivalence relation, and its equivalence classes partition \(V(G)\).

Take one class \(C\). Any two vertices in \(C\) have a path between them. Every vertex on that path is also reachable from a vertex of \(C\), so it belongs to \(C\). Hence the subgraph induced by \(C\), denoted \(G[C]\), is connected. If a vertex outside \(C\) could be included in a connected subgraph containing \(C\), it would have a path to a vertex of \(C\), and would belong to the same class after all. Thus \(G[C]\) is maximal connected. Finally, an edge joining two different classes would itself give a path between its endpoints, contradicting that they lie in different classes. \(\square\)

The theorem gives a practical way to read components from an edge list. Start from a vertex and follow edges as far as possible; the vertices reached form one component. Then repeat with any vertex not yet reached. A vertex with no incident edges is not omitted: it forms a component by itself.

Why Components of a Forest Are Trees

Proof. Let \(G\) be a forest and let \(C\) be one of its connected components. By definition of component, \(G[C]\) is connected. If \(G[C]\) contained a cycle, the same cycle would be present in \(G\), contradicting that \(G\) is a forest. Therefore \(G[C]\) is connected and acyclic. It is nonempty because it contains the vertices of the component, so it is a tree.

Conversely, suppose every component of \(G\) is a tree. If \(G\) contained a cycle, all vertices on that cycle would be connected to one another by paths along the cycle. They would therefore lie in the same component. That component would contain a cycle, contradicting that it is a tree. Thus \(G\) contains no cycle and is a forest. If \(G\) has no vertices, it has no components and no cycles; the forest condition holds, and the statement that every component is a tree holds vacuously. \(\square\)

This equivalence is useful in both directions. When a graph is already known to be a forest, its components can be studied as trees. When checking whether a graph is a forest, one can instead examine each component for cycles. In either case, component membership comes from reachability, not from how the vertices happen to be arranged in a list.

Common Pitfall: Omitting Isolated Vertices

Consider \(F=(V,E)\) with \(V=\{1,2,3,4\}\) and \(E=\{12,23\}\). A mistaken component list might be “\(\{1,2,3\}\), so there is one component,” because the listed edges form one connected piece. That list omits vertex \(4\), even though \(4\) is part of the vertex set. Starting from \(4\), no edge can be followed, so its reachability class is \(\{4\}\). The correct components are \(\{1,2,3\}\) and \(\{4\}\). Both are trees, and \(F\) is a forest.

Component lists must cover the entire vertex set, not only the vertices that appear in an edge. A reliable final check is to verify that each vertex appears in exactly one listed component and that every edge has both endpoints in the same component.