It appears that the geometry has changed since Euler's time, or the diagram is incorrect. It appears that is the larger ( Lomse/ Oktyabrsky ) island that has the 4 bridges from the mainland rather than the smaller one (Kneiphof). Ironically; the topology appears preserved, so it doesn't actually matter, which underscores the point of Euler's achievement.
The cathedral on the island is beautiful and contains Immanuel Kant's tomb. It was bombed pretty severely in WW2, before that there were a bunch of buildings on the island:
> After the war, the cathedral remained a burnt-out shell and Kneiphof was made into a park with no other buildings. Before the war, Kneiphof had many buildings. One of the buildings was the first Albertina University building, where Immanuel Kant taught, which was situated next to the east side of the cathedral.
The cathedral got lucky as its skeleton, the walls, whats left after WWII fighting and bombing, were allowed to survive through the Soviet times. During 198x were was a flea/farmers market inside and behind it.
The Castle didn't get that luck - https://en.wikipedia.org/wiki/K%C3%B6nigsberg_Castle. It got bulldozed, and the boondoggle of Soviet glory - the "skyscrapper" (21 story in Kaliningrad region in 198x was almost mindblowing, add to that that it is on the top of the Castle hill, so it looms large over the city) - is still unfinished and
(https://en.wikipedia.org/wiki/K%C3%B6nigsberg_Castle#Current... ) "Continuation of development was stopped in the 1980s as the massive building gradually sank into the structurally unsound soil stemming from the collapse of tunnels in the old castle's subterranean levels. Many people call this the "Revenge of the Prussians" or "The Monster"."
These underground tunnels (Kenigsberg and Prussia as whole has a lot of them) were back then and i'd guess even more today the scene of active exploration, in particular for hidden Nazi stolen treasures (e.g. "Amber room"), weapons/munitions/etc. and just out of sheer curiosity ( after all it is centuries of history starting from Teutonic Order). So you sometimes would find yourself facing a problem of "N tunnels in three dimensions" with some of them flooded/leading into unknown/etc.
My grandfather gave me a puzzle when I was 8 or 9 years old where the goal was to trace a path through each of the "walls" in the diagram below without the path crossing itself:
I played with it off and on for years and suspected that it was impossible. I realized that it is in fact impossible when I took discrete mathematics in college and we covered the Seven Bridges.
I've passed this on to my kids but only let them play with it for hours until revealing that it's not possible and getting into the theory of it.
I don't think my grandfather knows this is impossible, and I haven't yet remembered to tell him.
Wow thank you! So I just learned the proper name of this "puzzle", which my father also showed me a long time ago (and for which I used to fill pages and pages of trials even though I knew that it had no solution), and which I tried to render as an "applet toy", a couple of years ago on my blog (see my other comment below).
It's interesting that there exists a solution (shown in the Wikipedia article), if you build the rooms on a torus. That would be the equivalent of digging a tunnel between two rooms.
The discussion of the "Variations" section is interesting. Apparently the person who inserted it (and had it removed several times) won't give a citation but also won't come out and say that they made the examples up themselves. Nobody ever calls out the useless introduction of German terms in the examples, and more importantly that (a) "Ritcher" is not a German word, and (b) even if it were a misspelling of some German word, it would not mean "church".
The way the section was phrased (it's removed now) it appeared to refer to some external source. The sentence "It is understood that the problems to follow should be taken in order, and begin with a statement of the original problem:" would make no sense otherwise. But if there is such an external source, it should be cited. This is the main problem. It's not about Wikipedia being a boring stickler for rules.
I was fascinated by a "puzzle version" of this problem as a child, and a couple of years ago I wrote some little Processing applets to explore the idea of "gamifying" it:
It's interesting that it's apparently the problem that laid the foundation for modern graph theory, but the problem can't actually be specified as a graph under its usual modern definition... can it? At least not without some shenanigans that would make it more complicated than "node = landmass, edge = bridge", as it's depicted in the standard diagram shown on Wikipedia.
A graph is usually defined as a set of nodes and a set of edges, where an edge is a pair of nodes (an ordered pair if it's a directed graph). The "set" of edges (bridges) of the "graph" in this case contains duplicates -- there are two edges with the same pair of vertices, two bridges crossing between the same pairs of landmasses. And the two pairs of duplicated bridges are essential to the problem setup. So AFAICT it can't be fully specified as a set of edges; it would have to be a multiset.
(I've seen this problem before but only just noticed this when reading Wikipedia now -- let me know if I'm missing something.)
A "graph" can sometimes implicitly mean a "Simple Graph" which has neither loops nor multiple edges between pairs of vertices, but in some contexts can mean "Multi-Graph", which does allow multiple edges and loops. So the usual conversion of the bridges problem to a network gives us a "Multi-Graph" ... the distinction is often left to be inferred, because it's usually obvious (to the skilled practitioner).
One way around this to end up with a simple graph is to include a vertex in the middle of each bridge. Then each edge has one end in the landmass and the other end in the middle of the bridge. That equivalence/conversion shows that the distinction, in this case, is effectively unimportant.
Some friends and I took a holiday to NYC a few years ago, calling it "Project Königsberg" as we attempted to travel all public transport entry and exits to Manhattan without duplication, over the course of 3 days. I was glad not to be involved in its planning, but very happy to participate!
William Hamilton has an interesting variation of Euler's Seven Bridges puzzle [0] which asks whether there is a path visiting every vertex of a polyhedron exactly once. Strangely, while the complexity of detecting Eulerian paths is linear in the number of edges [1], the complexity of detecting Hamiltonian paths is NP-complete [2]!
Hamilton (who was also fond of crossing bridges [3]) developed some interesting algebraic structures to study the polyhedron problem [4]. I recently became interested in Eulerian and Hamiltonian paths after taking a class in Graph Representation Learning [5]. In it, I learned there are many interesting connections between algebra and graph theory [6] and started writing a library called Kaliningraph to study some of those connections [7].
Well, the HN/engineer solution would be to propose the building of a new bridge.
Then we could have a big discussion about funding strategies, metallurgical esoterica, cutting edge topological algorithms for determining best place to add a vertex in the graph, and/or history of Roman land jurisdiction. And we’d all learn something.
https://www.google.com/maps/place/Knaypkhof,+Ulitsa+Kanta,+K...
It appears that the geometry has changed since Euler's time, or the diagram is incorrect. It appears that is the larger ( Lomse/ Oktyabrsky ) island that has the 4 bridges from the mainland rather than the smaller one (Kneiphof). Ironically; the topology appears preserved, so it doesn't actually matter, which underscores the point of Euler's achievement.