Another Example

Let us consider another example.

3-1) Are the two graphs isomorphic? Click on the answer before reading further.
Here is the reason these two graphs are not isomorphic.  If they were isomorphic, then we would be able to superpose the pink graph onto the orange one so that the vertices of the pink graph would be matched with the vertices of the orange, and the edges of the pink would be matched with the corresponding edges of the orange. 

However, such a match does not exist between the two graphs for several reasons.  The simplest one is as follows: the pink graph has two vertices of degree three, while the orange graph has three vertices of degree three.  Thus, any one-to-one match between the vertices of the graphs would match some vertex x of degree three of the orange graph with a vertex y of degree less than three of the pink graph.  Thus a neighbor of x, say , would have to be matched with a vertex , which is not a neighbor of y.

The fact that such two pairs, and must exist for any one-to-one match between the vertices of the two graphs shows that the graphs are not "the same."  The idea of the superposition of one structure onto the other is at the core of the definition of isomorphism.

Copyright 2000 Rensselaer Polytechnic Institute. All Rights Reserved.