Real MATHEMATICS – Graphs #6

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:

20190423_000256.jpg

In this case Serkan I can have two children:

20190423_000310.jpg

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:

20190423_000334.jpg

Let’s add another land to this map:

20190423_000402.jpg

Adding a land on a map is the same thing as adding a dot on a graph:

20190423_000507.jpg

Map #2

Let’s assume there are three lands on a map:

20190423_000523.jpg

We can convert this map into graph as follows:

20190423_000537.jpg

As seen above, three children are needed in order to fulfill Serkan I’s rules:

20190423_000553.jpg

Map #3

Let the third map be the following:

20190423_000627.jpg

According to Serkan I’s rules, we will need four children for such map:

20190423_000642.jpg

Map #3 can be shown as a graph like the following:

20190423_000728.jpg

Map #4

For the final map, let’s assume Serkan I left a map that looks like USA’s map:

480271690e1e0485f71988e273730559

Surprisingly four children are enough in order to allocate the lands on the map of USA:

amarikaaa

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…

20190423_003916.jpg

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

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s