Connected Components

Graph Theory · Axiom Academy

Understanding how graphs decompose into maximal connected subgraphs 1. Definition of Connected Component A connected component of a graph G is a maximal connected subgraph. This means: All vertices within the component are reachable from each other No vertex outside the component is reachable from vertices inside The component cannot be extended by adding more vertices while maintaining connectivity The term "maximal" is key to understanding components. A component is maximal because: It includes all vertices reachable from any starting vertex in the component Adding any vertex from outside would make it disconnected It represents the largest possible connected subgraph containing its vertices 3. Finding Components with BFS/DFS We can identify all components using graph traversal algorithms: Mark all vertices as unvisited For each unvisited vertex v: Start BFS or DFS from v All vertices reached form one component Repeat until all vertices are visited Both BFS and DFS work equally well. The time complexity is O(V + E) where V is vertices and E is edges. The number of connected components, denoted k(G), is an important graph invariant that tells us: k(G) = 1: The graph is connected k(G) > 1: The graph is disconnected k(G) = n: The graph has n isolated vertices (no edges) Connected components are closely related to graph connectivity: Connected graph: Has exactly one component (k(G) = 1) Disconnected graph: Has multiple components (k(G) ≥ 2)

This is the written version of the interactive lesson above. See the full Graph Theory course.