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

### 25 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. Unknown says:
6. Unknown says:
7. Unknown says:
8. amar says:
9. amar says:

Nice Training
Data Science Training in Chennai

10. Unknown says:

nice blog
hadoop training in chennai

11. Unknown says:
12. amar says:

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

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

14. Dharani M says:
15. kayal says:
16. kayal says:
17. 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

18. Priyanka says:

Attend The Machine Learning course Bangalore From ExcelR. Practical Machine Learning course Bangalore Sessions With Assured Placement Support From Experienced Faculty. ExcelR Offers The Machine Learning course Bangalore.
Machine Learning course Bangalore

19. CloudLearn ERP says:

It's truly an honor to run across informational content like this. You are clearly knowledgeable on this topic and you have unique views to share.
Best Data Science training in Mumbai

Data Science training in Mumbai

20. nisharoshan says:

Really it was an awesome article...very interesting to read..You have provided an nice article....Thanks for sharing..

Web Designing Training Course in Chennai | Certification | Online Training Course | Web Designing Training Course in Bangalore | Certification | Online Training Course | Web Designing Training Course in Hyderabad | Certification | Online Training Course | Web Designing Training Course in Coimbatore | Certification | Online Training Course | Web Designing Training Course in Online | Certification | Online Training Course

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

22. Pankaj Singh 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

23. Pradeep Appslure says:

Appslure is an award-winning mobile app development company building feature-packed and interactive mobile applications for startups, medium and large enterprises.

24. Buy SEO Service says:
25. 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
FOR MORE INFO: