After a joyful stay in Rotterdam, and having visited the Markthal and the cube-houses, Maya decided to continue her trip to Brussel. Thankfully there is a direct train and the ticket is not very expensive, even if you book last minute. She was still thinking of what she read about the cube-houses. In Rotterdam they are part of a neighborhood called the "Blaakse Bos" (Blaak is a neighborhood in Rotterdam, and "bos" means forest in Dutch), a name which encapsulated the vision of architect Piet Blom that each house represents a tree, and the whole complex a forest. He envisioned it as a village and a safe space in the city for residents, shop owners, schools, playgrounds, and businesses.
Maya was looking out of the window as the train departed Rotterdam central station, she left her imagination travel while she was just looking at the blue sky and the green scenery. Suddenly she thought of her puzzles. She recalled a tricky puzzle from her childhood called three utilities problem. Her grandmother used to give her such puzzles for fun. She was a mathematician and every now and then she would share some new discoveries she made in her research. In this puzzle you have three vacation houses, and each house needs to be provided with water, electricity and gas. For each of these facilities, you have a provider which can supply you with it, but you need to connect your house to the facility source with a tube. And as tubes are quite massive, they cannot be either burrowed or lifted above the other ones. So, to solve it you need to connect each house to each facility with a line, and these lines should not intersect.
In terms of Maya’s diagrams, you have two sets of three points, and each point should be connected to all the points from the different set. But there shouldn't be any connections between points in the same set. Even then she knew that this puzzle is impossible, but she was never completely sure about it. Maybe now she can dispel her doubts.
Three utilities problem The graph related to this problem is called the complete bipartite graph with 3 and 3 vertices. The term bipartite means that you can separate the points of your graph into two sets in such a way that every connection is connecting points from different sets. In the case of the ‘three utilities problem’, the first set contains points which denote houses, and the second contains points which denote utilities. The term complete in this case means that all pairs of points from different sets are connected with a connection.
Now Maya has 6 points, and she needs to add 9 connections which shouldn't intersect each other. She started looking in her notes from the trip to Rotterdam, she knew she had found a nice result she could maybe use to solve the problem.
"Arghh, where did I write that down, I remember I had found something about the maximum number of connections you can add if there are no intesections. Yes! Here it is, how was it again?"
Maya started reading her previous notes and trying to remember what she had done.
"Right, the amount of connections can't exceed 3 times the amount of points minus 2. Let's see what we get for this graph. The maximal amount of connections possible is , which is larger than the 9 connections I want to add in this case. Hm, weird. This doesn't seem to help. According to this result it could be possible."
Maya was stuck. It seems that the approach she just invented does not work for this case. So, she comes back to drawing, maybe there is something that she missed (in the following pictures, all the utilities are marked in blue and all the houses are marked in red).
Indeed, after some attempts Maya realizes that she cannot draw a face with exactly 3 connections around it. And there is a reason behind it. If you follow the boundary of a face, the points which represent houses and facilities should alternate, as the connections link only houses with facilities. Having in mind this observation, Maya notices that for this particular diagram, each face needs not 3, but at least 4 connections around it! So, the amount of faces cannot exceed a half of the amount of connections (try to prove this yourself by following the ideas of our previous article).
"This is much beter! In my previous puzzle I had that the amount of faces cannot be larger than 2/3 of the number of connections. Using the additional property that this graph should be bipartite makes this estimate better! Let's see what I get now in Euler's formula."
Using Euler's formula means that the maximal amount of connections in this case is at most 2 times the amount of points minus 2. For 6 points you have which is smaller than the required 9! It provides Maya with the complete argument why the "three utilities problem" puzzle is unsolvable.
However, this second puzzle raised a question: is the recently discovered formula enough to test if a particular diagram can be represented without intersecting connections or not? Thinking about this question for a while, Maya faces the main problem. Even if she manages to construct a diagram for which Euler’s formula will not lead to a contradiction, she still needs some different arguments to be sure that the representation of this diagram is impossible. The solution she finds was quite elegant.
The diagram cannot for sure be represented if at least some part of this diagram cannot. Indeed, knowing that it is impossible to draw five pairwise connected points, you for sure cannot draw six. With this insight in mind, Maya easily manages to find an example of a diagram which is impossible to represent, but this fact cannot be derived from Euler's formula. You can simply take 6 points, connect five of them to each other, and connect the last one to two of the others.
This diagram contains 6 points, meaning that the maximal possible amount of connections is , which is exactly the amount of connections. But as Maya knows, such a diagram is impossible to draw. It contains a part, 5 pairwise connected points, which you cannot draw. This example shows Maya that Euler's formula is not that reliable, but she finds a different rule.
A diagram is impossible to draw if it contains either a diagram of 5 connected points (the graph of the first puzzle), or a diagram with two sets of three points, each connected to all points from the other set (the graph of the "second puzzle"three utilities problem").
“Is that all?”
A question arises in Maya's head at the same time when the Antwerpen Central Station was announced.
“Are these really the only two reasons why a diagram cannot be represented without intersections?”
She gets off the train to walk a little bit around, deeply in her thoughts. During her ten minutes stop in Antwerpen she tries to imagine different diagrams, maybe she can find such a graph that is impossible to draw, but does not involve any of two forbidden patterns. And it seems that she finds one. After getting back on the train, Maya draws the following diagram.
It definitely does not have any of the two forbidden diagrams Maya has in mind, but it looks so much similar to the first one, so there is no chance it can be drawn without intersections. Or can it? Looking closely at this diagram, Maya notices that it actually contains the “houses and utilities” diagram, but some connections are interrupted by some different point.
This example gives Maya another insight. If one of your points is connected only to two of the others, you can erase this point, saving the drawn connections - then the two points which were connected to this point appear to be connected to each other, and the erased point disappears.
As you can see, such an action does not change the diagram in a sense of its picture, but does in fact change the diagram itself. It means that if the initial diagram is possible to draw without intersections, the new one, which appears after erasing some points, is possible to draw as well. And what is even more useful, Maya can combine her two ideas: first delete some connections from your initial diagram and only after that erase some points.
In this case it means that if the diagram on the left is possible to draw without intersections, then it is possible to draw the diagram on the right without intersections as well. But Maya knows that the diagram she obtains is the three utilities diagram, which cannot be drawn without intersections. Hence, the diagram on the left cannot be pictured in this was as well!
This idea gives Maya a new procedure of building a non-drawable diagrams. Instead of simply adding points and connections to her forbidden diagrams, Maya can come up with a graph from which, after erasing some points she can get either the 5 pairwise connected points, or the three utilities diagram. But is there a simple way to create such graphs?
Apparently, there is. You simply need to invert the erasing procedure. You may notice that after erasing a point you obtain a simple connection. Meaning, if you want to go backwards you can choose a connection and interrupt it with a point. And you can in fact do such interruption not only once, but many times.
Here you need to be a bit careful as you should do it only for one connection. Remember that you are allowed to erase only those points which have just two connections. If you try to put a point exactly on the intersection of two different connections, such a point would have 4 connected points, meaning that you are not allowed to erase it.
Combining these three actions: adding new points, adding new connections and interrupting the connections, Maya manages to build enormous amounts of diagrams which are for sure impossible to draw based only on the two forbidden diagrams.
This thought sounds to Maya a bit heavier than the previous one, but after spending some time and energy she convinced herself about it - at the end of the day, there are only two principally different patterns which prevent you from drawing a diagram, the rest are just their variations. Can there be anything else?
Searching in the internet Maya indeed finds the following fact:
Every non-planar graph should contain either a subdivision of the complete graph with 5 vertices, or a subdivision of the complete bipartite graph with 3 and 3 vertices.
This fact is called Kuratowski’s theorem, and it is extremely remarkable result in the mathematical field of graph theory. In terms of Maya's diagrams it means exactly what she just formulated from her observations: the diagram is impossible to draw without intersections only if it either contains an ’interrupted’ diagram of five pairwise connected points, or an ’interrupted’ diagram from the ‘three utilities problem’!
There are only two principally different patterns which prevent you from drawing a diagram, the complete graph on 5 points, and the complete 3,3 bipartite graph, the rest are just their variations.
The train arrives at Brussels central station. Finally, Maya gets to her destination. She is extremely proud of herself, she just managed to complete not only the journey from Cologne to Rotterdam and then to Brussels, but also the whole path from a simple question about five bordering countries to the complete and definitive answer about the possibility of drawing diagrams without intersections. With this feeling she heads toward the Atomium to enjoy its architecture!
Say you are living in Eindhoven and would like to spend a day in Amsterdam: what better way to get there than taking the train? Before your train departs, a whole logistic operation has taken place in the headquarters of the railway company to make this trip possible.
How can one hope to understand the precise structure of a virus if it is able to become unrecognizable within weeks? The mathematics behind this questions didn't let go of my mind for extensive periods of time during my PhD studies in Belgium.
Alfred Aho and Jeffrey Ullman received the 2020 A.M Turing Award for their contributions to computer science. Let’s explore how their contributions have shaped the principles, techniques and tools for writing compilers.
three utilities problem
. Her grandmother used to give her such puzzles for fun. She was a mathematician and every now and then she would share some new discoveries she made in her research. In this puzzle you have three vacation houses, and each house needs to be provided with water, electricity and gas. For each of these facilities, you have a provider which can supply you with it, but you need to connect your house to the facility source with a tube. And as tubes are quite massive, they cannot be either burrowed or lifted above the other ones. So, to solve it you need to connect each house to each facility with a line, and these lines should not intersect. 
, which is larger than the 9 connections I want to add in this case. Hm, weird. This doesn't seem to help. According to this result it could be possible."
which is smaller than the required 9! It provides Maya with the complete argument why the "three utilities problem" puzzle is unsolvable.
