Proof and the Art of Mathematics

136 Chapter 12

grand circuit. Eventually, one must come back to w, by the same reasoning as before. We

absorb the detour into the grand circuit, by ﬁrst following the grand circuit from v

to w,

and then following the detour from w to w, and then continuing with the grand circuit.

By repeating this process ﬁnitely many times so as to add additional detours, we thereby

construct a circuit from v

to v

that uses every edge of the graph exactly once. So it is an

Euler circuit, as desired.

Corollary 98. There is no Euler circuit in the K

onigsberg graph. Therefore, there is

no walking tour of the bridges in K

onigsberg traversing each bridge exactly once, while

starting and ending in the same location.

Proof. The K

onigsberg graph has four vertices, with respective degrees of 3, 3, 3, and 5,

all odd. So by theorem 97, there can be no Euler circuit in this graph. Therefore, there can

be no walking tour of the town that traverses each bridge exactly once, while starting and

ending in the same location.

Great! We seem to have solved the K

onigsberg bridge problem. Or have we? The

corollary shows that one cannot successfully walk the bridges in K

onigsberg by a tour that

starts and ends in the same place. This explains why the boasts of success at the pub were

never reproducible. But perhaps the townspeople would count it as a successful walking of

the bridges if a tour happened to start and end in different parts of town? That is, perhaps

the problem concerns Euler paths rather than Euler circuits. Can we prove an analogue of

theorem 97 for Euler paths, rather than Euler circuits? Yes, we can.

Theorem 99. A ﬁnite connected graph admits an Euler path if and only if there are at most

two vertices with odd degree.

Proof. (→) Suppose that G is a ﬁnite connected graph with an Euler path. Fix such a path,

and observe as in theorem 97 that every vertex v appearing on it, except possibly the initial

and terminal vertices, must have even degree, because the path enters each such vertex on

one edge and departs on another, using up two edges with each visit. So there are at most

two nodes with odd degree, as desired.

(←) One can mount a direct argument for the converse implication here, with an argu-

ment similar in style to that of theorem 97. But let us instead deduce this implication more

simply as a corollary to theorem 97. We begin with a ﬁnite connected graph G in which

there are at most two vertices with odd degree. If there are no odd-degree vertices, then we

already know by theorem 97 that there is an Euler circuit, and this is also an Euler path.

So assume that there is an odd-degree vertex. It follows that there must be exactly two

odd-degree vertices v and w, since by exercise 12.2 there cannot be just one. Let G

be the

graph obtained by adding an edge between the two odd-degree vertices of G. So this is a

ﬁnite connected graph in which every vertex now has even degree. So by theorem 97 there

is an Euler circuit in G

. By exercise 12.1, we may assume that the circuit ends exactly