Introduction to Graph Theory (40 page)

Figure 147

3)
The graphs of
Figure 147c
and
d
) have no hamilton walks.

Stein calls the problem of hamilton walks the “problem of the traveling salesman”. A network of towns and highways can be viewed as a graph; a salesman who has stops to make in each town, but doesn't want to waste time by passing through towns more than once, is naturally interested in finding a hamilton walk through the network.

As defined, euler walks and hamilton walks are very similar things. An euler walk uses each edge exactly once, a hamilton walk uses each vertex exactly once. As the problem of euler walks is completely solved, one might expect the same to be true for hamilton walks. Surprisingly, this is not so. Most of what is known about hamilton walks is contained in two rather uninformative theorems that we shall prove in this section. First a lemma, the proof of which I leave to you.

Lemma 32
.
If the sum of the degrees of every pair of vertices of a graph
G
is at least v
− 1,
then

(1)
every pair of vertices are either adjacent to each other or to a common third vertex
,
and

(2)
G is connected
.

Proof outline
. Assume that (1) is false, i.e. that there are vertices
A
and
B
which are not adjacent to one another or to a common third vertex. Derive from this the conclusion that the degree of
A
plus the degree of
B
is less than
v
− 1, contradicting the hypothesis of the theorem. Then (2) follows quickly from (1).

Theorem 32
.
If the sum of the degrees of every pair of vertices of a graph G
is at least
v
− 1,
then
G
has an open hamilton walk
.

Proof
. Let
w
be the largest integer such that the path graph
P
_w
is a subgraph of
G
. See Chapter 2,
Exercise 5
for the definition of “path graph”.

Were
w
to equal
v
,
P
_w
would be an open hamilton walk in
G
.

We shall therefore essay to show that
w
=
v
.

Assume for the sake of argument that
w
<
v
. Our goal is to deduce a contradiction.

Figure 148a
illustrates the subgraph
P
_w
of
G
. Since
w
<
v
,
G
has vertices not in the drawing. And since
G
is connected—which it is by
Lemma 32
—
G
also has edges not in the drawing. These you will have to imagine. Let “
C
” and “
D
” be the vertices at the ends of
P
_w
. Note that
C
and
D
can be adjacent only to other vertices of
P
_w
. For if
C
, say, were adjacent to some vertex
F
which is not a vertex of
P
_w
—as in
Figure 148b
—then
FCJKLMNRD
≅
P
<sub>w
+ 1</sub>
would be a subgraph of
G
in conflict with the maximality of the integer
w
.

Figure 148

Case 1
.
C
and
D
are adjacent.

Let
Q
be a vertex of
G
not included in
P
_w
. By the lemma either
C
and
Q
are adjacent to each other—which we have just noted is impossible since
C
is adjacent only to other vertices of
P
_w
—or
C
and
Q
are adjacent to a common third vertex. This common third vertex, being adjacent to
C
, must be in
P
_w
; say it is
N
, for the sake of example. Then
QNMLKJCDR
≅
P
<sub>w
+ 1</sub>
is a subgraph of
G
, contradicting the maximality of
w
. So we have a contradiction for this case.

Case 2
.
C
and
D
are not adjacent.

For this discussion we shall think of the direction along
P
_w
from
C
toward
D
as being “left to right”. With this understanding we can say “
K
is to the left of
L
” and “
M
is to the right of
L
.”

Let
y
be the number of vertices other than
R
that are adjacent to
D
, so
y
= deg
D
− 1. These
y
vertices are all vertices of
P
_w
as noted above. We want to show that
C
is adjacent to one of the
y
vertices which are immediately to the right of the
y
vertices adjacent to
D
. For example if
y
were 3 and the vertices other than
R
that are adjacent to
D
were
J
,
K
, and
M
, we would want to show that
C
is adjacent to
K
,
L
, or
N
. We do this by contradiction.

Suppose that
C
is not adjacent to any of the
y
vertices which are immediately to the right of the
y
vertices (other than
R
) adjacent to
D
. We shall derive an upper bound for deg
C
. Using first the information that
C
is adjacent only to other vertices of
P
_w
, we can make the rather coarse statement that deg
C
≤
w
− 1. Using next the information that
C
and
D
are not adjacent, we can sharpen this a bit into deg
C
≤
w
− 2. Using finally our supposition that
C
is not adjacent to any of the
y
vertices to the right of the
y
vertices adjacent to
D
, we can say that in fact deg
C
≤
w
− 2 −
y
. Now by the definition of
y
, deg
D
=
y
+ 1; so deg
C
+ deg
D
≤
w
− 2 −
y
+
y
+ 1 =
w
− 1 <
v
− 1, which contradicts the hypothesis of the theorem.

So
C
is adjacent to one of the
y
vertices immediately to the right of the
y
vertices—other than
R
—adjacent to
D
. This situation has been illustrated in
Figure 148d
, with
D
adjacent to
K
and
C
adjacent to
L
.

Let
Q
be a vertex of
G
not included in
P
_w
. As before,
Q
must be adjacent to some vertex of
P
_w
which is in turn adjacent to
C
. If this vertex is
L
, as in
Figure 148e
, then
QLCJKDRNM
≅
P
<sub>w
+ 1</sub>
is a subgraph of
G
, contradicting the maximality of
w
. If this vertex is to the left of
L
, say it is
J
, then
QJCLKDRNM
≅
P
<sub>w
+ 1</sub>
is a subgraph of
G
—contradiction. If it is to the right of
L
, say it is
N
, then we have the same contradiction with
QNRDKJCLM
≅
P
<sub>w
+ 1</sub>
.

So we have contradictions in this case too; thus
w
is not smaller than
v
. Hence
w
=
v
and the theorem is proved.

Theorem 33
.
If the sum of the degrees of every pair of vertices of a graph
G
is at least v
,
then
G
has a closed hamilton walk
.

Proof
.
This is really a corollary to the previous theorem. Let
G
be a graph satisfying the hypothesis. Then by the previous theorem
G
has an open hamilton walk
P
_v
.
Figure 149a
depicts such a walk. All the vertices of
G
are in the drawing, since
P
_v
is a hamilton walk; there may be edges left out, which the reader will have to imagine.

Case 1
.
C
and
D
are adjacent.

Then
G
has a closed hamilton walk, shown in
Figure 149b
.

Case 2
.
C
and
D
are not adjacent.

Then
C
is adjacent to a vertex immediately to the right of a vertex adjacent to
D
, for otherwise (as before) deg
C
≤
v
− 2 − (deg
D
− 1) so deg
C
+ deg
D
≤
v
− 2 − deg
D
+ 1 + deg
D
=
v
− 1 <
v
—contradiction. Hence the situation is as depicted in
Figure 149c
and
G
has a closed hamilton walk.

Figure 149

These two theorems leave much to be desired. First, the hypotheses, though sufficient to guarantee the respective conclusions, are not even remotely necessary. Consider for example the simple graph
C
₆
. Though it obviously has both open and closed hamilton walks, if any two vertices are chosen the sum of their degrees is 4, which is less than 5 =
v
− 1 and therefore too small for either theorem to apply. And so though
C
₆
has both open and closed hamilton walks, we would never know it from the theorems. See
Exercise 8
for more examples.

Second, there is no surprise to them. Paraphrased,
Theorem 32
says that if a graph has rather a lot of edges, and if these edges are rather evenly distributed around the vertices, then the graph has an open hamilton walk.
Theorem 33
says that a graph with even more evenly-distributed edges has a closed hamilton walk. Upon reflection neither statement is startling.

Third, the theorems are hard to apply. To determine if either theorem yields information about a graph with, say, 20 vertices, one would have to compute the degree-sum for each of the 190 possible pairs of vertices. Surely, just by inspecting the graph closely, one could determine if it had hamilton walks in less time than that would take.

There is one respect, however, in which the two theorems are remarkable: they represent practically all that is known about hamilton walks. Though apparently so similar to euler walks, about which everything is known, it seems that hamilton walks are at root much more complicated things.

Multigraphs

Definition 38
.
A
skein
is an object consisting of two dots connected by two or more lines.

Examples
.
The first five skeins are shown in
Figure 150
.