## 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.

### 34 Response to "X Bridges of Königsberg"

1. LPs says:
This comment has been removed by a blog administrator.
2. Unknown says:
This comment has been removed by a blog administrator.
3. essay best says:

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:
5. Rithi Rawat says:

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. Sophie Grace says:

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:

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:

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

11. manjot singh says:

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:

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:

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:

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:

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:

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:

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:

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

19. Akash Kanaujiya says:

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:

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:

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

22. PROMOTEDIAL says:

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

23. website company says:

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

24. CSS Founder says:

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:

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

26. Rio Resort Lansdowne says:

Your article is wonderful and beautiful. Luxury Resorts in Lansdowne

27. vishal says:

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:

29. Website Designing Company in Delhi says:

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:

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:

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:

“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:
This comment has been removed by the author.
34. Roperro says:

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