Introduction to Graph Theory (42 page)

These rules solve completely the problem initially proposed.

Once the machine is built and stands looming over the puny problem that suggested its construction, the pure mathematician can act out his/her violent fantasies by activating the machine and watching it pulverize the original problem. In our situation, feeding the Königsberg Bridge Problem to Euler's machine produces an immediate solution: No, one cannot take a walk and cross every bridge exactly once because there are four regions touched by an odd number of bridges. Or, in modern terminology,
Figure 154
has no euler walks because it has four odd vertices.

Euler's paper is a first-rate example of mathematical thinking. For that reason it is required reading in many college English courses.

In the last section we remarked that this book could have been about multigraphs; one might wonder that it hasn't been, since multigraph theory is apparently older than graph theory. The reason is that the added complexity of multigraphs makes them more difficult to deal with, but there are virtually no interesting multigraph theorems to make the added difficulty worthwhile. A theorem in multigraph theory almost always has an equally interesting counterpart in graph theory.

By the way, Königsberg is not on any map. The town has been renamed “Kaliningrad”; it is in Russia on the Baltic Sea.

Exercises

  
1.
  
Definition
.
A vertex of a graph is
odd
if its degree is an odd number; otherwise it is
even
.

Use
Exercise 11
of Chapter 2 to prove that every graph has an even number of odd vertices.

  
2.
  
Find all integers
v
≥ 2 for which

        
a)
  
K
_v
has an open euler walk

        
b)
  
K
_v
has a closed euler walk

        
c)
  
K
_v
has an open hamilton walk

        
d)
  
K
_v
has a closed hamilton walk.

  
3.
  
Trace each drawing in
Figure 155
without lifting your pencil from the paper or going over any lines more than once, a) is a bad puzzle because it can't be done no matter where you start (explain why); b) is a bad puzzle because it
can
be done no matter where you start (explain why); c) is a good puzzle because it can be done, but only if you start at one of two places (explain why).

  
4
.
  
In chess, a “knight's move” consists of two squares either vertically or horizontally and then one square
in a perpendicular direction. Depending on where the knight is situated, he has a minimum mobility of two moves—when in a corner—and a maximum mobility of eight moves, as shown in
Figure 156
. Let
C
be a graph with
v
= 64, its vertices corresponding to the squares of a chessboard. Let two vertices of
C
be joined by an edge whenever a knight can go from one of the corresponding squares to the other in one move. Does
C
have an euler walk? (You don't have to draw
C
to answer.)

Figure 155

Figure 156

  
5.
  
Prove that the graph
C
of the previous exercise has a closed hamilton walk. Such a walk is called a “knight's tour” by puzzle
enthusiasts.

  
6.
  
Figure 157
depicts a system of bridges and land areas. Can you take a walk and cross each bridge exactly once? If so, where do you start and finish? Blow up the bridge from
H
to
I
and answer the same two questions.

  
7.
  
For each integer
v
≥ 2, find a graph with
v
vertices in which the sum of the degrees of every pair of vertices is at least
v
− 1, but which has no closed hamilton walk. Of course the graph will have an open hamilton walk by
Theorem 32
.

Figure 157

  
8.
  
Show that every path graph
P
_v
(see Chapter 2,
Exercise 5
) has an open hamilton walk, though
Theorem 32
is applicable only to
P
_z
and
P
₃
. Then show that every wheel graph
W
_v
(see Chapter 2
Exercise 6
) has a closed hamilton walk, though
Theorem 33
is applicable only to
W
₄
,
W
₅
, and
W
₆
.

  
9.
  
Satisfy yourself that every graph with
v
vertices and a closed hamilton walk is a supergraph of the cyclic graph
C
_v
. Then use this fact to prove that if a graph has a closed hamilton walk then its connectivity
c
is at least 2 (see Chapter 4,
Exercise 11
).

10.
  
There are
v
guests to be seated at a single round table. Each guest is acquainted with at least {
v
/2} of the others. Prove that they can be seated in such a way that each guest is between two acquaintances. (If
v
/2 is not a whole number, the braces round it up to the next whole number.)

11
.
  
Prove: if
n
≥ 2 and
G
is connected with 2
n
odd vertices then
G
has
n
open walks which, together, use every edge of
G
exactly once.

12.
  
Draw four graphs with
v
= 8, the first with an euler walk but no hamilton walk, the second with a hamilton walk but no euler walk, the third with both and the fourth with neither. This indicates that there is no simple relationship between euler walks and hamilton walks. (There is, however, a complicated relationship— see
Exercise 18
.)

13.
Definition
. If
G
is a graph with
e
≠ 0 then the
line graph of G
, denoted “
L
(
G
)”, is the graph having one vertex corresponding to each edge of
G
and such that two vertices of
L
(
G
) are joined by an edge whenever the corresponding edges of
G
share a vertex.

Examples
.
1)
Figure 158a
is a graph whose line graph has been drawn in
Figure 158b
. Each vertex of
L
(
G
) corresponds to an edge of
G
. In the figure this correspondence has been made explicit by numbering the edges of
G
and giving the same numbers to the corresponding vertices of
L
(
G
). Two vertices of
L
(
G
) are joined whenever the corresponding edges of
G
share a vertex.

Figure 158

2)
Figure 158c
is the line graph of
K
₄
.
K
₄
has six edges, each adjacent to four of the others, thus its line graph has six vertices, each adjacent to four of the others.

Of the eleven graphs with
v
= 4 (drawn in
Figure 45
),
N
₄
has no line graph because it has
e
= 0 and we have just drawn the line graph of
K
₄
. Draw the line graphs of the remaining nine.

14
.
  
Prove: if
G
has a closed euler walk then
L
(
G
) has both a closed euler walk and a closed hamilton walk.

15.
  
Find a graph
G
such that
L
(
G
) has both a closed euler walk and a closed hamilton walk but
G
has no closed euler walk. This shows that the converse of
Exercise 14
is false.

16.
  
Prove: if
G
has a closed hamilton walk then
L
(
G
) has one too.

17.
  
Find a graph
G
such that
L
(
G
) has a closed hamilton walk but
G
hasn't. This shows that the converse of
Exercise 16
is false.

18.
  
Definition
.
If
G
is a graph with
e
≠ 0, then the
trisection graph of G
, denoted “
T
(
G
)”, is the expansion of
G
formed by splicing two vertices of degree 2 into every edge of
G
.