Discrete Mathematics for Computer Science

Connected Graphs 353

Definition 1. A graph for which each pair of (not necessarily distinct) vertices is joined

by a trail is connected. A graph that is not connected is disconnected. A connected com-

ponent of a graph is a subgraph that is connected but not contained in any connected

subgraph with more vertices or edges.

For the graphs drawn in Figure 6.20, it is easy to identify G as a connected graph and

the subgraphs A and B as the connected components of the disconnected graph H.

The key notion for designing an algorithm to decompose a graph into connected com-

ponents is the following relation defined on the vertices of a graph.

Definition 2. Let G = (V, E) be a graph. For all v, w e V, define v CONN w if and only

if there is a trail in G from v to w.

Example 1. Find the connected components of the graphs G and H:

b d a

a c Of c

G H

Solution. There is no trail in G from a to e. Therefore, G is disconnected. The two

components of G are

bd

a c

C 1 C 2

The graph H is connected, as can be seen by considering the trail a - b - c - d. H has

one connected component, itself! 0

To begin the process of decomposing a graph into its connected components, we will

show that the relation CONN is an equivalence relation on the vertices of the graph. Once

we know that the relation is an equivalence relation, we can use the fact that the distinct

equivalence classes form a partition. It will follow that the elements of the partition are the

vertex sets of the distinct connected components of the graph. The actual components of

the graphs are the subgraphs induced by the elements of this partition.

Theorem 1. CONN is an equivalence relation on the vertices of a graph.

Proof. The proof consists of showing that the relation CONN is reflexive, symmetric, and

transitive. Let G = (V, E) be a graph. For each v E V, the vertex itself is a trail from v to
v. Thus, v CONN v holds for each v E V, and CONN is reflexive. For vertices v, w E V
such that v CONN w, there is a trail in G from v to w. Such a trail can be reversed to
form a trail from w to v, showing that w CONN v. Therefore, CONN is symmetric. Now,