# Seven Bridges of Königsberg

• March 14th, 2008, 09:44 PM
numb3rs
Seven Bridges of Königsberg
:bh :bh :bh :bh :bh :bh :bh :bh :bh :bh :bh :bh :bh :bh :bh :bh :bh :bh :bh :bh :bh :bh
there has to be a way to cross all seven of these briges just once and only once its driveing me mad
• March 14th, 2008, 11:19 PM
AlexP
Sorry to burst your bubble, but Leonhard Euler proved that it can't be done in 1736. And I wouldn't question Euler if I were you, he was a very smart guy. :) There's a Wikipedia article on the subject if you'd like to take a look at it.
• March 15th, 2008, 01:56 AM
serpicojr
Notice that all four landmasses have an odd number of bridges leading to them. Now suppose you made a full circuit of all the bridges without repeating. Then you started in some landmass, and you ended in some landmass. So the two landmasses you neither started nor ended on must have been visited by you an even number of times--for each time you visited one of them, you also left it. So they must be attached to an even number of bridges, which is not the case.
• March 15th, 2008, 09:55 AM
numb3rs
i found a way to do it! :shock:
you go through some of the briges half way and walk back thats 1 time and you can do it! :lol: :lol: :lol: :lol:
• March 15th, 2008, 01:30 PM
Demen Tolden
Quote:

i found a way to do it!
you go through some of the briges half way and walk back thats 1 time and you can do it!
Why not swim across that blue stuff a couple times just for good measure?
• March 15th, 2008, 01:37 PM
numb3rs
:o but thats cheating
• March 17th, 2008, 12:09 PM
sunshinewarrior
It's actually quite easy - the surface of the earth is, literally, curved space. Simply walk around the earth from one of the bridges (chosen carefully) to come back to the opposite side of Konigsberg, and Bob's your uncle. :twisted:
• March 17th, 2008, 09:11 PM
bit4bit
I was reading about this problem recently, looking into topology. Euler proved that to take a route using each path only once, called a Euler path, you would have to have exactly 2 or exactly 0 odd nodes, otherwise it cant be done. A node would be a landmass, and if it has an even number of bridges connecting it, it is even, but if it has an odd number it is odd. This is all about considering how the landmasses (nodes) are connected by the bridges, and not thinking about any physical geometry of the situiation.
• March 18th, 2008, 08:38 AM
sunshinewarrior
Quote:

Originally Posted by bit4bit
I was reading about this problem recently, looking into topology. Euler proved that to take a route using each path only once, called a Euler path, you would have to have exactly 2 or exactly 0 odd nodes, otherwise it cant be done. A node would be a landmass, and if it has an even number of bridges connecting it, it is even, but if it has an odd number it is odd. This is all about considering how the landmasses (nodes) are connected by the bridges, and not thinking about any physical geometry of the situiation.

Absolutely true - unless you consider that the nodes have different properties (and Euler's proofs different considerations) depending on the shape of the surface. For instance, I'm guessing that Euler's proof is concerned solely with plane surfaces (or surfaces with a particular topological characteristic - order 0?) but does not hold for spheres, mobius strips, klein bottles or toroids.
• March 18th, 2008, 12:51 PM
serpicojr
I don't think Euler's proof depends on topology (and I'm pretty sure the proof I posted is essentially Euler's proof). Actually, let me restate this: it doesn't depend upon the topology of the surface upon which the problem exists. The key assumption is that there is no way to get between two landmasses without crossing a bridge (or without getting wet), and so the problem can be abstracted to a question about graphs (vertices connected by edges). Sure, the graph has topological properties, and I'm sure you can use these to prove the result, but it's not necessary, as my proof shows. And it doesn't matter what sort of surface you put this graph on, you still can't do it.

The only way for there to be a solution to the problem is, as you suggest, consider the idea that some of the landmasses may be connected if you walk far enough. And this isn't in the spirit of the original problem--people wanted to be able to walk all of the bridges in a single day. :)
• March 18th, 2008, 03:21 PM
bit4bit
I think the proof can be stated simply, as you said (And I repeated), but it seems to be given as an example of topology in alot of pages i have read. As far as explaing why that is, I don't know enough topology, to say.
• March 18th, 2008, 03:37 PM
serpicojr
This is a topological question in the sense that it doesn't matter where the nodes are in relation to each other, which order the bridges are in, etc. We can pull and push and stretch and bend things around without changing the nature of the problem. Like you said, the actual geometry of the picture doesn't matter. Indeed, everything rests upon the fact that, when you're on a bridge, the world locally looks like a line, whereas when you're at a node, the world looks like an arbitrary set of rays--and these are topological facts. These facts basically characterize what the possible paths through the space are (up to some sense of equivalence).

I suppose what I was saying, then, is that these basic topological properties of graphs are basically assumed/formalized when you're doing graph theory.
• March 19th, 2008, 06:21 AM
sunshinewarrior
Quote:

Originally Posted by serpicojr

The only way for there to be a solution to the problem is, as you suggest, consider the idea that some of the landmasses may be connected if you walk far enough. And this isn't in the spirit of the original problem--people wanted to be able to walk all of the bridges in a single day. :)

Fair enough. And your proof was elegant. Ta. :-D