Isomorphism Of Graphs

Isomorphism of Graphs:

DEFINITION 1 The simple graphs G1 = (V1,E1) and G2 = (V2,E2) are isomorphic if there exists a oneto- one and onto function f from V1 to V2 with the property that a and b are adjacent in G1 if and only if f (a) and f (b) are adjacent inG2, for all a and b in V1. 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 1 Show that the graphs G = (V ,E) and H = (W, F), displayed in Figure 8, are isomorphic.

Solution: The function f with f (u1) = v1, f (u2) = v4, f (u3) = v3, and f (u4) = v2 is a oneto- one correspondence between V and W. To see that this correspondence preserves adjacency, note that adjacent vertices inGare u1 and u2, u1 and u3, u2 and u4, and u3 and u4, and each of the pairs f (u1) = v1 and f (u2) = v4, f (u1) = v1 and f (u3) = v3, f (u2) = v4 and f (u4) = v2, and f (u3) = v3 and f (u4) = v2 consists of two adjacent vertices in H.

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 with n vertices.Testing each such correspondence to see whether it preserves adjacency and nonadjacency is impractical if n is at all large.

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 has, but that is preserved by isomorphism. A property preserved by isomorphism of graphs is 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 2 Show that the graphs displayed in Figure 9 are not isomorphic.
Solution: BothGandH 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.

EXAMPLE Determine whether the graphs shown in Figure 10 are isomorphic.

Solution: The graphs G and H both have eight vertices and 10 edges. They also both have four
vertices of degree two and four of degree three. Because these invariants all agree, it is still
conceivable that these graphs are isomorphic.
However, G and H are not isomorphic. To see this, note that because deg(a) = 2 in G, a 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, 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 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, shown in Figure 11, are not isomorphic.

To show that a function f from the vertex set of a graphGto the vertex set of a graphH is an isomorphism, we need to show that f preserves the presence and absence of edges. One helpful way to do this is to use adjacency matrices. In particular, to show that f is an isomorphism, we can show that the adjacency matrix of G is the same as the adjacency matrix of H, when rows and columns are labeled to correspond to the images under f of the vertices in G that are the labels of these rows and columns in the adjacency matrix of G. We illustrate how this is done in Example 2.