Connectivity and Components

Connected components are computed by standard graph-search algorithms (breadth-first and depth-first search), which run in linear time in the size of the graph; this makes connectivity-checking one of the cheapest nontrivial questions in all of algorithmic graph theory, and it underlies union-find data structures used throughout computer science. In network engineering, checking whether a communication network stays connected after link failures is literally the question "is $c(G)$ still $1$?" In social network analysis, connected components identify separate communities or clusters that share no path of acquaintance. In image processing, "connected component labeling" segments a binary image into blobs of touching pixels, a direct pixel-grid instance of this theorem. In percolation theory and statistical physics, the emergence of a single giant connected component in a random graph as edge density increases is a phase transition studied via exactly the equivalence-class machinery proved here. In cryptographic protocol design and distributed computing, connectivity of the underlying communication graph is a baseline assumption for consensus and broadcast protocols to even be possible. And in pure graph theory, connectivity is the natural first step before finer invariants: it sets up Vertex and Edge Connectivity (how many vertices or edges must be removed to disconnect a graph) and is exactly the hypothesis needed to state the defining property of trees as minimal connected graphs.

Ask the tutor: How do breadth-first search and depth-first search each compute the connected components of a graph, and why do both run in linear time?

Picture a graph as a collection of islands (vertices) linked by bridges (edges). The relation $u \sim v$ says: you can walk from island $u$ to island $v$ crossing only bridges that exist. If every island can reach every other island, the whole archipelago is "one piece" — connected. If not, the archipelago naturally splits into clusters of islands that are internally fully reachable but mutually unreachable across clusters. Those clusters are the connected components. The key mental habit to build is that reachability behaves like an equivalence relation, the same kind of object as "same remainder mod $n$" or "same parity." Once you see $\sim$ as an equivalence relation, the whole theory of components becomes a special case of a fact you already know: an equivalence relation partitions a set into disjoint classes. The only graph-theoretic work is showing that walks compose (to get transitivity), reverse (to get symmetry), and that a single vertex reaches itself (reflexivity).

Example 1: Computing components of an explicit graph. Let $G$ have vertex set $V = \{1,2,3,4,5,6,7,8\}$ and edge set

There is no vertex numbered as isolated by omission — vertex $8$ appears only via edge $\{7,8\}$, and all of $1$–$8$ appear in some edge, so no vertex is isolated. We compute $\sim$-classes directly. Start with vertex $1$: it is joined to $2$ and $3$ directly; $2$ is joined to $3$; $3$ is joined to $4$. So $1 \sim 2$ (edge), $1 \sim 3$ (edge), and $1 \sim 4$ via the walk $1,3,4$. No edge touches $\{5,6,7,8\}$ from $\{1,2,3,4\}$, so we cannot extend further from this side. Hence one candidate class is $\{1,2,3,4\}$. Check maximality/closure: every edge with an endpoint in $\{1,2,3,4\}$ is $\{1,2\},\{2,3\},\{3,1\},\{3,4\}$ — all four endpoints stay inside $\{1,2,3,4\}$. So this is a full equivalence class (no missing outgoing edges), giving component $C_1$ with vertex set $\{1,2,3,4\}$ and edge set $\{\{1,2\},\{2,3\},\{3,1\},\{3,4\}\}$: a triangle $1,2,3$ with a pendant edge to $4$. Now start from $5$: $5 \sim 6$ (edge), $5 \sim 7$ (edge), $6\sim 7$ (edge), and $7 \sim 8$ (edge). So $\{5,6,7,8\}$ all lie in one class. Checking closure: all edges touching this set are $\{5,6\},\{6,7\},\{7,5\},\{7,8\}$, with both endpoints inside $\{5,6,7,8\}$; no edge leaves this set. This is the second component $C_2$: a triangle $5,6,7$ with a pendant edge to $8$. By Theorem part (4), $\{1,2,3,4\}$ and $\{5,6,7,8\}$ partition $V$ (indeed $4+4=8=|V|$, and they are disjoint), so these are all the components: $c(G) = 2$, hence $G$ is not connected. Notice the asymmetry deliberately built in: $C_1$'s pendant hangs off the triangle vertex $3$, while $C_2$'s pendant hangs off vertex $7$ — the two components are isomorphic as abstract graphs but attached to differently labeled anchor vertices, illustrating that component computation is about the labeled structure, not just isomorphism type.

Example 2: Verifying connectivity via path search, and reconstructing components after an edge deletion. Let $G$ have vertex set $\{a,b,c,d,e,f\}$ and edges

Is $G$ connected? We build a class starting at $a$: $a \sim b$ (edge), $b \sim c$ (edge), so $a \sim c$ by transitivity; $c \sim d$ (edge) so $a \sim d$; $d \sim e$ (edge) so $a \sim e$ (also directly by the edge $\{a,e\}$, consistent); $c \sim f$ (edge) so $a \sim f$. Every vertex of $V$ is reachable from $a$, and $|V| = 6$ vertices are all accounted for, so $\sim$ has a single class $V$ itself. By Theorem part (4), $G$ is connected, $c(G) = 1$. As a check via part (2), exhibit an explicit path (not just a walk) from $a$ to $f$: $a, b, c, f$ — three edges, all in $E$, no repeated vertices. Good, this confirms $a \sim f$ concretely. Now delete the edge $\{c,d\}$ from $G$, forming $G' = G - \{c,d\}$. Recompute components. Starting from $a$: $a \sim b$, $a\sim e$ (direct edge), $b \sim c$ so $a \sim c$, $c \sim f$ so $a \sim f$. So far the class of $a$ contains $\{a,b,c,e,f\}$ — but does it contain $d$? The only edges touching $d$ in the original graph were $\{c,d\}$ and $\{d,e\}$; we removed $\{c,d\}$, but $\{d,e\}$ remains in $G'$. So $d \sim e$ still holds via the direct edge $\{d,e\}$, and $e \sim a$, so in fact $d \sim a$ too! Let's redo this carefully: $G'$ has edges $\{a,b\},\{b,c\},\{d,e\},\{a,e\},\{c,f\}$ (five edges, since we removed exactly one of the original six). Trace again from $a$: $a\sim b$ (edge), $a \sim e$ (edge), $b \sim c$ (edge) gives $a \sim c$, $c \sim f$ (edge) gives $a \sim f$, $e \sim d$ (edge) gives $a \sim d$. So every vertex is still reachable from $a$ — removing the single edge $\{c,d\}$ did not disconnect $G$, because $d$ has an alternate route to the rest of the graph via $e$. So $G'$ is still connected, $c(G') = 1$. This example is chosen precisely because the naive guess "deleting an edge increases the number of components" is false in general — it depends on whether that edge lies on a cycle (here, $\{c,d\}$ sits on the cycle $c,d,e,a,b,c$, so removing it leaves an alternate path). This foreshadows the material on Vertex and Edge Connectivity, where the edges whose removal does disconnect a graph are singled out as bridges.

Euler did not use the modern vocabulary of vertices, edges, or connected components, but his 1736 resolution of the Seven Bridges of Königsberg problem is the historical seed from which this entire subject grew. He recognized that the only combinatorial data relevant to a walking-tour question was which landmasses were joined by which bridges — an abstraction that, a century and a half later, would be formalized as a graph, with connectivity and reachability as its most primitive structural questions. The rigorous equivalence-relation treatment of components used above belongs to the modern axiomatic era, but its motivating question — can I get from here to there? — is exactly Euler's.