Introduction to Graph Theory (8 page)

is another one.

One-to-one correspondence is the principle behind counting. To count the playing cards in a pack a person removes the first card and says—at least thinks—“one”; then removes the second and says
“two”; and so on. The person is associating a number to each card. If the number associated with the last card is, say, “fifty”, the person concludes that the pack contains fifty cards. A one-to-one correspondence has been established between the cards and the set {1, 2, 3, ..., 50}.

Definition 16
. Two graphs are said to be isomorphic if there exists between their vertex sets a one-to-one correspondence having the property that whenever two vertices are adjacent in either graph, the corresponding two vertices are adjacent in the other graph. Such a one-to-one correspondence is called an isomorphism. If
G
and
H
are isomorphic graphs we denote this by writing “G ≅ H”.

An isomorphism is a special one-to-one correspondence in that it not only associates vertices with vertices but also, in a sense, edges with edges. That is, given an isomorphism between the vertex sets of two graphs under which vertices
A
and
B
correspond to vertices
X
and
Y
, I am guaranteed that if {
A
,
B
} is in the edge set of the first graph, then {
X
,
Y
} is in the edge set of the second; and that if {
A
,
B
} is not in the edge set of the first graph, then {
X
,
Y
} is not in the edge set of the second. The isomorphism leaves the edge structure undisturbed: the adjacency or nonadjacency of a pair of vertices implies, respectively, the adjacency or nonadjacency of the corresponding vertices. Mathematicians describe this property by saying that an isomorphism is a one-to-one correspondence between vertex sets that “preserves vertex adjacency.”

The definition calls two graphs “isomorphic” if “there exists” an isomorphism; so to prove that two graphs are isomorphic, all you have to do is find an isomorphism and present it.

Example
. The graphs of
Figure 20
are isomorphic, and here is an isomorphism:

To check that this one-to-one correspondence is an isomorphism, I only have to verify that it preserves vertex adjacency as the definition requires. In the first graph
B
is adjacent to
C
;
B
and
C
correspond to 1 and 2; and in the second graph 1 is adjacent to 2. In the first graph
A
is adjacent to
C
;
A
and
C
correspond to 3 and 2; and in the second graph 3 is adjacent to 2. In the first graph
A
is adjacent to
D
;
A
and
D
correspond to 3 and 4; and in the second graph 3 is adjacent to 4. There are no more adjacencies in either graph, so we have shown that whenever two vertices are adjacent in either one of the graphs, the corresponding two vertices are adjacent in the other graph.

Often there exist several isomorphisms between a pair of isomorphic graphs, though of course the definition requires only that there be one.

Figure 20

Example
. Here is another isomorphism between the graph of
Figure 20
:

You can check for yourself that this one-to-one correspondence preserves vertex adjacency and so is an isomorphism as claimed.

Here's another way of displaying an isomorphism, one that I find a lot simpler. Pick one of the two graphs and put a pair of parentheses next to each vertex. Then fill each pair of parentheses with the name of the corresponding vertex from the other graph.

Examples.
1) The graphs of
Figure 21
are isomorphic, and I have indicated an isomorphism by adding parenthetical labels to the second graph; that is, 3 corresponds to
D
, 2 to
C
, 4 to
A
, and 1 to 5. To
verify that this one-to-one correspondence between the vertex sets is an isomorphism, all I have to do is check that the adjacency of the parenthetical labels in the second graph is the same as their adjacency in the first graph. For instance in the second graph,
A
is adjacent only to
D
and
C
; and in the first graph,
A
is adjacent only to
D
and
C
. So
A
checks;
A
's structural involvement is the same in both graphs.

Figure 21

Now I'll do the same for
B
,
C
, and
D
. In the second graph,
B
is adjacent only to
C
; and in the first graph,
B
is adjacent only to
C
. Check.

In the second graph,
C
is adjacent to all the other vertices; and in the first graph,
C
is adjacent to all the other vertices. Check.

In the second graph,
D
is adjacent only to
A
and
C
; and in the first graph,
D
is adjacent only to
A
and
C
. Check.

Everything checks, so the correspondence indicated by the labels in parentheses is an isomorphism, and the graphs of
Figure 21
are isomorphic.

2) The graphs of
Figure 22
are isomorphic, and I have displayed an isomorphism by the labels added parenthetically to the second graph. It is an isomorphism because, in both graphs:

1 is adjacent only to 3 and 6,

2 is adjacent only to 4 and 7,

3 is adjacent only to 1 and 5,

4 is adjacent only to 2, 5, and 6,

5 is adjacent only to 3, 4, 6, and 7,

6 is adjacent only to 1, 4, and 5, and

7 is adjacent only to 2 and 5.

Therefore, whenever two vertices are adjacent in either graph, the
corresponding two vertices are adjacent in the other graph, and we have an isomorphism.

Figure 22

Looking at the second graph in
Figure 22
, we can think of the labels in parentheses as being new labels that we are about to substitute in order to transform the second graph into a graph equal to the first graph. This suggests an alternate way of defining isomorphism: two graphs are isomorphic if either

      
1)
  
they are equal, or

      
2)
  
they could be made equal by changing the way one of them is labeled.

By the way, graphs don't
become
isomorphic when you discover an isomorphism. They are of themselves isomorphic, or not, whether or not anyone discovers the fact, or proves it.

Example
. The graphs of
Figure 23
are isomorphic as they stand, even though under the actual labeling they are not equal (because the edge sets are not equal), and I offer no alternate labeling under which they would be equal. They are isomorphic because they have the potential to be labeled so that edges appear in corresponding places.

This apparent independence of mathematical facts from what people do, this sense that mathematics is discovered rather than created, has caused a number of mathematicians (for instance Hardy in
A Mathematician's Apology
) to ascribe to mathematical objects a separate existence on another level of reality, akin to Plato's “world of Ideas”. Someone taking this view to its extreme would maintain that the graphs of
Figure 23
have been isomorphic since before the formation of the solar system.

Figure 23

Recognizing isomorphic graphs

In doing graph theory, it's important not only to understand what it means when someone tells you two graphs are isomorphic, but also to develop some degree of skill at recognizing isomorphic graphs on your own. Often you'll need to decide whether or not two unfamiliar graphs are isomorphic, and then be able to prove that your choice is correct. Unfortunately, recognizing isomorphic graphs, finding specific isomorphisms, and proving graphs to be nonisomorphic are skills that can't really be taught; they come mostly with practice. Nevertheless in this section I will present some general guidelines that I hope will be of help.