Leonhard Euler, the outstanding Swiss mathematician, 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.
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 shows there are seven bridges from the left bank, seven from the right bank, 10 from Île de la Cité and six from Île Saint-Louis. This makes 30 in all but, as each bridge is double-counted, there are in total 15 bridges.
Inspired by Euler, let us seek walking routes through the centre of Paris that cross each bridge exactly once. We distinguish between open routes that link from one point to another, and closed routes that lead back to the starting point. We pose three problems. The first is this: starting from Saint-Michel on the left bank, walk continuously so as to cross each bridge exactly once. The second problem is not so simple: start at Notre-Dame Cathedral, on Île de la Cité, and cross each bridge exactly once. The third problem is this: find a closed route crossing each bridge once and returning to its starting point.
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 node must have a corresponding exit link. Thus, there can be at most two nodes with an odd number of links. Moreover, if any node has an odd number of links, there are no closed routes.
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. So, the first problem is easily solved.
Since there are an even number of bridges to Île de la Cité, Notre-Dame Cathedral cannot be at the start or end of the route: the second problem has no solution. Finally, since both banks must be termini, there is no closed route and the third problem is also impossible to solve.
Euler's original problem, The Seven Bridges of Königsberg, had no solutions at all, as each of the four nodes had an odd number of links. His problem, discussed in virtually every textbook on graph theory, is considered as the first real problem in topology. This branch of mathematics is concerned with continuity and connectivity, and studies properties that remain unchanged under continuous deformations, such as stretching or bending but not cutting or gluing. Topology is a powerful unifying theme in modern mathematics.
Peter Lynch is emeritus professor at the school of mathematical sciences, University College Dublin. He blogs at thatsmaths.com