Dose of STEM: A Trip to Kaliningrad a.k.a. Königsberg

It's been a while since we have posted anything. Recently, we came across an interesting problem: The Königsberg bridges problem. According to this problem, you should cross each of the seven bridges only once.

You must NOT:

1. reach an island or mainland bank other than via one of the bridges

2. access any bridge without crossing to its other end

The seven bridges are shown above. So, can you solve this? You have time to think about it. Just pause for some time and think about it. If you want a simplified diagram, here you go:

Note: A, B, C and D represent land and a, b, c, d, e, f, g represent the bridges

FUN FACT

Two of the seven bridges did not survive the bombing of Königsberg during World War II. Two others were demolished and converted into a modern highway. Only 3 remain, out of which two were from Euler's time and one was rebuilt in 1935.

SOLUTION

IT IS IMPOSSIBLE TO PASS THROUGH ALL THE SEVEN BRIDGES AT ONCE!

You heard that right!

If we convert the map (from the previous post) into a graph like the one above, where the orange points represent land (we can label it 'a', 'b', 'c' and 'd', and the black lines represent the bridges, we can count the number of lines meeting each orange point (the degree) and we get :

1) a = 3 2) b = 3 3) c = 5 4) d =3 According to Euler (who proved that it was impossible) if there are none or 2 points (in the diagram: orange points) with odd degrees, then it would be possible, but in this case, there are 4 points with odd degrees. Therefore it isn't possible. You can try this method out with 'x' bridges too!

For example:

5 bridges