Page 694 - Discrete Mathematics and Its Applications

10.3 Representing Graphs and Graph Isomorphism 673

b b
a b s t
a c a c
f w
e x
h g z y

e d e d d c v u
G H G H

FIGURE 9 The Graphs G and H. FIGURE 10 The Graphs G and H.

EXAMPLE 10 Determine whether the graphs shown in Figure 10 are isomorphic.
b
Solution: The graphs G and H both have eight vertices and 10 edges. They also both have four
f vertices of degree two and four of degree three. Because these invariants all agree, it is still
conceivable that these graphs are isomorphic.
h However, G and H are not isomorphic. To see this, note that because deg(a) = 2in G, a
d must correspond to either t, u, x,or y in H, because these are the vertices of degree two in H.
However, each of these four vertices in H is adjacent to another vertex of degree two in H,
s which is not true for a in G.
Another way to see that G and H are not isomorphic is to note that the subgraphs of G
w and H made up of vertices of degree three and the edges connecting them must be isomorphic
if these two graphs are isomorphic (the reader should verify this). However, these subgraphs,
z
shown in Figure 11, are not isomorphic. ▲
v
To show that a function f from the vertex set of a graph G to the vertex set of a graph H is an
FIGURE 11 The isomorphism, we need to show that f preserves the presence and absence of edges. One helpful
Subgraphs of G way to do this is to use adjacency matrices. In particular, to show that f is an isomorphism, we
and H Made Up can show that the adjacency matrix of G is the same as the adjacency matrix of H, when rows
of Vertices of De- and columns are labeled to correspond to the images under f of the vertices in G that are the
gree Three and labels of these rows and columns in the adjacency matrix of G. We illustrate how this is done
the Edges Con- in Example 11.
necting Them.
EXAMPLE 11 Determine whether the graphs G and H displayed in Figure 12 are isomorphic.

Solution: Both G and H have six vertices and seven edges. Both have four vertices of degree two
and two vertices of degree three. It is also easy to see that the subgraphs of G and H consisting
of all vertices of degree two and the edges connecting them are isomorphic (as the reader should
verify). Because G and H agree with respect to these invariants, it is reasonable to try to find
an isomorphism f .

u 1 u 2 v 1 v 3

u 5
v 2
u 6 v 6
u 4 u 3 v 5 v 4
G H

FIGURE 12 Graphs G and H.