Page 695 - Discrete Mathematics and Its Applications

674 10 / Graphs

We now will define a function f and then determine whether it is an isomorphism. Because
deg(u 1 ) = 2 and because u 1 is not adjacent to any other vertex of degree two, the image of u 1
must be either v 4 or v 6 , the only vertices of degree two in H not adjacent to a vertex of degree
two. We arbitrarily set f(u 1 ) = v 6 . [If we found that this choice did not lead to isomorphism,
we would then try f(u 1 ) = v 4 .] Because u 2 is adjacent to u 1 , the possible images of u 2 are v 3
and v 5 . We arbitrarily set f(u 2 ) = v 3 . Continuing in this way, using adjacency of vertices and
degrees as a guide, we set f(u 3 ) = v 4 , f(u 4 ) = v 5 , f(u 5 ) = v 1 , and f(u 6 ) = v 2 .We now have
a one-to-one correspondence between the vertex set of G and the vertex set of H, namely,
f(u 1 ) = v 6 , f(u 2 ) = v 3 , f(u 3 ) = v 4 , f(u 4 ) = v 5 , f(u 5 ) = v 1 , f(u 6 ) = v 2 . To see whether f
preserves edges, we examine the adjacency matrix of G,

u 1 u 2 u 3 u 4 u 5 u 6
⎡ ⎤
u 1 0 1 0 1 0 0
⎢
⎥
u 2 ⎢ 1 0 1 0 0 1 ⎥
⎥
⎢
u 3 ⎢ 0 1 0 1 0 0 ⎥
A G = ⎢ ⎥,
⎢ 1
u 4 0 1 0 1 0 ⎥
⎢ ⎥
u 5 ⎣ 0 0 0 1 0 1 ⎦
u 6 0 1 0 0 1 0
and the adjacency matrix of H with the rows and columns labeled by the images of the corre-
sponding vertices in G,
v 6 v 3 v 4 v 5 v 1 v 2
⎡ ⎤
v 6 0 1 0 1 0 0
⎢ 1 0 1 0 0 ⎥
⎢
v 3 1 ⎥
⎢ ⎥
v 4 ⎢ 0 1 0 1 0 0 ⎥
A H = ⎢ ⎥.
v 5 ⎢ 1 0 1 0 1 0 ⎥
⎢ ⎥
v 1 ⎣ 0 0 0 1 0 1 ⎦
v 2 0 1 0 0 1 0
Because A G = A H , 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. ▲

ALGORITHMSFORGRAPHISOMORPHISM Thebestalgorithmsknownfordetermining
whether two graphs are isomorphic have exponential worst-case time complexity (in the number
of vertices of the graphs). However, linear average-case time complexity algorithms are known
that solve this problem, and there is some hope, but also skepticism, that an algorithm with
polynomial worst-case time complexity for determining whether two graphs are isomorphic can
be found. The best practical general purpose software for isomorphism testing, called NAUTY,
can be used to determine whether two graphs with as many as 100 vertices are isomorphic
in less than a second on a modern PC. NAUTY software can be downloaded over the Internet
and experimented with. Practical algorithms for determining whether two graphs are isomorphic
exist for graphs that are restricted in various ways, such as when the maximum degree of vertices
is small.The problem of determining whether any two graphs are isomorphic is of special interest
because it is one of only a few NP problems (see Exercise 72) not known to be either tractable
or NP-complete (see Section 3.3).

APPLICATIONS OF GRAPH ISOMORPHISMS Graph isomorphisms, and functions that
are almost graph isomorphisms, arise in applications of graph theory to chemistry and to the
design of electronic circuits, and other areas including bioinformatics and computer vision.