X Bridges of Königsberg

The recent Spiked Math comic strip proposes some cheats to build an Eulerian path over the famous bridges of Königsberg, which was originally impossible. Here is the strip:


It turns out that in practice another solution worked out (in fact, the mix of the engineer’s and mythbuster’s solutions). You can ruin the city during a world war and then transfer it to Russians, who will build the new bridges instead. I’ve been to Kaliningrad (the city has been renamed too) two years ago, but did not try to solve the Euler’s problem in field. Let’s find out if it is possible now. Look at the modern map:

View Königsberg bridges in a larger map

So, the modified Spiked Math’s scheme looks as follows (the new bridges are shown in light blue):

Is there an Eulerian path nowadays, i.e. can you walk through the city and cross each bridge once and only once? Recall the theorem:
A connected graph allows an Eulerian path if and only if it has no more than two vertices of an odd degree.
In the picture above, two pieces of land have even number of incident bridges, while the Kneiphof island in the center has degree 3, and the left bank (in the bottom) has degree 5. This means that now Eulerian paths exist. Any such path should begin in the left bank and end in the island, or vice-versa. It may be a good idea to finish your journey near the grave of Immanuel Kant. :) However, there is no Eulerian conduit, i.e. closed Eulerian path.

PS. 1. If you zoom out the above map, you’ll see one more piece of land and two more bridges on the East. However, it only adds a vertex of degree 2, and swaps parity of the banks, so the properties of the new graph are similar, you just need to start/finish your journey in the right bank, not the left one (and walk 10 km more).
2. When I was preparing this article, I found a similar analysis. It used an old map, so the Jubilee bridge and the 2nd Estacade bridges were not marked (they were built in 2005 and 2012, respectively), and also ignored the Reichsbahnbrüke (railroad bridge, but seems pedestrian-accessible).
3. It would be more interesting to analyze the bridge graphs of other cities with more islands like St. Petersburg (several hundred bridges) or Amsterdam (numerous bridges/canals, but have structure).
4. Here is Euler’s original paper (in Latin) with his drawings of the above schemes.

Read Users' Comments (12)

12 Response to "X Bridges of Königsberg"

  1. LPs says:
    8 February 2014 at 08:12
    This comment has been removed by a blog administrator.
  2. Computertricksweb Blogspot says:
    14 September 2015 at 23:15
    This comment has been removed by a blog administrator.
  3. write my research papers says:
    27 March 2017 at 18:14

    Good read to follow. If this is possible, I am really going to try this for other cities and like your work though. Good effort.

  4. Gokul Ravi says:
    26 May 2018 at 09:24

    nice blog
    android training in bangalore
    ios training in bangalore
    machine learning online training

  5. Gokul Ravi says:
    26 May 2018 at 09:27

    useful blog
    python interview questions
    cognos interview questions
    perl interview questions
    vlsi interview questions
    web api interview questions
    msbi interview questions

  6. Gokul Ravi says:
    26 May 2018 at 09:27

    laravel interview questions aem interview questions
    salesforce interview questions
    oops abab interview questions itil interview questions
    informatica interview questions
    extjs interview questions

  7. Gokul Ravi says:
    26 May 2018 at 09:27

    sap bi interview questions
    hive interview questions
    seo interview questions
    as400 interview questions
    wordpress interview questions accounting interview questions
    basic accounting and financial interview questions

  8. Amar G says:
    12 June 2018 at 14:38

    Iot Training in Bangalore
    Machine Learning Training in Bangalore
    Pcb Training in Bangalore
    Devops Training in Bangalore

  9. Amar G says:
    13 June 2018 at 10:02

    Nice Training
    Data Science Training in Chennai

  10. Gokul Ravi says:
    13 June 2018 at 13:33

    nice blog
    hadoop training in chennai

  11. Gokul Ravi says:
    13 June 2018 at 13:36

    nice blog
    android training in bangalore
    ios training in bangalore
    machine learning online training

  12. Amar G says:
    26 June 2018 at 13:29

    nice blogs about financial accounting at The Basic Financial training in bangalore

Post a Comment