Introduction to Graph Theory (9 page)

Steel balls and rubber bands
. This first suggestion is intended primarily for people with a good intuitive grasp of spatial relationships. Think of a graph as a network of steel balls (vertices) and rubber bands (edges). We assume the balls will remain in whatever position we place them and that the rubber bands will never break. Under this interpretation, isomorphic graphs are graphs that can be rearranged to look like one another.

Example
. The graphs of
Figure 24
are isomorphic. The first can be rearranged to look like the second, as shown in
Figures 25
and
26
. Start (
Figure 25
) by pulling triangle 1–5–3 down and away from triangle 6–2–4. This inverts edge {1, 4} and stretches edges {5, 2} and {6, 3}. Now with edge {1, 4} as an axis (
Figure 26
), flip triangle 1–5–3 over so that vertices 5 and 3 exchange places. This twists edge {1, 4} and untangles edges {5, 2} and {6, 3}. The result looks like the second
graph in
Figure 24
, so we can conclude that the graphs in
Figure 24
are isomorphic. Moreover, we have discovered a specific isomorphism between the original graphs, which I have indicated by parenthetical labels in
Figure 27
. I obtained it by associating the labels of the second graph in
Figure 26
to those of the second graph in
Figure 24
.

Figure 24

Figure 25

Figure 26

Figure 27

Properties preserved by isomorphism
. This is for everyone. We have seen that isomorphism preserves vertex adjacency; it preserves a number of simpler properties as well, of which we will consider four.

(i)
The number of vertices
. An isomorphism is a one-to-one correspondence between vertex sets and vertex sets are finite (see
Definition 5
), so isomorphic graphs must have the same number of vertices.

(ii)
The number of edges
. An isomorphism induces a one-to-one correspondence between edge sets and edge sets are finite too (because the vertex sets are finite), so isomorphic graphs must have the same number of edges.

Before considering the next two properties preserved under isomorphism, we need a definition.

Definition 17
. The degree of a vertex is the number of edges incident to it.

Examples
. 1) The graph of
Figure 28
has two vertices (
H
and
I
) of degree 0, two vertices (
E
and
G
) of degree 1, three vertices (
A
,
D
, and
F
) of degree 2, and two vertices (
B
and
C
) of degree 3.

2) Each vertex of
K
₁₅₃
has degree 152.

(iii)
The distribution of degrees
. In isomorphic graphs corresponding vertices have the same degree, because isomorphism preserves vertex
adjacency. Consequently if a graph has, say, one vertex of degree five vertices of degree 3, and two vertices of degree 4, then any graph isomorphic to it will have one vertex of degree 1, five vertices of degree 3, and two vertices of degree 4.

Figure 28

(iv)
The number of “pieces” of a graph
. I want to defer a precise definition until later (p. 113), but I think you'll get my meaning if I tell you that the two graphs of
Figure 27
are each “in one piece” and the graph of
Figure 28
is “in four pieces”. At first glance the graph of
Figure 17f
might appear to be “in one piece”, but it's really “in two pieces” as it is equal to the graph of
Figure 17e
. Since isomorphism preserves vertex adjacency it preserves the number of pieces of a graph, that is, isomorphic graphs must be composed of the same number of pieces.

These properties are useful in two ways. First, they can be used to prove that graphs are not isomorphic. Since all four properties are preserved by isomorphisms, a pair of graphs differing in any one of those four respects cannot possibly be isomorphic.

Examples
. 1) If the graphs of
Figure 29
were isomorphic, they would have the same number of vertices. The first has
v
= 6 and the second has
v
= 5, so they are not isomorphic. One reason is enough, but here are two more: their degree distributions are different, for example the first has two vertices of degree 1 and the second has only one vertex of degree 1; and they have different numbers of pieces, the first being in two pieces while the second is in one piece.

2) The graphs of
Figure 30
are not isomorphic because they have different numbers of edges: the first has
e
= 6 and the second has
e
= 5. Also, the first has a vertex of degree 4 and the second has no vertex of degree 4. They have the same number of vertices, and are both in one piece.

3) The graphs of
Figure 31
are not isomorphic because they have
different degree distributions: the first has one vertex of degree 4, two of degree 5, and four of degree 6, whereas the second has no vertices of degree 4, four of degree 5, and three of degree 6. They share the other three properties: they have the same
v
's and
e
's and they are both in one piece.

Figure 29

Figure 30

4) The graphs of
Figure 32
have the same number of vertices (6), the same number of edges (6), and the same distribution of degrees (all vertices have degree 2). Yet they are not isomorphic because the first is in one piece and the second is in two pieces.

The second use to which the four properties can be put is that they can provide the basis for a conjecture that two graphs are isomorphic. Even if a pair of graphs share all four properties, they are not necessarily isomorphic; but having checked that they do not differ in these four obvious ways, it is at least less of a gamble to invest some time searching for an isomorphism.

Figure 31