134 Chapter 12

The question had ultimately stumped the town’s inhabitants but was finally answered

in 1736 by mathematician Leonhard Euler, whose solution gave rise to a new field of

mathematics: graph theory. He had in effect invented a new field of mathematics in order to

solve the problem. Euler approached the problem by representing it abstractly, finding the

mathematical essence of the situation. For this problem, what mattered about the bridges

and the town’s layout was not their exact shape and location but, rather, the fact that the

town had essentially four distinct land masses or neighborhoods—the north bank, the south

bank, the central island, and the island at the east—and these were connected by the bridges

in a certain way. What mattered was the logical connectivity of those neighborhoods by

the bridges.

S

C

N

E

For the purpose of finding a tour, therefore, we

may imagine each neighborhood as a single lo-

cation, a single point or vertex, and each bridge

is a line connecting one vertex to another. Thus,

the K

¨

onigsberg bridge problem is represented ab-

stractly by what we now call the K

¨

onigsberg graph,

pictured here. More generally, a graph is any col-

lection of vertices and edges, where each edge con-

nects one vertex to another or to itself. One can

represent a graph visually by drawing the vertices

as dots and the edges as lines between them.

12.2 Circuits and paths in a graph

A

B

C

F

D

E

A path in a graph is a sequence of vertices

in the graph, with each pair of vertices con-

nected by an edge. For graphs that happen

to have multiple edges between some of

their pairs of vertices, as in the K

¨

onigsberg

graph, we require also that the path should

indicate which particular edge was taken at

each step, when there was a choice. We

may represent each path visually by in-

dicating how the edges are traversed. A

graph is said to be connected if any pair

of vertices admits a path from one to the

other. A circuit in a graph is a path that starts and ends at the same vertex.

Definition 96. An Euler circuit is a circuit that uses every edge in the graph exactly once.

An Euler path is a path that uses every edge exactly once.