Page 708 - Discrete Mathematics and Its Applications

10.4 Connectivity 687

GSCC following a series of links, but cannot be reached by following links on pages in the
GSCC; and pages that cannot reach pages in the GSCC and cannot be reached from pages in
the GSCC following a series of links. In this study, each of these three other sets was found to
have approximately 44 million vertices. (It is rather surprising that these three sets are close to
the same size.) ▲

Paths and Isomorphism

There are several ways that paths and circuits can help determine whether two graphs are
isomorphic. For example, the existence of a simple circuit of a particular length is a useful
invariant that can be used to show that two graphs are not isomorphic. In addition, paths can be
used to construct mappings that may be isomorphisms.
As we mentioned, a useful isomorphic invariant for simple graphs is the existence of a
simple circuit of length k, where k is a positive integer greater than 2. (The proof that this is an
invariant is left as Exercise 60.) Example 13 illustrates how this invariant can be used to show
that two graphs are not isomorphic.

EXAMPLE 13 Determine whether the graphs G and H shown in Figure 6 are isomorphic.

Solution: Both G and H have six vertices and eight edges. Each has four vertices of degree
three, and two vertices of degree two. So, the three invariants—number of vertices, number of
edges, and degrees of vertices—all agree for the two graphs. However, H has a simple circuit
of length three, namely, v 1 , v 2 , v 6 , v 1 , whereas G has no simple circuit of length three, as
can be determined by inspection (all simple circuits in G have length at least four). Because
the existence of a simple circuit of length three is an isomorphic invariant, G and H are not
isomorphic. ▲

We have shown how the existence of a type of path, namely, a simple circuit of a particular
length, can be used to show that two graphs are not isomorphic. We can also use paths to find
mappings that are potential isomorphisms.

EXAMPLE 14 Determine whether the graphs G and H shown in Figure 7 are isomorphic.

Solution: Both G and H have five vertices and six edges, both have two vertices of degree three
and three vertices of degree two, and both have a simple circuit of length three, a simple circuit
of length four, and a simple circuit of length five. Because all these isomorphic invariants agree,
G and H may be isomorphic.

u 1 v 1

u 6 u 2 v 6 v 2
u 2 v 1

u 5 u 3 v 5 v 3 u 1 u 3 v 5 v 2

u v
u 4 v 4 u 5 4 v 4 3
G H G H

FIGURE 6 The Graphs G and H. FIGURE 7 The Graphs G and H.