12 Graph Theory

12.1 The bridges of K

¨

onigsberg

The city of K

¨

onigsberg, quietly nestled on the banks of the Pregel River, was in the eigh-

teenth century the setting of a mathematical conundrum. The town had seven bridges

crossing the river, lovely to traverse in the night air, and the townspeople had a habit of

strolling through town in the evening.

The center of the townspeople’s mathematical discussions was the pub on the center

island, with challenges and late-night attempts to “walk the bridges,” to make a tour of

the town crossing every bridge exactly once. Despite the accompanying boasts, rarely

reproducible in the sober morning, this was a difficult task. Most who attempted found

that they had missed a bridge or that they crossed a bridge twice.

Question 95. Can you walk the bridges? Can you find a tour of the town that traverses

each of the seven bridges exactly once?

Interlude. . .