SKEDSOFT

EXAMPLE 2  Determine whether the graphs G and H displayed in Figure 12 are isomorphic.
Solution: BothGandH 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 .

We now will define a function f and then determine whether it is an isomorphism. Because deg(u1) = 2 and because u1 is not adjacent to any other vertex of degree two, the image of u1 must be either v4 or v6, the only vertices of degree two in H not adjacent to a vertex of degree two. We arbitrarily set f (u1) = v6. [If we found that this choice did not lead to isomorphism, we would then try f (u1) = v4.] Because u2 is adjacent to u1, the possible images of u2 are v3 and v5. We arbitrarily set f (u2) = v3. Continuing in this way, using adjacency of vertices and degrees as a guide, we set f (u3) = v4, f (u4) = v5, f (u5) = v1, and f (u6) = v2.We nowhave a one-to-one correspondence between the vertex set of G and the vertex set of H, namely, f (u1) = v6, f (u2) = v3, f (u3) = v4, f (u4) = v5, f (u5) = v1, f (u6) = v2. To see whether f preserves edges, we examine the adjacency matrix of G,

and the adjacency matrix of H with the rows and columns labeled by the images of the corresponding vertices in G,

Because AG = AH, it follows that f preserves edges. We conclude that f is an isomorphism, so G and H are isomorphic. Note that if f turned out not to be an isomorphism, we would not have established that G and H are not isomorphic, because another correspondence of the vertices in G and H may be an isomorphism.