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 (34)

34 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. Unknown says:
    14 September 2015 at 23:15
    This comment has been removed by a blog administrator.
  3. essay best 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. Unknown 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

  5. Rithi Rawat says:
    18 November 2018 at 13:36

    It's really a nice experience to read your post. Thank you for sharing this useful information. If you are looking for more about Best Machine learning training in chennai
    machine learning with python course in Chennai
    machine learning course in chennai

  6. kayal says:
    7 December 2018 at 09:54

    Nice post
    iot courses in Bangalore

    internet of things training course in Bangalore

    internet of things course in Bangalore

  7. Sophie Grace says:
    3 July 2019 at 05:43

    Its not my first time to pay a visit this web page, i am visiting this web site dailly and take good information from here every day. picbear

  8. prabhu says:
    29 August 2020 at 11:55

    Thank you for taking the time to provide us with your valuable information. We strive to provide our candidates with excellent care and we take your comments to heart.As always, we appreciate your confidence and trust in us

    IELTS Coaching in chennai

    German Classes in Chennai

    GRE Coaching Classes in Chennai

    TOEFL Coaching in Chennai

    spoken english classes in chennai | Communication training

  9. OGEN Infosystem (P) Limited says:
    8 January 2021 at 08:19

    Thank you so much for this innovative post, keep it up for more valuable information. Visit Ogen Infosystem for professional Website Designing and SEO Services in Delhi, India.
    Web Designing Company in Delhi

  10. Buy SEO Service says:
    24 March 2021 at 12:25

    Thanksyou for the valuable content.50 High Quality for just 50 INR
    2000 Backlink at cheapest
    5000 Backlink at cheapest
    Boost DA upto 15+ at cheapest
    Boost DA upto 25+ at cheapest
    Boost DA upto 35+ at cheapest
    Boost DA upto 45+ at cheapest

  11. manjot singh says:
    20 April 2021 at 13:09

    Thanks for the Valuable information.Really useful information. Thank you so much for sharing. It will help everyone.

    Full Stack Training in Delhi

  12. CSS Founder says:
    6 January 2022 at 12:08

    Get the best business and informative website by hiring the world class web design company in navi mumbai. Connect with us and get best design and development services.

  13. Unknown says:
    12 January 2022 at 11:54

    This is very good information you have shared in your blog. I love to read your blog on daily basis, I'm waiting for your new blog. Please keep posting like this.
    Upcoming residential projects in sector 79 Noida

  14. CSS Founder says:
    25 February 2022 at 10:13

    Great Information. I hope you will upload these types of articles in the future as well. If you are looking for website designing
    web design company houston

  15. Gaurav's Blog says:
    5 April 2022 at 12:16

    Nice! thank you so much! Thank you for sharing. Your blog posts are more interesting and informative.
    Brackish Water Desalination 100000 GPD R.O. System Djibouti

  16. Akash Kanaujiya says:
    14 April 2022 at 14:43

    Are you a business owner, or a director, as a start-up, your goal is to grow your digital presence? If you are creating a website especially to promote your product, or brand, then i tell you we have the most intelligent web designers contact us if you want to design your business website.
    Website design company sofia

  17. PromoteDial - Prince Kumar says:
    25 April 2022 at 09:24

    PromoteDial is known as the best SEO Company in Noida that provides full solution for digital marketing service. We can rank your website on the first page of Google.

  18. Css Founder PVT. LTD. Web Design says:
    26 April 2022 at 13:19

    Thanks for the informative and helpful post, obviously in your blog everything is good. Website design company in Tiruchirappalli

  19. Akash Kanaujiya says:
    2 May 2022 at 14:12

    If you have any problem related to the website, then contact immediately off CSS Founder. CSS Founder is a website design company, which designs all types of websites and also does SEO.
    Website design company Lari

  20. Css Founder PVT. LTD. Web Design says:
    17 May 2022 at 14:06

    If you are looking for a web designing service provider you have come to the right place Website design company in Palakkad

  21. 7 Hotel Hills and Resorts | BlogSpot says:
    26 July 2022 at 09:36

    Thanks for the article may be useful for everything Luxury Resorts in Lansdowne

  22. PROMOTEDIAL says:
    23 August 2022 at 15:27

    “Social media is about sociology and psychology more than technology.” Seo Company in Sofia

  23. website company says:
    13 October 2022 at 10:28

    Both website design and development at affordable cost. website design company in geona

  24. CSS Founder says:
    27 October 2022 at 10:13

    CSS Founder is the best website designing company in Gurgaon that provides a full website design & development solution at an affordable price. Contact us today and take your business to the next level with CSS Founder.

  25. thorndalemedicalclinic says:
    8 November 2022 at 12:43

    “Drugs are not always necessary. Belief in recovery always is.” Medical center in Dublin

  26. Rio Resort Lansdowne says:
    16 December 2022 at 12:31

    Your article is wonderful and beautiful. Luxury Resorts in Lansdowne

  27. vishal says:
    22 August 2023 at 09:47

    If you are looking to buy online water filter system in Dubai, Aqua Pro is a reliable option. With a range of domestic, commercial, and industrial water filters, Aqua Pro ensures that only the cleanest and purest water passes through its semipermeable film.

  28. ukassignmenthelpp says:
    16 September 2023 at 12:41

    Get the best service of Assignment Help Birmingham. We are the right choice for you.

  29. Website Designing Company in Delhi says:
    19 September 2023 at 12:48

    It is important to choose the right Website designing company in Delhi. There are many options available, but if you want the highest quality and exceptional service, look no further than CSS Founder.

  30. E visa Dubai says:
    3 October 2023 at 10:54

    If you have an Indonesian passport and dream of exploring the vibrant city of Dubai, you're in luck! You can easily apply for a Dubai visa for Indonesia Passport and set out on an unforgettable journey to this dazzling city. With its breathtaking skyscrapers, luxurious resorts, and rich cultural experiences, Dubai has something for everyone. Whether you're planning a short holiday or a longer stay, there are visa options available to suit your needs.

  31. cssfoundergurgaon says:
    29 November 2023 at 13:10

    CSS Founder is a trusted website designing company in India that provides top-notch services. With a strong reputation for quality and reliability, CSS Founder is the ideal choice for anyone looking to create a professional and attractive online presence. Contact us today to experience the best website design services in India.

  32. Saudi e-visa says:
    29 November 2023 at 15:03

    “Man cannot discover new oceans unless he has the courage to lose sight of the shore,” We can understand the importance of traveling by this quote that is written by Andre Gide. So cross your limit and just apply for Saudi arabia visa only at Visitsvisa, trust of millionaire traveler.

  33. Roperro says:
    17 January 2024 at 19:17
    This comment has been removed by the author.
  34. Roperro says:
    17 January 2024 at 19:19

    Celebrate the Republic Day offer and buy the Best quality Bags from Roperro and get two products in the price of one.

Post a Comment