Page 703 - Discrete Mathematics and Its Applications

682 10 / Graphs

a b
H 2
H 1 H 3
c a b
d e
b f
f d e
c

g e d f H
a c h g
G 1 G 2

FIGURE 2 The Graphs G 1 and FIGURE 3 The Graph H and Its
G 2 . Connected Components H 1 , H 2 , and H 3 .

THEOREM 1 There is a simple path between every pair of distinct vertices of a connected undirected graph.

Proof: Let u and v be two distinct vertices of the connected undirected graph G = (V, E). Be-
cause G is connected, there is at least one path between u and v. Let x 0 ,x 1 ,...,x n , where x 0 = u
and x n = v, be the vertex sequence of a path of least length. This path of least length is simple. To
see this, suppose it is not simple. Then x i = x j for some i and j with 0 ≤ i< j. This means that
there is a path from u to v of shorter length with vertex sequence x 0 ,x 1 ,...,x i−1 ,x j ,...,x n
obtained by deleting the edges corresponding to the vertex sequence x i ,...,x j−1 .

CONNECTED COMPONENTS A connected component of a graph G is a connected sub-
graph of G that is not a proper subgraph of another connected subgraph of G.That is, a connected
component of a graph G is a maximal connected subgraph of G.A graph G that is not connected
has two or more connected components that are disjoint and have G as their union.
EXAMPLE 5 What are the connected components of the graph H shown in Figure 3?

Solution: The graph H is the union of three disjoint connected subgraphs H 1 , H 2 , and H 3 , shown
in Figure 3. These three subgraphs are the connected components of H. ▲

EXAMPLE 6 Connected Components of Call Graphs Two vertices x and y are in the same component of a
telephone call graph (see Example 4 in Section 10.1) when there is a sequence of telephone calls
beginning at x and ending at y. When a call graph for telephone calls made during a particular
day in the AT&T network was analyzed, this graph was found to have 53,767,087 vertices,
more than 170 million edges, and more than 3.7 million connected components. Most of these
components were small; approximately three-fourths consisted of two vertices representing pairs
of telephone numbers that called only each other. This graph has one huge connected component
with 44,989,297 vertices comprising more than 80% of the total. Furthermore, every vertex in
this component can be linked to any other vertex by a chain of no more than 20 calls. ▲

How Connected is a Graph?

Suppose that a graph represents a computer network. Knowing that this graph is connected tells
us that any two computers on the network can communicate. However, we would also like to
understand how reliable this network is. For instance, will it still be possible for all computers to
communicate after a router or a communications link fails? To answer this and similar questions,
we now develop some new concepts.