Looking on the world map you can easily spot four countries that border each other. But can you find five?
Maya likes travelling. This year she spends her vacation in Germany. She has already been to Berlin and Frankfurt, and now she is in Cologne. Walking around after visiting the monumental Cologne Cathedral and looking for some close attractions, she sees pictures of Atomium in Brussels and Markthal in Rotterdam. They immediately attract her attention. She thinks why not to go there right now, both these cities are close to each other, and it should not be a problem to go there by train. So, she comes up with a plan: first go from Cologne to Brussels to visit Atomium, and then from Brussels to Rotterdam for the Markthal.
However, when she came to the train station, she realized that all trains to Brussels are cancelled due to strikes. Trying to solve this issue, Maya comes up with an idea: she can do the same trip but reversed. Going from Cologne first to Rotterdam, and then to Brussels she fulfils the same goal. And this reverse way is possible because all three countries border each other. Reflecting on this idea, she became more ambitious. Maybe, next time she can visit four different countries, or five, or even more? But this situation taught her a lesson. Next time she would like to be as much independent of the unreliable between-country traffic as possible.
If she wants to go from one country to another, her way should not go through any third country. And this rule should be applied not only to her original route, because in this case she can get stuck, but to all possible travels between countries. In fact, it means that any two of these countries should share a common border. In this case, even if her initial travel plan will be ruined by any reason, she still manages to change the order of the countries she wants to visit, and continue her journey. But first she should buy a ticket to Rotterdam.
Taking her seat in the train, Maya starts scrolling maps in curiosity of how many such countries she could find. Finding four countries where any two of them share a boarder does not take much time, they are located right next to her: Germany, France, Belgium and Luxembourg. However, finding five is much more challenging. Ensured that there are no such countries in Europe, Maya proceeds to scan the other areas. Though, even passing through all the other continents, she manages to find one more example of four countries, namely Brazil, Bolivia, Paraguay and Argentina (fun puzzle: open a map and try this yourself, you will definitely improve your geography skills!). But she can't find five countries! No matter how much she looks. At this point she starts wondering if such a configuration is actually possible. So, she begins drawing.
Some of Maya's drawings trying to make five countries such that any two of them share a boarder.
Time flies and the train passed by the small German town Neuss. The more Maya tried, the more complicated her pictures become, but none of them satisfies her goal. At some point she decided to simplify her sketches.
“Maybe I don’t need to draw the whole country” - Maya thinks
“Maybe it is enough just to mark the city I want to visit by a point, and then simply picture all possible routes between them by lines which connect a pair of points. But I need a picture for which each route does not intersect the third country. So maybe it is enough to draw these connections in such a way that they do not intersect each other?”
For Germany, Belgium, Luxembourg and France you can see that each pair of them shares a boarder. Hence you can connect all capitals so that the connections don't intersect.
Going through her pictures Maya noticed that indeed for any particular country you can put the points inside the corresponding countries and draw each connection line exactly through its border so that they do not intersect each other.
By making a graph of the cities, the countries and the connections between them the drawings become simpler.
The graphs which can be pictured in such a way that its edges do not intersect each other are called planar graphs. And, what is much more remarkable, it works as well the other way around: if you can draw a diagram without intersections, you can make a map out of it.
"But I have to be careful when drawing the graph!"
Usually, the particular image of a graph does not play a role. The crucial property of a graph is the way how different points are connected to the other ones by a connection. However, to verify if a graph is planar or not, we should look at its pictures. And it is not enough to look only at one image because the same graph can be drawn with and without intersections. It suffices to find one such picture without intersections!
Maya starts wondering
"If I want to find five cities, in five neighboring countries, such that every pair of countries shares a border, then I need to draw a graph with five points, where all points are connected to each other, and make sure that no connections intersect!"
This realization excited Maya who started working on this puzzle. Using this new insight, Maya's pictures became more readable, but she still kept failing to draw such a graph. Meanwhile, the train reaches her first stop - Monchengladbach train station.
”Is it actually possible?” - Maya wonders -
”Maybe there is a way to show that, but how…”
Looking at her new diagrams, Maya realized that the new pictures look again similar to maps. You can again see different countries with theirs borders, which are now bounded by the connections Maya is drawing.
"Maybe I can just start adding connections one by one and see how I can add them all. I can now connect the purple and the black point without intersecting any other connection. Then I only need to connect the purple and the green points. Aaaah, frustrating! The purple point lies trapped in the red-black-blue face and I can't reach the green point without intersecting one of these three connections. Maybe it is just not possible to do this... Let's start from the beginning and see how it goes."
While adding connections to the graph Maya realized there are three numbers that seem to play a role in how the graph looks like, namely the number of points , the number of connections , and the number of faces . A face is a closed area which is surrounded by connections. Faces seem somehow important since they may redeem points inaccessible to each other, as above with the purple-green points. Maya starts from a single point, adding points and the connections one by one, and writing down how many points, connections, and faces appear in the graph.
"Ok, I am going to build the graph from 1 point and keep adding points and connections to see how this works".
While drawing another diagram, Maya noticed that each time she draws a new connection, she either adds a new point, or a new face:
So, there must be some relation which tie them together. Certainly, going through all her diagrams, Maya finds one remarkable property:
"Wow, the sum of the number of points and the number of different faces which appear, including a giant one around the image, is always two more than total amount of connections!"
If we write this down compactly in a formula it is
Puzzle time
At this point we welcome the reader to verify this fact for different planar graphs. To construct a graph you take look at some area of the map, for example, Europe or South America. For each country you can mark its capital. These would be the points of your graph. Then, for each two neighbouring countries you should draw a line which connects the respective capitals and passes only through these two countries. Please keep in mind that your connections should not intersect each other. This way you construct a planar graph. Now you can verify the formula by simply calculating the amount of points, connections, and faces. Do not forget that the area around your picture is considered as a face as well.
The formula discovered by Maya is called Euler’s formula. We kindly invite our reader to visit this article for more details. You may notice however that Euler’s formula presented in the aforementioned article is slightly different to what we discuss here. This difference appears from our convention of considering the area around diagram as a face. From a visual perspective such a convention is not natural. However, such an agreement is natural from a mathematical point of view and will be useful later.
Maya really likes her recent observation. But can it actually help her with his problem? Remember that she still tries to connect 5 points pairwise without any intersections of the connections. Maybe her recent insight can tell her that 10 connections are too much for 5 points. Scanning her pictures, Maya noticed that each face needs at least three connections surrounding it (why is this?, look at the figure above and try to understand why this is true.). Moreover each connection can take part in constructing only two faces. It means that the amount of faces cannot be larger than 2/3 of the amount of connections. Using this finding, in combination with Euler's formula from above, Maya obtains that the amount of connections can't exceed 3 times the amount of points minus 2. In particular, for 5 points we can't draw more than connections, meaning that it is indeed impossible to draw 5 points connected to each other without an intersection of these connections!
"Whaaaat!" - Maya uttered in surprise of what she has found.
By the dramatically deteriorated weather Maya understood that the train entered The Netherlands. She was slightly dissatisfied with her recent discovery, as she must limit to only four countries! On the other hand, she gained some knowledge, so she can maybe use it in a different occassion. She opened again the map and she was looking at all these countries being destined to satisfy this mathematical restriction for ever. While she was thinking about her time in Rotterdam and what she will do there, she remembered another puzzle from her childhood which sounded similar.
The train conductor announced its stop at ’s-Hertogenbosch, the origin of famous Dutch painter Hieronymus Bosch. Maya recalls that she saw the pictures of Bosch in the Städel museum in Frankfurt a couple of days ago. But despite reflecting on the nice memories about the art exhibition, she is still puzzled.
"I don't want to think about it anymore, I am almost there. I will think about that on my way to Brussels!"
In this article Maya continues her journey from Rotterdam to Brussels. She starts thinking about a puzzle from her childhood, the three utilities problem. At the end of the jouney she has reached a very important theorem from graph theory!
Recently there has been a breakthrough in the field of algorithms for geometric network problems, concerning the complexity of the Euclidean Travelling Salesman Problem.
A mathematician once told me that problems that are very simple to state can be very deceiving, and sometimes turn out to be extremely difficult to solve. One such problem was the Four Color Problem.
Rapid urbanization without consideration for the environment is currently threatening urban dwellers. Its effects are exacerbating climate change and the urgency to adapt to our circumstances is growing. Network science may just have the key to solving our multifaceted problems.
, the number of connections 
, and the number of faces 
. A face is a closed area which is surrounded by connections. Faces seem somehow important since they may redeem points inaccessible to each other, as above with the purple-green points. Maya starts from a single point, adding points and the connections one by one, and writing down how many points, connections, and faces appear in the graph. 
connections, meaning that it is indeed impossible to draw 5 points connected to each other without an intersection of these connections!
