Page 693 - Discrete Mathematics and Its Applications

672 10 / Graphs

There is a useful terminology for graphs with the same structure.

DEFINITION 1 The simple graphs G 1 = (V 1 ,E 1 ) and G 2 = (V 2 ,E 2 ) are isomorphic if there exists a one-
to-one and onto function f from V 1 to V 2 with the property that a and b are adjacent in G 1 if
and only if f(a) and f(b) are adjacent in G 2 , for all a and b in V 1 . Such a function f is called
∗
an isomorphism. Two simple graphs that are not isomorphic are called nonisomorphic.

In other words, when two simple graphs are isomorphic, there is a one-to-one correspondence
between vertices of the two graphs that preserves the adjacency relationship. Isomorphism of
simple graphs is an equivalence relation. (We leave the verification of this as Exercise 45.)

EXAMPLE 8 Show that the graphs G = (V, E) and H = (W, F), displayed in Figure 8, are isomorphic.

u 1 u 2 Solution: The function f with f(u 1 ) = v 1 , f(u 2 ) = v 4 , f(u 3 ) = v 3 , and f(u 4 ) = v 2 is a one-
to-one correspondence between V and W. To see that this correspondence preserves adjacency,
note that adjacent vertices in G are u 1 and u 2 ,u 1 and u 3 , u 2 and u 4 , and u 3 and u 4 , and each of the
pairs f(u 1 ) = v 1 and f(u 2 ) = v 4 , f(u 1 ) = v 1 and f(u 3 ) = v 3 , f(u 2 ) = v 4 and f(u 4 ) = v 2 ,
and f(u 3 ) = v 3 and f(u 4 ) = v 2 consists of two adjacent vertices in H. ▲
u 3 u 4
G
v 1 v 2 Determining whether Two Simple Graphs are Isomorphic
It is often difficult to determine whether two simple graphs are isomorphic. There are n! possible
one-to-one correspondences between the vertex sets of two simple graphs withn vertices.Testing
each such correspondence to see whether it preserves adjacency and nonadjacency is impractical
if n is at all large.
v 3 v 4
H Sometimes it is not hard to show that two graphs are not isomorphic. In particular, we can
show that two graphs are not isomorphic if we can find a property only one of the two graphs
FIGURE 8 The has, but that is preserved by isomorphism. A property preserved by isomorphism of graphs is
Graphs G and H. called a graph invariant. For instance, isomorphic simple graphs must have the same number
of vertices, because there is a one-to-one correspondence between the sets of vertices of the
graphs.
Isomorphic simple graphs also must have the same number of edges, because the one-to-one
correspondence between vertices establishes a one-to-one correspondence between edges. In
addition, the degrees of the vertices in isomorphic simple graphs must be the same. That is, a
vertex v of degree d in G must correspond to a vertex f(v) of degree d in H, because a vertex
w in G is adjacent to v if and only if f(v) and f(w) are adjacent in H.

EXAMPLE 9 Show that the graphs displayed in Figure 9 are not isomorphic.

Solution: Both G and H have five vertices and six edges. However, H has a vertex of degree one,
namely, e, whereas G has no vertices of degree one. It follows that G and H are not isomorphic.
▲

The number of vertices, the number of edges, and the number of vertices of each degree
are all invariants under isomorphism. If any of these quantities differ in two simple graphs,
these graphs cannot be isomorphic. However, when these invariants are the same, it does not
necessarily mean that the two graphs are isomorphic. There are no useful sets of invariants
currently known that can be used to determine whether simple graphs are isomorphic.

∗ The word isomorphism comes from the Greek roots isos for “equal” and morphe for “form.”