ThatsMaths

Leonhard Euler considered a problem known as The Seven Bridges of Königsberg. It involves a walk around the city now known as Kaliningrad, in the Russian exclave between Poland and Lithuania. Since Kaliningrad is out of the way for most of us, let’s have a look closer to home, at the bridges of Paris. [TM073: search for “thatsmaths” at irishtimes.com ]

In the centre of Paris, two small islands, Île de la Cité and Île Saint-Louis, are linked to the Left and Right Banks of the Seine and to each other. We consider only bridges that link the two islands to each other or to the river banks, and ignore all other bridges spanning the Seine. The figure below shows the following numbers of bridges:

• Left Bank: 7 bridges

• Right Bank: 7 bridges

• Île de la Cité: 10 bridges

• Île Saint-Louis: 6 bridges

These numbers sum to 30 but, as each bridge is double-counted, there are in total 15 bridges.

Image from Wikimedia Commons.

Let us seek walking routes through the centre of Paris that cross each bridge exactly once. We can distinguish between open routes that link from one point to another, and closed routes that lead back to the starting point. Here are four problems:

1.  Starting from Saint-Michel on the Left Bank, walk continuously so as to cross each bridge exactly once.
2.  Once again, start at Saint-Michel but find a closed route that ends back at the starting point.
3.  Start at Notre-Dame Cathedral, on Île de la Cité, and cross each bridge exactly once.
4.  Find a closed route that crosses each bridge once and arrives back at Notre-Dame.

Try these puzzles before reading on.

*        *        *

Euler reduced the problem to its basics, replacing each piece of land by a point or node and each bridge by a link joining two nodes. He saw immediately that any node not at the start or end of the walk must have an even number of links: every link into the point must have a corresponding exit link. Thus, there can be at most two points with an odd number of links.

For the Paris problems, both banks of the Seine have seven bridges, an odd number. The two islands each have an even number of links. Thus, the Left and Right Banks must be at the start and end of the route.

It is simple to find a route starting at Saint-Michel and ending at Hôtel de Ville on the Right Bank, but impossible to find a closed route, ending back at Saint-Michel. So, problem (1) is easily solved, but Problem (2) is impossible to solve.

Since the two islands each have an even number of bridges, they can only be internal points of the route. So problems (3) and (4) have no solutions. [Of course, problems (2) and (4) are identical: a closed route can start and end at any point!].

Euler’s problem had no solutions at all, as each of the four nodes had an odd number of links. His problem is considered as the first real problem in topology and is discussed in virtually every textbook on graph theory.

Other Puzzles

Q1: On the map of central St. Petersburg, shown below, twelve bridges are marked by pairs of red dots.

(A) Can you find an open route crossing each bridge once?

(B) Can you find a closed route?

Central St Petersburg

Q2: This is for people who love 1000-piece jigsaw puzzles. The figure below is an old map of Amsterdam. Focus on the region within the ring of bastions.

(A) Search for a route, open or closed, that crosses each bridge exactly once.

(B) Using a less arduous method, draw conclusions about the feasibility of finding such a route.

Old Amsterdam

*        *        *        *        *        *

Peter Lynch’s book about walking around the coastal counties of Ireland is now available as an ebook (at a very low price!). For more information and photographs go to RRI.