Connected Components and Their Partition

From Reachability to Components

A graph may consist of several groups of vertices with no way to travel by a path from one group to another. Connected components describe those groups precisely: two vertices belong to the same component exactly when a path joins them. This viewpoint turns the informal idea of a separate “piece” of a graph into a precise partition of its vertex set.

Throughout, graphs are finite and simple. A path is a sequence of distinct vertices in which consecutive vertices are adjacent; a path of length zero consists of one vertex. Vertices \(u\) and \(v\) are reachable from one another if there is a path from \(u\) to \(v\). In particular, every vertex is reachable from itself by the path of length zero.

The definition describes components as sets of vertices. We will not need to define a component as a particular subgraph here. The earlier material on connectedness establishes that reachability is an equivalence relation: every vertex reaches itself, a path can be reversed, and paths can be joined at a common endpoint to obtain a walk, which contains a path between its endpoints. Thus the equivalence classes of reachability are exactly the sets \([v]\) above.

The Partition Theorem

A partition of a set is a collection of nonempty subsets that are pairwise disjoint and whose union is the whole set. For connected components, these three requirements say that each component contains a vertex, no vertex lies in two different components, and no vertex is left out.

Proof. First fix any vertex \(v\in V(G)\). The length-zero path from \(v\) to itself shows that \(v\in[v]\), so \([v]\) is nonempty. Next, every vertex \(x\in V(G)\) belongs to its own class \([x]\). Therefore the union of all the reachability classes contains every vertex of \(G\). Each class is, by definition, a subset of \(V(G)\), so that union is exactly \(V(G)\).

It remains to prove that any two classes are either identical or disjoint. Suppose \([a]\cap[b]\ne\varnothing\), and choose \(x\in[a]\cap[b]\). Since reachability is an equivalence relation, \(a\) is reachable from \(x\) and \(x\) is reachable from \(b\); hence \(a\) and \(b\) are reachable from each other. Now let \(y\in[a]\). Then \(y\) is reachable from \(a\), and \(a\) is reachable from \(b\), so \(y\) is reachable from \(b\). Thus \(y\in[b]\), proving \([a]\subseteq[b]\). Interchanging \(a\) and \(b\) gives \([b]\subseteq[a]\), so \([a]=[b]\). Therefore intersecting classes are equal, and distinct classes are disjoint. Together with nonemptiness and the union statement, this proves that the classes form a partition of \(V(G)\). \(\square\)

This theorem also gives a useful way to think about membership: a vertex belongs to exactly one component. It belongs to at least one because it is reachable from itself. If it belonged to two, those classes would intersect and so would have to be equal.

Worked Examples

Edges and Component Membership

Proof. Let \(uv\in E(G)\). The edge \(uv\) is itself a path from \(u\) to \(v\), so \(u\) and \(v\) are reachable. Hence \(v\in[u]\). Since \([u]\) is the component containing \(u\), both endpoints of the edge belong to that component. \(\square\)

The proposition explains why separate components have no edges between them: an edge between two vertices would make them reachable and place them in the same class. The converse needs care. Knowing that there is no edge directly between two groups does not, by itself, rule out a path between them; a path could use intermediate vertices. To show that two proposed sets really are separate components, one must rule out paths, not merely inspect whether a direct edge joins the sets. In the examples, the edge lists and the lack of any route through intermediate vertices provide that justification.

Empty Graph and Common Pitfalls

If \(V(G)=\varnothing\), there are no vertices and therefore no reachability classes. The collection of components is empty. Its union is the empty set, which equals \(V(G)\); the statements that every component is nonempty and that distinct components are disjoint hold vacuously because there are no components to test. Thus the partition statement also includes the empty graph. For any nonempty graph, the length-zero path ensures that each vertex contributes to some nonempty class, including when the vertex is isolated.

Common mistake: omitting isolated vertices. In the edgeless example, a mistaken list might say that there are no components because there are no edges. This confuses edges with vertices. The calculation “\(E=\varnothing\), so the number of components is \(0\)” is wrong: components are reachability classes of vertices, not groups of edges. Since each vertex reaches itself, the correct list is \(\{1\},\{2\},\{3\},\{4\}\), giving four components. The correction follows directly from the length-zero path in the definition.

Common mistake: allowing overlapping components. One might list \(\{1,2\}\) and \(\{2,3\}\) as separate components in a graph where \(1,2,3\) are joined by paths. These sets overlap at \(2\), so they cannot be distinct reachability classes: the partition theorem proves that intersecting classes are equal. The correct component includes all vertices reachable from any one of its members.

Connected components organize the vertex set according to whether paths exist, without requiring a choice of starting vertex for the whole graph. This is useful whenever a graph is disconnected: statements about reachability can be considered separately within each class, and no edge can carry a route from one class to another. The essential bookkeeping is exact: every vertex appears once, even when a component consists of a single isolated vertex.