Introduction to Graph Theory (10 page)

Figure 32

Example
. The two graphs in
Figure 33
each have
v
= 8 and
e
= 12; they have the same distribution of degrees, namely two vertices of degree 1, three of degree 3, two of degree 4, and one of degree 5; and they are both in two pieces. This covers the more obvious possible differences, so I'll conjecture that they are isomorphic and try to construct an isomorphism. (If I fail I'll come back and search for differences that are less obvious.) Clearly vertices 4 and 5 of the first graph would have to correspond to vertices 2 and 3 of the second; I've indicated this by adding parenthetical labels to the second graph in
Figure 33
. And the vertex of degree 5 in the first graph would have to correspond to the vertex of degree 5 in the second, so after the label “4” in the second graph I'll put “(3)”. The two vertices of degree 4 in the first graph have to correspond to the two vertices of degree 4 in the second, but in what order? Should I associate
2 with 7 and 8 with 8, or should it be 2 with 8 and 8 with 7? It might make a difference. I'll try 2 with 7 and 8 with 8; if it doesn't work out I'll return to this point and try it the other way. So after labels “7” and “8” in the second graph I'll put “(2)” and “(8)”. Now all I have left is to associate the vertices of degree 3. I'll start with vertex 1 in the first graph. I won't match it with the “1” in the second graph, because the two “l”s are involved differently in the structures of their graphs: in the first graph vertex 1 is adjacent to vertices of degrees 3, 4, and 5, but in the second graph vertex 1 is adjacent to vertices of degrees 4, 4, and 5. Instead I'll match the “1” of the first graph with vertex 5 of the second graph, because in the second graph vertex 5 is adjacent to vertices of degrees 3, 4, and 5, a structural involvement like that of vertex 1 in the first graph. So next to the label “5” in the second graph I'll write “(1)”. Finally I'll associate vertex 6 of the first graph with vertex 1 of the second, as they are both adjacent to vertices of degrees 4, 4, and 5; this leaves vertex of the first graph associated with vertex 6 of the second graph, as they are the only vertices left. I have displayed all this in
Figure 34
, and you can verify for yourself that the correspondence does turn out to be an isomorphism. All you have to do is check that the numbers in parentheses in the second graph are connected to one another in exactly the same way as the numbers in the first graph.

Figure 33

The sort of thing we've just done is very often possible. Two graphs sharing all four properties are frequently isomorphic, and if they are an isomorphism can always be found by a careful search. Unfortunately, things don't always turn out so nicely. Graphs sharing the four properties can still be nonisomorphic, making the most patient search for an isomorphism a complete waste of time. This uncertainty puts a little zip into the graph game.

Figure 34

Example
. The graphs of
Figure 35
are not isomorphic, even though they share the four properties: in each
v
= 8 and
e
= 10; each has four vertices of degree 2 and four of degree 3; and they are both in one piece. The structural difference is that the vertices of degree are not related in the same way in the two graphs. In the first graph the vertices of degree 2 come in adjacent pairs:
B
is adjacent to
H
and
D
is adjacent to F. But in the second graph they are completely separated from one another by vertices of degree 3: no vertex of degree is adjacent to any other vertex of degree 2. To see how this prevents the graphs from being isomorphic, we shall systematically try to construct an isomorphism in all possible ways. We begin by noticing that
B
, being of degree 2, would have to correspond to 1, 3, 6, or 8.

First case: B
corresponds to 1.

Then
H
, being adjacent to
B
, would have to correspond to 2 or
7. But
H
must correspond to a vertex having the same degree, so
H
cannot correspond to either 2 or 7. Therefore no isomorphism is possible if
B
is made to correspond with 1.

Figure 35

Second case: B
corresponds to 3.

Then
H
, being adjacent to
B
, would have to correspond to eithe or 5. But
H
must correspond to a vertex having the same degree, so
H
cannot correspond to either 4 or 5. Therefore no isomorphism is possible if
B
is made to correspond to 3.

Third Case: B
corresponds to 6.

Then
H
, being adjacent to
B
, would have to correspond to eithe 4 or 5, which is impossible as we noted in the second case. Therefore no isomorphism is possible if
B
is made to correspond to 6.

Fourth case: B
corresponds to 8.

Then
H
, being adjacent to
B
, would have to correspond to either 2 or 7, which is impossible as we noted in the first case. Therefore no isomorphism is possible if
B
is made to correspond to 8.

We have seen that no isomorphism is possible if
B
is made to correspond to any of 1, 3, 6, or 8. But under any isomorphism,
B
would have to correspond to 1, 3, 6, or 8. Therefore no isomorphism is possible, and the graphs of
Figure 35
are not isomorphic.

Semantics

In graph theory there are two concepts of “sameness” whereby graphs are judged to be “the same”, namely equality and isomorphism. Of these isomorphism is the more fundamental, and the one with which we will be chiefly concerned from now on. It's true that we may care to know, occasionally, whether or not two graphs are equal, but I introduced the notion of equality mostly as a stepping-stone to the more abstract notion of isomorphism.

An indication of the pervasive role isomorphism has in graph theory is the fact that isomorphism has virtually captured the word “is”. In most contexts graph theorists use “is” not to mean “is equal to”, as you would naturally think, but to mean “is isomorphic to”. This is a departure from the usage of school mathematics, and you may find it takes some getting used to. For example a graph theorist would say “the graph of
Figure 36
is the utility graph”, by which he or she would mean that it is isomorphic to the utility graph, though by standard usage the graph of
Figure 36
most certainly “is not” the
utility graph (it is not equal to the utility graph) because its vertex set {1, 2, 3, 4, 5, 6} is different from the vertex set of the utility graph, which (see
Definition 12
) is {
A
,
B
,
C
,
X
,
Y
,
Z
}.

Figure 36

Henceforth we will adopt this semantic convention and use “is” to mean “is isomorphic to”. It may seem that by so doing we are blurring an important distinction, but that's really not the case. In the rest of this book we will discuss only those properties of a graph that are shared by all the graphs isomorphic to it, whether or not they are also equal to it. We still have the distinction between equality and isomorphism to fall back on should it ever be important to maintain, but in the meantime letting “is” mean “is isomorphic to” will emphasize isomorphism as the primary sense in which we will consider graphs to be “the same”.

Accordingly, from now on whenever we say “this graph is that graph” without qualification, it will mean “this graph is isomorphic to that graph; we don't care if they are equal as well”.

Examples
. 1) I say, “the first graph in
Figure 37
is the complement of
UG
.” It is not equal to the complement of
UG
(the second graph in
Figure 37
), because its vertex set {
G
,
H
,
I
,
J
,
K
,
L
} is different from the vertex set of the complement of
UG
, which (by
Definitions 12
and
13
) is {
A
,
B
,
C
,
X
,
Y
,
Z
}. However, the two graphs in
Figure 37
are isomorphic, which is what I meant.

2) I say, “
UG
is a subgraph of
K
₆
.” It is not equal to a subgraph of
K
₆
, because its vertex set {
A
,
B
,
C
,
X
,
Y
,
Z
} is not a subset of
the vertex set of
K
₆
, which is {1, 2, 3, 4, 5, 6}. (See
Definitions 11
and
14
.) However,
UG
is isomorphic to a subgraph of
K
₆
, for instance the one drawn in
Figure 36
, and this is what I meant. You can check for yourself that the graph of
Figure 36
is equal to a subgraph of
K
₆
by drawing
K
₆
and then erasing edges {1, 2}, {1, 3}, {2, 3}, {4, 5}, {4, 6}, and {5, 6}.