Connected Component — Definition, Formula & Examples

A connected component is a piece of a graph in which every vertex can reach every other vertex through some path, and no additional vertices from the rest of the graph can be added without breaking this property.

A connected component of an undirected graph $G = (V, E)$ is a maximal subset $S \subseteq V$ such that for every pair of vertices $u, v \in S$ , there exists a path from $u$ to $v$ in $G$ , together with all edges of $G$ whose endpoints both lie in $S$ . Equivalently, connected components are the equivalence classes of the reachability relation on $V$ .

How It Works

To find the connected components of a graph, start at any unvisited vertex and explore all vertices reachable from it using BFS or DFS. Every vertex you visit belongs to the same component. Mark those vertices as visited, then repeat from any remaining unvisited vertex. Each round of exploration produces one connected component. A graph with exactly one connected component is called a connected graph.

Worked Example

Problem: Find all connected components of the graph

G

with vertices

\{1, 2, 3, 4, 5, 6\}

and edges

\{(1,2),\,(2,3),\,(4,5)\}

Step 1: Start at vertex 1. Explore its neighbors: vertex 2 is adjacent. From vertex 2, vertex 3 is adjacent. No more reachable vertices.

C_1 = \{1, 2, 3\}

Step 2: Move to the next unvisited vertex, 4. Vertex 5 is adjacent to 4. No more reachable vertices.

C_2 = \{4, 5\}

Step 3: Vertex 6 remains unvisited and has no edges, so it forms its own component.

C_3 = \{6\}

Answer: The graph has three connected components:

\{1,2,3\}

\{4,5\}

, and

\{6\}

Why It Matters

Connected components appear whenever you need to determine which parts of a network can communicate. In computer science, finding connected components is a fundamental step in algorithms for image segmentation, social-network clustering, and detecting isolated subnetworks. Many graph algorithms (shortest path, spanning tree) require the graph to be connected, so identifying components is often a necessary first check.

Common Mistakes

Mistake: Forgetting the 'maximal' requirement and listing a proper subset of a component as a component itself.

Correction: A connected component must include every vertex reachable from any vertex in the set. If you can still add a vertex that is connected to the group, you have not yet identified the full component.