A contemporary Eulerian walk over the bridges of Kaliningrad

Abstract

To commemorate the three-hundredth anniversary of the birth of Leonhard Euler (1707–83) the author outlines the history of one of Euler's most famous and most easily understood contributions to mathematics, the problem concerning the Bridges of Königsberg, and describes a modern Eulerian walk over the bridges of present-day Kaliningrad, Russia. This article is a shortened form of Mallion (2007), but with the addition of a Postscript.

Acknowledgements

I am very grateful to Professor Dr Ivan Gutman, Editor of MATCH Communications in Mathematical and in Computer Chemistry, who gave his copyright permission and, through his office, that of the Faculty of Science of the University of Kragujevac (Serbia), for me to condense the paper (Mallion 2007) that I had earlier published in that journal. The Postscript contains new material that was not presented in that article. Readers wanting further detail may consult the original paper.

I thank Professor Dr Hans-Dietrich Gronau for kindly bringing the references Taylor (2000) and Gribkovskaia et al. (2007) to my attention. I am also indebted to Professor Gilbert Laporte, Dr Peter Taylor, and my friend and colleague Paul Pollak for very helpful and cordial discussion and correspondence. My final thanks are reserved for my erstwhile travelling companion, Paweł Skrzyński, who had the courage, patience, and resourcefulness to accompany, support, and guide me on the ‘voyage of discovery’ here described.

Notes

¹ It may be noted in passing that in presenting for the first time the graph depicted in Figure 5, Rouse Ball (1892) referred to edges as ‘branches’ and vertices as ‘points’ and, on other occasions, as ‘nodes’. He did not mention a ‘graph’ as such (despite the fact that that term had already been coined in Sylvester (1877–78) some 15 years earlier); instead, he called the resulting diagram a ‘network’. It is clear that by this he meant what would now be called a graph. Further, he explicitly cited Listing's Toplogie (Listing 1847). In considering the geographical map of Königsberg (Figure 4), Rouse Ball simply claimed that ‘… it is evident that the question will not be affected if we suppose the [landmasses] to diminish to points and the bridges to lengthen out. In this way we ultimately obtain a geometrical figure or network.’ He then illustrated the equivalent of Figure 5. Modern authors might dispute the appropriateness of the adjective ‘geometrical’ in the quotation, preferring, perhaps, ‘topological’, but would agree the appellation ‘network’. It was in this way that Rouse Ball metamorphosed the geographical map depicted in Figure 4 into the familiar graph shown in Figure 5.

² Gribkovskaia et al. (2007) claim that the Schmiedebrücke was constructed in 1397. However, in Figure 2, and Mallion (2007), I have stated that it was constructed in 1379. Subsequent correspondence with Professor Laporte (2007) has confirmed that all of us used the same source, a postcard-set issued in 2005 to commemorate the city's 750th anniversary. This source is inconsistent in its information about the Schmiedebrücke, possibly as the result of a misprint: in one place the date of construction is given as 1379 and in another as 1397. For full details see Mallion (2007).

³ This is assuming that before the extra bridge was added the system had two vertices of odd degree and two of even degree. If no assumptions are made about the state of the network before the extra bridge is added, a modified probability argument shows that after the addition of a further bridge the probabilities of (a) a graph with an Eulerian circuit (b) a graph with an Eulerian walk but not an Eulerian circuit (c) a graph with no Eulerian walk, will remain as 1/8, 3/4, and 1/8, respectively.