Introduction to Graph Theory (5 page)

Figure 3

Figure 4

It appears then that graph diagrams can look quite different, yet in some sense be the same.

Definition 8
. We will say that two graphs are equal if they have equal vertex sets and equal edge sets. And we will say that two graph diagrams are equal if they represent equal vertex sets and equal edge sets.

It may seem that this definition is circular, as it defines “equality” in terms of equality. But it is not. Equality of sets is an old concept, introduced in
Definition 4
, which we are using to define the new concepts of equality of graphs and equality of graph diagrams.

Examples
. 1) The graph
G
having vertex set {
P
,
Q
,
R
,
S
,
T
,
U
} and edge set {{
P
,
Q
}, {
P
,
R
}, {
Q
,
R
}, {
S
,
U
}} is equal to the graph
L
having vertex set {
T
,
P
,
R
,
Q
,
U
,
S
} and edge set {{
Q
,
R
}, {
R
,
P
}, {
U
,
S
}, {
P
,
Q
}}; and
G
is equal to any other graph differing from
G
only by a permutation of set elements. I won't belabor the point as you have probably taken it for granted all along. The first part of the definition only makes this understanding explicit.

2)
Though the second part of the definition isn't surprising either on an intellectual level, it is interesting visually. By it the two diagrams in
Figure 5
are equal. In fact, they and
Figures 3
and
4
are all equal as they all represent
G
; they have vertices
P
,
Q
,
R
,
S
,
T
,
U
and no others, and edges {
P
,
Q
}, {
P
,
R
}, {
Q
,
R
}, {
S
,
U
} and no others. Apparent differences are irrelevant.

3) The diagrams of
Figure 6
are equal. They represent the graph
H
mentioned in the last section.

4) The diagrams of
Figure 7
are equal. They represent
J
from the last section.

I want to emphasize that to verify that two graph diagrams are equal, it's not necessary to write down their vertex sets and edge sets. All you have to do is check that they have the same number of vertices, that the vertices have the same names, and that the graphs have the same adjacency structure. For example, without writing anything down I can verify that the diagrams of
Figure 5
are equal, by saying to myself: “Both graphs have six vertices labeled
P
,
Q
,
R
,
S
,
T
, and
U
. In both graphs
P
is adjacent to
Q
and
R
and to nothing else,
Q
is adjacent to
P
and
R
and to nothing else,
R
is adjacent to
P
and
Q
and to nothing else,
S
and
U
are adjacent only to each other, and
T
is isolated.”

Figure 5

Figure 6

Figure 7

Cautions

1) It so happens that pencil and paper, blackboard and chalk are handy, so graphs are usually represented by flat drawings. But three-dimensional models made of sticks and wads of chewing-gum would do as well. The plane surface is just another incidental feature of a diagram. In a later chapter we will draw graphs on doughnuts!

2) The object in
Figure 8
is not a graph. This is because an edge is by definition a set of two vertices, hence cannot exist without a vertex at each end. We have already seen that a graph can have a vertex without incident edges (an isolated vertex); note now that edges, on the other hand, must always have two incident vertices.

3) The graph of
Figure 9
is not equal to the graph of
Figure 5a
, because in
Figure 9
there is no edge connecting
P
to
R
. Vertex adjacency is not like electric current: it is not transmitted through the intermediary vertex
Q
.

Figure 8

Figure 9

4) The graphs in
Figure 7
have a number of edge-crossings. An edge-crossing is not a vertex, but yet another incidental feature of a diagram. Edge-crossings can always be avoided in three-dimensional models, so they are certainly not essential properties of a graph. But even when, as often happens, they cannot be avoided in our standard two-dimensional diagrams, they should not be taken for vertices. To prevent ambiguity we've been using heavy dots for vertices.

5) Sharp corners on edges aren't vertices either; for example in
Figure 5b
the only vertices are
P
,
Q
,
R
,
S
,
T
, and
U
.

6) The definition of graph precludes “loops” (vertices joined to themselves) and “skeins” (several edges joining the same pair of vertices). This is because a loop would translate abstractly as an “edge” of the form {
A
,
A
}, which is impossible as {
A
,
A
} is not a set (see p. 14 and
Definition 5
); and a skein would imply the multiple inclusion of an element {
A
,
B
} in the edge collection, which would prevent the collection of edges from being a set as required. Were we to allow skeins but not loops we would have something called a “multigraph”; the result of allowing both is called a “pseudograph”. We will discuss multigraphs in
Chapter 8
, but we will not discuss pseudographs. See
Figure 10
.

7) The edges of a graph are undirected; that is, any impression that the notation {
A
,
B
} may give of an edge “going from
A
toward
B
” is unintentional. Remember that {
A
,
B
} = {
B
,
A
}. A graph-like thing in which the edges have direction is called a “digraph”. We will not discuss digraphs in this book. See
Figure 11
.