Introduction to Graph Theory (41 page)

Figure 150

Definition 39
.
If some of the edges of a graph
G
, together with their incident vertices, are replaced by skeins, the result is called a
multigraph M
(
G
)
generated by G
.

Note that each multigraph has a unique generator, which can be retrieved by erasing all but one of the lines in each skein. On the other hand, a single graph
G
generates infinitely many multigraphs
M
₁
(
G
),
M
₂
(
G
),
M
₃
(
G
), etc. Note also that every graph is a multigraph since in mathematics the word “some” includes the possibility “none”.

Examples
.
Figure 151
depicts a graph and three multigraphs generated by it.

Figure 151

This book could have been about multigraphs. That is, most of the concepts we have discussed—complement, isomorphism, coloring, genus, etc.—could have been defined to include multigraphs and, had this been done, most of the theorems would have remained true. In this section we shall extend the definitions of “walk” and related concepts to include multigraphs, and shall indicate how to re-prove
Theorems 30
and
31
for multigraphs. The interested reader might care to do the same for other theorems in this book.

Definition 40
.
A
walk
in a multigraph is an alternating sequence
A
₁
B
₁
A
₂
B
₂
...
A
_{n
− 1}
B
_{n
− 1}
A
_n
of not necessarily distinct vertices and edges, beginning and ending with a vertex, such that each edge connects the vertices flanking it in the sequence. If
A
₁
=
A
_n
the walk is
closed
; otherwise it is
open
. A multigraph is
connected
if every pair of vertices are joined by a walk; otherwise it is
disconnected
. An
euler walk
is a walk that uses every edge of the multigraph exactly once. In a multigraph the
degree
of a vertex is the number of incident edges. A vertex is
odd
or
even
according to whether its degree is odd or even.

Examples
.
In
Figure 152
, multigraph a) has open walks such as A3D7E6D6E and closed walks like A4D8C11B2A; it is connected; it has open euler walks such as B2A5D6E7D4A3D8C9B10C11B1C but no closed euler walks; vertex
D
is even, having degree 6, and vertex
B
is odd, having degree 5. Multigraph b) has open and closed walks too, but being disconnected has no euler walks; it has two odd vertices and four even ones.

Figure 152

Theorem 34
.
If a connected multigraph has a closed euler walk then every vertex is even
.
Conversely
,
if a multigraph is connected and every vertex is even, then it has a closed euler walk
.

Proof outline
. There are two separate statements to prove. For each, start with a connected multigraph
M
(
G
) and splice one vertex of degree 2 into each of its edges. The result is a connected
graph H
. Apply
Theorem 30
to
H
and translate back to
M
(
G
). Note the convert-solve-reconvert procedure.

Corollary 34
.
If every vertex of a connected multigraph is even and a particular vertex is selected
,
then it is possible to find a closed euler walk beginning and ending at that particular vertex
.

Theorem 35
.
If a connected multigraph has an open euler walk then it has exactly two odd vertices
.
Conversely
,
if a multigraph is connected and has exactly two odd vertices
,
then it has an open euler walk
.

Proof outline
. We
could
prove this theorem by imitating the proof of
Theorem 34
, the only difference being that we would apply
Theorem 31
instead of
Theorem 30
. But that would be dull. Here's another approach:

Let
M
(
G
) be a connected multigraph with an open euler walk. Add to
M
(
G
) a new edge joining the ends of the open euler walk, producing a new multigraph
M
(
H
) having a closed euler walk. Apply
Theorem 34
to
M
(
H
), remove the new edge, and conclude that
M
(
G
) has exactly two odd vertices.

To get the other half of the theorem let
M
(
G
) be a connected multigraph having exactly two odd vertices. Add a new edge joining the odd vertices, producing a new multigraph
M
(
H
) having every vertex even. Apply
Corollary 34
to
M
(
H
), remove the new edge, and conclude that
M
(
G
) has an open euler walk.

Corollary 35
.
If a connected multigraph has an open euler walk
,
the open euler walk begins at one of the two odd vertices and ends at the other
.

The Königsberg Bridge Problem

Recently there was announced a problem that, while it certainly seemed to belong to geometry, was nevertheless so designed that it did not call for the determination of a magnitude, nor could it be solved by quantitative calculation; consequently I did not hesitate to assign it to the geometry of position, especially since the solution required only the consideration of position, calculation being of no use. In this paper I shall give an account of the method that I discovered for solving this type of problem, which may serve as an example of the geometry of position.

Thus runs the birth notice of “the geometry of position”, a branch of mathematics now called “topology”. The quotation is taken from the first paragraph of Euler's epochal 1736 paper “The Seven Bridges of Königsberg.” Euler goes on to describe the problem as follows.

The problem, which I understand is quite well known, is stated as follows: In the town of Königsberg in Prussia there is an island A, called “Kneiphof ”, with the two branches of the river (Pregel) flowing around it, as shown in
figure [153]
. There are seven bridges,
a
,
b
,
c
,
d
,
e
,
f
and
g
, crossing the two branches. The question is whether a person can plan a walk in such a way that he will cross each of these bridges once but not more than once. I was told that while some denied the possibility of doing this and others were in doubt, there were none who maintained that it was actually possible.
On the basis of the above I formulated the following very general problem for myself: Given any configuration of the river and the branches into which it may divide, as well as any number of bridges, to determine whether or not it is possible to cross each bridge exactly once.

Figure 153

How true to the mathematical spirit is Euler's move to formulate for himself a “very general problem.” Solving one specific problem isn't any fun. Given a specific problem, a pure mathematician will set it aside, ignore it, and turn his/her efforts to constructing an enormous machine—made up of definitions, lemmas, theorems, etc.—that will not only solve the original problem, but also a wide range of similar problems. Of course, more time and energy go into the construction of the machine than would have been required to solve merely the original problem. But the pure mathematician's goal is to have a good time, not to be efficient; and machine-building is a lot more fun than problem-solving.

Euler builds his machine by first abstracting from
Figure 153
the notion of multigraph. Letting land areas be vertices and bridges be edges,
Figure 153
becomes the multigraph of
Figure 154
, and the original problem “whether a person can plan a walk in such a way that he will cross each of these bridges once but not more than once” becomes “does the multigraph of
Figure 154
have an euler walk?”

Euler was not so vain as to christen such a walk an “euler walk”. Nor does there appear in his paper the word “multigraph” or any drawing resembling
Figure 154
. We are attaching modern labels to Euler's thoughts; nonetheless, we are being faithful to them.

Figure 154

Euler's next step is to prove two theorems.

Theorem 36
.
The sum of the degrees of the vertices of a multigraph is
2
e
.

Proof
. Left to the reader. This theorem is an extension to multigraphs of Chapter 2,
Exercise 11
.

Theorem 37
.
Every multigraph has an even number of odd vertices
.

Proof
. Left to the reader. This extends
Exercise 1
.

Finally he proves
Theorems 34
and
35
, and their corollaries; and the machine is complete. Here it is in the builder's own words:

Thus for any configuration that may arise the easiest way of determining whether a single crossing of all the bridges is possible is to apply the following rules:

If there are more than two regions which are approached by an odd number of bridges, no route satisfying the required conditions can be found.

If, however, there are only two regions with an odd number of approach bridges the required journey can be completed provided it originates in one of the regions.

If, finally, there is no region with an odd number of approach bridges, the required journey can be effected, no matter where it begins.