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.