We often need to know whether it is possible to draw two graphs in the same way.

That is, do the graphs have the same structure when we ignore the identities of their vertices?

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

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?

FIGURE8: The Graphs G and H.

Problem in finding Isomorphism:

It is easy to show Non-Isomorphism:

FIGURE11 The Subgraphs of G and H MadeUp
of Vertices of Degree Three and the Edges Connecting Them.