6502's cornerThe seven bridges of Konigsberg [Solution]
2002-12-28
Index

Welcome!
Who am I
Demo
Documents
Small ones
Problems
Chess
Images
Music
My blog
Write me

Versione italiana 


The seven bridges of Konigsberg [Solution]

It's easy to see that every place in which there are an odd number of streets must be either the start or the stop of a path while a place with an even number of street can be also a passage point (when you "pass" from the place you use two streets, one for arrival and one for departure).

In the problem one can see 4 places: the two river sides and the two islands and all of them have an odd number of streets and so all of them must be either the begin or the end of a path. This is clearly impossible.

Note that if you remove any of the bridges then the solution is easy as we will remain with two places with an odd number of streets and two places with an even number of streets.

For example eliminating the bridge between the two islands it's easy to find paths, and all of them will start from one side and end to the other. Or if we remove one of the bridges of the big island to the land then we will find paths either starting or ending on the small island (see next figure).

Example of removal of a bridge and one of the solutions it generates.