Introduction to Graph Theory (39 page)

Examples
.
In
Figure 145a
DCABCD
,
CBC
, and
BACBCDCB
are closed walks;
ACDCACD
,
BCA
, and
CABCD
are open walks.

Figure 145

Definition 36
.
An
euler walk
is a walk that uses every edge in the graph exactly once.

Examples
.
1) In
Figure 145a
DCABC
,
CABCD
, and
CBACD
are open euler walks; there are no closed euler walks.

2)
Figure 145b
has several closed euler walks, one of which is 12345142531; it has no open euler walks.

3)
Figure 145c
has no euler walks, open or closed.

4)
UG
has no euler walks.

It is clear from the definition that a disconnected graph cannot possibly have an euler walk unless all the edges are in one component (see Chapter 4,
Exercise 7
) as in
Figure 145b
. Thus we may as well restrict our attention to connected graphs.

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

Proof
. A vertex is “even” if its degree is an even number—see
Exercise 1
. Though not difficult, the proof is rather wordy. The theorem is a compound of two statements which we shall prove in turn. The first is

(1)
If a graph is connected and has a closed euler walk then every vertex is even.

This is almost obvious. Let
G
be connected with a closed euler walk that begins and ends at, say, vertex “
A
”. Trace the walk with your finger. We start at vertex
A
and leave it along an edge. Since the walk is closed it cannot end at any vertex other than
A
. Thus we will leave every vertex we come to, other than
A
, as many times as we enter it. And since the walk is an euler walk, we will traverse every edge in the graph; so every vertex other than
A
has even degree. Eventually we will enter vertex
A
without being able to leave it—this will be the end of the walk, when we have traversed every edge. Since the walk started at
A
, the degree of
A
is even also.

If you have trouble visualizing this process I suggest you draw some graphs having closed euler walks and follow along. The second half of the theorem is

(2)
If a graph is connected and every vertex is even then it has a closed euler walk.

This is only slightly more difficult than the first half. Let
G
be connected with every vertex even. Select any vertex and call, it “
A
”. Select any edge incident to
A
and traverse it. Leave every subsequent vertex on an edge that has not been used, and continue until forced to stop. The result is a walk beginning at
A
which we can call “
W
”.
W
doesn't repeat any edges because of the way it was constructed.
Figure 146a
depicts a connected graph with every vertex even and vertex
A
chosen. In
Figure 146b
a walk
W
has been constructed according to instructions; notice that
W
is closed. We shall now show that
W
is necessarily closed.

Whenever we pass through a vertex we use two edges, one when we enter it and one when we leave. Every vertex has even degree, and an even number diminished by 2 is still even; so every time we pass through a vertex there remain an even number of unused edges incident to it, though of course this even number may be 0. Thus every vertex that we have either (1) not touched at all or (2) passed through one or more times has either (1) no unused edges or (2) a positive even number of unused edges. The only vertex to which this does not apply is vertex
A
, which we touched but did not pass through when we started tracing
W
; vertex
A
has an odd number of unused edges. Since every vertex that can be entered can be left, except for vertex
A
which we will eventually not be able to leave, it follows that when we are forced to stop it will be at vertex
A
. Thus
W
is necessarily closed.

It might be that
W
does not include every edge of
G
. The walk
W
of
Figure 146b
, for example, does not include every edge of the graph. We shall now show that
W
can be expanded to include any edges left out.

If there are edges of
G
not included in
W
let be “
B
” the first vertex of
W
having incident edges not in
W
. Leave
B
on any unused edge, and leave each subsequent vertex on an unused edge, continuing as long as possible. The result is a walk—call it “
X
”—that starts at
B
and doesn't repeat any edges. By the same argument as before,
X
must be closed—see
Figure 146c
. Splice
X
into
W
and the result is a new walk “
Y
”.
Y
is a closed walk beginning and ending at
A
and repeating no edges. If there are edges of
G
not included in
Y
, let “
C
” be the first vertex of
Y
having edges not in
Y
and repeat the process. Since graphs have only a finite number of vertices and edges, this can't go on forever, and at some point we will find ourselves in possession of a closed walk, beginning and ending at
A
, that repeats no edges and uses every edge of
G
; that is, an euler walk. For the graph of
Figure 146
a second splice was necessary—see
Figure 146d
.

Figure 146

This completes the proof of statement (2) and we have the theorem.

Corollary 30
.
If a particular vertex is selected from a connected graph having every vertex even
,
then it is possible to find a closed euler walk beginning and ending at that particular vertex
.

Proof
. We proved this while we were proving statement (2) above, because we started with an
arbitrary
vertex
A
. It could have been any vertex in the graph.

Theorem 31
.
If a connected graph has an open euler walk then it has exactly two odd vertices
.
Conversely
,
if a connected graph has exactly two odd vertices then it has an open euler walk
.

Proof
. A vertex is “odd” if its degree is an odd number (see
Exercise 1
).

The first half of the theorem is

(1)
If a connected graph has an open euler walk then it has exactly two odd vertices.

Let
G
be connected with an open euler walk that begins at vertex “
A
” and ends at vertex “
B
”. Add a new vertex “
Z
” and two edges {
A
,
Z
} and {
B
,
Z
}. The result is a supergraph
H
of
G
. Take the open euler walk
A
...
B
of
G
, append to it the walk
BZA
of
H
, and we have a closed euler walk
A
...
BZA
in
H
. By
Theorem 30
all vertices of
H
are even, so
G
must have had exactly two odd vertices
A
and
B
.

(2)
If a connected graph has exactly two odd vertices then it has an open euler walk
.

This is the second half of the theorem. Let
G
be connected with exactly two odd vertices “
A
” and “
B
”. Form a supergraph
H
of
G
by adding a new vertex “
Z
” and two new edges {
A
,
Z
} and {
B
,
Z
}. Then
H
is a connected graph with all vertices even, so by Corollary 30
H
has a closed euler walk beginning and ending at vertex
Z
. As
Z
is adjacent only to
A
and
B
, this closed euler walk must look like this:
ZA
...
BZ
. If we remove the two
Z
's the result is
A
...
B
, which must be an open euler walk in
G
.

This completes the proof of statement (2) and we have the theorem.

Corollary 31
.
If a connected graph has an open euler walk
,
then the open euler walk must begin at one of the odd vertices and end at the other
.

Proof
. The proof is contained in the proof of part (1) of
Theorem 31
.

The problem of euler walks is now completely solved. The number of odd vertices in a graph must be even by
Exercise 1
. If that even number is 0 the graph has a closed euler walk; if it is 2 the graph has an open euler walk; and if it is 4 or more the graph has no euler walk.

In his interesting book
Mathematics: the Man
-
Made Universe
, Stein refers to the problem of euler walks as the “problem of the highway inspector”. A highway system can be viewed as a graph, where intersections are the vertices. In order to do his job properly, a highway inspector requires a route taking him over every section of highway in the system. But in order not to waste time, he would like the route not to repeat any sections. In short, the highway inspector is looking for an euler walk.

Hamilton walks

Ireland has produced only one famous mathematician, he a bizarre man named William Rowan Hamilton (1805–1865). In 1859, finding himself short of drinking money, he marketed a puzzle called “Around the World”. It consisted of a dodecahedron, the vertices of which were labeled with the names of major cities; the task was to discover a route along the edges that would pass through each city exactly once.

Definition 37
.
An
open hamilton walk
is a walk that uses every vertex in the graph exactly once. A
closed hamilton walk
is a closed walk that uses the initial vertex exactly twice and all the other vertices in the graph exactly once.

Examples
.
1) The graph of
Figure 147a
has several open hamilton walks, two of which are 12435 and 34521. It has no closed hamilton walks.

2)
Figure 147b
has several closed hamilton walks, two of which are 1234567891 and 7654321987. It has several open hamilton walks, for instance 123456789 and 765432198, which are obtained from the closed hamilton walks by erasing the terminal vertex. Note that every graph with a closed hamilton walk also has an open hamilton walk.