Bequeath Problem
King Serkan I decides to allocate his lands to his children. Obviously he had set up some ground rules for the allocation:
- Each child will get at least one land.
- Same child can’t have adjacent lands.
Problem: At least how many children should Serkan I has so that allocation can be done without a problem?
Map #1
Let’s start from a simple map:
In this case Serkan I can have two children:
As you can remember from the previous article a map and a graph is irreversible. If we represent lands with dots, and let two dots be connected with a line if they are adjacent, we can show maps as graphs:
Let’s add another land to this map:
Adding a land on a map is the same thing as adding a dot on a graph:
Map #2
Let’s assume there are three lands on a map:
We can convert this map into graph as follows:
As seen above, three children are needed in order to fulfill Serkan I’s rules:
Map #3
Let the third map be the following:
According to Serkan I’s rules, we will need four children for such map:
Map #3 can be shown as a graph like the following:
Map #4
For the final map, let’s assume Serkan I left a map that looks like USA’s map:
Surprisingly four children are enough in order to allocate the lands on the map of USA:
What is going on?
Careful readers already noticed that adding a dot that connects the other dots in the second map’s graph gives the graph of the third map. Same thing is true for the first and second maps:
Hence, adding a new dot to the graph means adding a new child.
Q: Is it possible to create a map that requires at least five children?
In other words: Is it possible to add a fifth dot to the graph so that it has connection to all existing four dots? (Ps: There can be no crossing in a graph as our maps are planar.)
Then, all we have to do is to add that fifth dot… Nevertheless I can’t seem to do it. When I add the fifth dot outside of the following graph:
It is impossible to connect 1 and 5 without crossing another line. No matter what I try, I can’t do it:
Four Color Theorem
About 160 years ago Francis Guthrie was thinking about coloring maps:
“Can the areas on any map be colored with at most four colors such that no pair of neighboring areas get the same color?”
Incredibly the answer is yes.
This simple problem was introduced for the first time by Francis Guthrie in 1852. Not until 1976 there was no proof for Guthrie’s conjecture. Only then with the help of computers the conjecture was proved. This proof is crucial for mathematics world as it is known as the mathematical theorem that was proven with the help of computers.
One wonders…
Add a fourth dot to the graph you see above and connect that dot to the existing dots. (You are free to place the fourth dot wherever you want on the graph.)
Now check your graph: One of those four dots is trapped inside the lines, isn’t it?
Can you fix that?
Explain how you can/can’t do it.
M. Serkan Kalaycıoğlu
kmatematikatolyesi.com 