This week, we had our very first math session at Future Science Leaders. With the help of four passionate mathematics fellows, we grappled with two very intriguing problems.

**Our First Challenge:**

*Colour this map with as few colours as possible, without having countries that share a border be the same colour.*

We all settled down in our table groups to ponder this conundrum. Pencil crayons and crayons in hand, we started off by spacing out separate colours. We soon came to the consensus that the map had to be completed with at least four – attempts with three colours all led to dead ends. Upon further reflection, we realized that Austria’s many borders were the cause of this problem. Czech Republic, Italy, and Hungary could be one colour, while Germany, Slovenia, and Slovakia could be another. However, Switzerland and Austria, both surrounded by two colours and bordering each other, each had to be a different colour (resulting in four colours in total). We then wondered – would this “four-colour rule” change if put to the test on more complicated configurations?

The answer was no. After colouring a couple of other diagrams and creating some of our own, we were left puzzled by the unchanging rule. It turns out that this problem had mathematicians equally puzzled for over a hundred and twenty years. This seemingly simple problem was conjectured in 1852, but wasn’t proven until 1977. Appropriately named the Four-Colour Theorem, it states that any map in a 2-D plane can be coloured using four colours such that regions sharing a common boundary are not the same colour.

**Our Second Challenge:**

*Try to devise a walk where you travel over each of the seven bridges once and only once. It doesn’t matter where you start and where you end. You do not need to finish in the same place you started.*

It didn’t take very long for us to realize that this was in fact, an impossible task. No matter where we started or what path we took, we were always one bridge short of completing the walk. It seemed that we’d always get stuck on one land mass, unable to return to cross over the last bridge. Therefore, we analyzed the placement of the bridges to see if we could detect any patterns – which was when we noticed something very interesting. Every “pair” of bridges crossed involved entering and then leaving a land mass. But after crossing six bridges, there was no way to enter the land mass containing the seventh (without using a bridge that had already been crossed). If we added another bridge to enter that land mass, we would be able to leave via the seventh bridge.

This problem, called The Königsberg Bridge Problem, represents the historically accurate configuration of bridges in Königsberg, Prussia, during the 18th century. It is rumoured that the people of the city noticed this situation and decided to tackle it themselves, the goal being to create a way to walk around the city while crossing each of the seven bridges only once. No one managed to devise a successful path, yet no one could prove it was impossible – until famous mathematician Leonard Euler published his proof in 1741.

How did Euler prove such a successful path was impossible?

Good description and analysis of these two fascinating puzzles. If only they taught this type of math in high school! If you’re looking for more problems that use graph theory http://www.mhhe.com/math/ltbmath/bennett_nelson/conceptual/netgraphs/graphs.htm has a lot of cool examples to get you started.