Chapter 9. Components

A disconnected graph is made of connected pieces. These pieces are called components. A component is a maximal connected subgraph: it is connected, and it cannot be enlarged inside the original graph while remaining a connected subgraph. Equivalently, the components partition the vertex set into maximal groups of mutually reachable vertices.

9.1 Definition

Let

be an undirected graph. A component of $G$ is a connected subgraph $H$ of $G$ such that no larger connected subgraph of $G$ contains $H$.

The word larger means larger by inclusion. A component already contains every vertex and edge that can be included without leaving its connected piece.

Thus a component is not merely a connected subgraph. It is a maximal connected subgraph.

9.2 Maximal Connected Subgraphs

A connected subgraph may fail to be a component because it can be enlarged.

For example, consider the path

The subgraph on vertices

is connected. But it is not a component of the whole graph, because the vertex $d$ and the edge $\{c,d\}$ can be added while preserving connectedness.

The whole path on

is a component if there are no edges from these vertices to any outside vertex.

Maximal does not mean maximum. A maximal connected subgraph cannot be enlarged. A maximum connected subgraph would be one of largest possible size. A graph may have several maximal components of different sizes.

9.3 Components Partition the Vertex Set

Every vertex belongs to exactly one component.

This follows from the fact that connectedness is an equivalence relation on vertices. Two vertices are equivalent when there is a path between them. The equivalence classes are the components.

Thus the vertex set decomposes as

where the sets $V_i$ are pairwise disjoint and each induced subgraph

is connected.

The number $k$ is the number of components of $G$. It is often written as

9.4 Connected and Disconnected Graphs

A graph is connected exactly when it has one component:

A disconnected graph has more than one component:

For example, if

and

then the graph has three components with vertex sets

The first component is a path on three vertices. The second component is a single edge. The third component is an isolated vertex.

9.5 Isolated Vertices as Components

An isolated vertex is a vertex of degree $0$.

If $v$ is isolated, then no edge is incident with $v$. Therefore no vertex other than $v$ is reachable from $v$. The singleton subgraph with vertex set

is connected and maximal. Hence it is a component.

An empty graph on $n$ vertices has

components. Each vertex is its own component.

9.6 Edges and Components

Each edge belongs to exactly one component.

If an edge joins $u$ and $v$, then $u$ and $v$ are connected by a path of length $1$. Therefore they belong to the same component.

There can be no edge between two different components. If such an edge existed, it would create a path between vertices in the two components, so the two components would actually be one component.

Thus components are separated not only by lack of paths, but also by lack of edges between them.

9.7 Components as Induced Subgraphs

The component containing a vertex $v$ can be described as the subgraph induced by all vertices reachable from $v$.

Let

Then the component containing $v$ is

It is induced because all edges between reachable vertices are included. If an edge has both endpoints in $R(v)$, then it lies inside the same connected piece.

This description is useful both in proofs and in algorithms.

9.8 Component Size

The order of a component is the number of vertices in it. The size of a component is the number of edges in it.

If a component $C$ has vertex set $V(C)$ and edge set $E(C)$, then its order is

and its size is

A graph may have components of different orders and sizes.

For example, a graph may have one component with $1000$ vertices and several components with one or two vertices. In network science, a very large component is often called a giant component, especially in random graph models.

9.9 Component Decomposition

Every graph is the disjoint union of its components.

If the components are

then

where the vertex sets are pairwise disjoint.

Similarly,

where the edge sets are pairwise disjoint.

This decomposition lets many graph questions be reduced to connected graphs. One studies each component separately and then combines the results.

9.10 Counting Components by Traversal

Components can be found by graph traversal.

Choose an unvisited vertex $v$. Run depth-first search or breadth-first search starting from $v$. The vertices reached are exactly the component containing $v$.

Then choose another unvisited vertex and repeat. Each new traversal finds one new component.

For a graph stored by adjacency lists, this takes time

Each vertex is visited once, and each edge is examined a bounded number of times.

9.11 Component Algorithm

A simple component-finding procedure is as follows.

components(G):
    mark every vertex as unvisited
    result = []

    for each vertex v in V(G):
        if v is unvisited:
            C = search_from(v)
            add C to result

    return result

Here search_from(v) may be breadth-first search or depth-first search. It returns all vertices reachable from $v$.

The correctness follows directly from the definition of component as a maximal reachable set.

9.12 Components and the Adjacency Matrix

If the vertices of a graph are ordered by component, the adjacency matrix becomes block diagonal.

Suppose

has components

If all vertices of $G_1$ are listed first, then all vertices of $G_2$, and so on, the adjacency matrix has the form

Each block $A_i$ is the adjacency matrix of component $G_i$. The zero blocks appear because there are no edges between different components.

This is one reason components are important in algebraic graph theory. They split a graph into independent matrix blocks.

9.13 Components in Forests

A forest is an acyclic graph. Each component of a forest is a tree.

If a forest has $n$ vertices, $m$ edges, and $c$ components, then

Equivalently,

This follows because each tree component with $n_i$ vertices has $n_i-1$ edges. Summing over all components gives

This formula is one of the basic counting identities for forests.

9.14 Components and Edge Addition

Adding an edge can reduce the number of components by at most one.

If the new edge joins two vertices already in the same component, then the number of components does not change.

If the new edge joins vertices in two different components, then those two components merge into one. The number of components decreases by one.

Thus, if $G'$ is obtained from $G$ by adding one edge, then

This observation is useful in minimum spanning tree algorithms and union-find data structures.

9.15 Components and Edge Removal

Removing an edge can increase the number of components by at most one.

If the removed edge lies on a cycle, then its endpoints remain connected by the rest of the cycle, so the component count does not change.

If the removed edge is a bridge, then its removal splits one component into two, increasing the component count by one.

Thus, if $G'$ is obtained from $G$ by removing one edge, then

Edges whose removal increases the component count are exactly bridges.

9.16 Components in Directed Graphs

Directed graphs have several component notions.

A weak component is a component of the underlying undirected graph obtained by ignoring edge directions.

A strong component is a maximal subgraph in which every vertex is reachable from every other vertex by directed paths.

Thus weak components describe undirected connectivity. Strong components describe two-way directed reachability. A directed graph may be weakly connected but have many strong components.

For example,

has one weak component, but three strong components:

No vertex can return to a previous one along directed edges.

9.17 Strongly Connected Components

A strongly connected component, often abbreviated SCC, is a maximal set of vertices such that every vertex in the set can reach every other vertex in the set by directed paths.

If $u$ and $v$ lie in the same SCC, then there is a directed path from $u$ to $v$ and a directed path from $v$ to $u$.

SCCs are central in directed graph algorithms. They appear in program analysis, dependency graphs, model checking, control flow, automata theory, and network analysis.

A directed cycle is one simple source of a strongly connected component. In the directed cycle

the vertices $a,b,c$ form one SCC.

9.18 Condensation Graph

The strongly connected components of a directed graph can be collapsed into single vertices.

The resulting directed graph is called the condensation graph.

Each vertex of the condensation graph represents one SCC. There is an arc from component $C_i$ to component $C_j$ if the original graph has an arc from a vertex in $C_i$ to a vertex in $C_j$.

The condensation graph is always acyclic. If it contained a directed cycle among components, then those components would be mutually reachable and should have been one larger SCC.

9.19 Example

Let

and

The components are:

The first component is a triangle. The second and third components are single edges. The fourth component is an isolated vertex.

Thus

The graph is disconnected because it has more than one component.

9.20 Summary

A component is a maximal connected subgraph. Components partition the vertices and edges of an undirected graph. A graph is connected exactly when it has one component.

Isolated vertices are components of order $1$. In a forest, each component is a tree, and the identity

holds.

Components can be found by breadth-first search or depth-first search in time

For directed graphs, weak components ignore edge direction, while strongly connected components require mutual directed reachability.