# Chapter 9. Components

# 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

$$
G = (V,E)
$$

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

$$
a,b,c,d.
$$

The subgraph on vertices

$$
\{a,b,c\}
$$

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

$$
\{a,b,c,d\}
$$

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

$$
V = V_1 \cup V_2 \cup \cdots \cup V_k,
$$

where the sets \(V_i\) are pairwise disjoint and each induced subgraph

$$
G[V_i]
$$

is connected.

The number \(k\) is the number of components of \(G\). It is often written as

$$
c(G).
$$

## 9.4 Connected and Disconnected Graphs

A graph is connected exactly when it has one component:

$$
c(G)=1.
$$

A disconnected graph has more than one component:

$$
c(G)>1.
$$

For example, if

$$
V=\{a,b,c,d,e,f\}
$$

and

$$
E=\{\{a,b\},\{b,c\},\{d,e\}\},
$$

then the graph has three components with vertex sets

$$
\{a,b,c\},
\qquad
\{d,e\},
\qquad
\{f\}.
$$

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

$$
\{v\}
$$

is connected and maximal. Hence it is a component.

An empty graph on \(n\) vertices has

$$
n
$$

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

$$
R(v)=\{u \in V(G): \text{there is a path from } v \text{ to } u\}.
$$

Then the component containing \(v\) is

$$
G[R(v)].
$$

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

$$
|V(C)|
$$

and its size is

$$
|E(C)|.
$$

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

$$
G_1,G_2,\ldots,G_k,
$$

then

$$
V(G)=V(G_1)\cup V(G_2)\cup \cdots \cup V(G_k),
$$

where the vertex sets are pairwise disjoint.

Similarly,

$$
E(G)=E(G_1)\cup E(G_2)\cup \cdots \cup E(G_k),
$$

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

$$
O(|V|+|E|).
$$

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.

```text
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

$$
G
$$

has components

$$
G_1,G_2,\ldots,G_k.
$$

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

$$
A =
\begin{bmatrix}
A_1 & 0 & \cdots & 0 \\
0 & A_2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & A_k
\end{bmatrix}.
$$

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

$$
m = n - c.
$$

Equivalently,

$$
c = n - m.
$$

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

$$
m = \sum_i (n_i - 1)
  = \left(\sum_i n_i\right) - c
  = n-c.
$$

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

$$
c(G') \in \{c(G), c(G)-1\}.
$$

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

$$
c(G') \in \{c(G), c(G)+1\}.
$$

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,

$$
a \to b \to c
$$

has one weak component, but three strong components:

$$
\{a\}, \{b\}, \{c\}.
$$

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

$$
a \to b \to c \to a,
$$

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

$$
V=\{a,b,c,d,e,f,g,h\}
$$

and

$$
E=
\{\{a,b\},\{b,c\},\{c,a\},\{d,e\},\{f,g\}\}.
$$

The components are:

$$
C_1 = G[\{a,b,c\}],
$$

$$
C_2 = G[\{d,e\}],
$$

$$
C_3 = G[\{f,g\}],
$$

$$
C_4 = G[\{h\}].
$$

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

Thus

$$
c(G)=4.
$$

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

$$
m=n-c
$$

holds.

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

$$
O(|V|+|E|).
$$

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