Puzzling Victorian Doodles...Answer

by Paul Curzon, Queen Mary University of London

Ada Lovelace and Charles Babbage had a go at the famous 'Bridges of Konisberg' Puzzle. Can you plot a route around Konigsberg that visits all parts of the city crossing each of the seven bridge only once?

In fact, it is impossible! There is no such route.

The great mathematician Leonard Euler came up with an elegant proof to show this. His first step was to simplify the problem. He drew a new version of the problem, with circles for the land masses - the islands and two banks of the river. He then drew lines between the circles to show which were connected by bridges. Computer Scientists call this kind of drawing a graph. In drawing the graph we have used the computational thinking trick of 'abstraction'. By hiding the information that doesn't really matter we make the problem easier to think about. We don't get distracted by the clutter of irrelevant information. In a graph, the circles are called 'nodes' and they represent the places to visit. The lines which represent how those places are connected are called 'edges' of the graph.

Having done this, Euler realised that you could show it was impossible to come up with a route by thinking about individual nodes and the number of edges connected to them. Any suitable route must visit every node. It must also involve every line (as they are the bridges). Let's suppose there is such a route and we draw a red line over the graph to show it. Think about a node in the middle of that the route. It must have a red line in to it for every red line out from it (or the route would have got stuck at that point). It must therefore have an even number of lines connected to it. The same applies to all nodes in the middle of the route.

An exception to this is the first node on the route, as the red line only has to leave it, not both enter and leave. It can have an odd number of edges from it. Similarly, the last node on the route can have an odd number too.

Now in the Konigsberg problem all the nodes have an odd number of edges. Two of these are the start and end of the route so they are ok, that still leaves two nodes with an odd number of edges though. At least one of those edges (so bridges) in each case wont be on our route. It cannot be a solution. By assuming we have a route, we have found a contradiction. It is therefore impossible for the route to include all the edges ie to cross all the bridges.

The beauty of this argument is that it is an argument about graphs generally not just our particular puzzle. Once you have worked it out, you can apply it to other problems too. It is impossible to find a route around any graph unless it has either no or two nodes with an odd number of edges. If you have a similar route-finding problem then draw it as a graph. You can then apply the same test to it, to see if it is impossible.

We are now using another computational thinking trick, called generalisation. If you can generalise problems and their solutions, then you get future answers for free. You don't have to work it all out again.

Ada and Charles seem to have worked out that there is no solution to the 'Bridges of Konigsberg' problem, given the scribbles they wrote on the sheet with the doodles. They realised it was all about odd and even numbers of bridges. Other drawings on the sheet are also of graphs, though to a different problem - a magic square, so they were obviously thinking about graph problems in general at the time.