Real Mathematics – Graphs #7

Serkan’s System

Serkan the math teacher, hands out a specific number of problems to his students. Kids who can solve 1 or more of those problems would get a certain prize. At the beginning of each semester, Serkan and his students sit down and agree on what kind of prize is going to be distributed. For the current semester, oreo is chosen as the prize:

If Serkan the math teacher hands out 10 problems:

• 10 Oreos for the kids who solved 10, 9 or 8 of those problems,
• 5 Oreos for the kids who solved 7, 6 or 5 of those problems,
• 2 Oreos for the kids who solved 4, 3 or 2 of those problems,
• 1 oreo for the kids who solved 1 problem,
• Absolutely nothing for the students who solved… well… none of those problems.

If you take a careful look at the numbers, you can see that Serkan the math teacher selected those numbers with a kind of logic: 10, 5, 2 and 1.

These are the natural numbers that can divide the number of the problems (that is 10) without any remainder.

Prize Distribution Machine (P.D.M.)

One month later…

Serkan the math teacher had faced some problems 4 weeks into the semester. He realized that it took hours to distribute the prizes since he has 10 classes in total.

Serkan the math teacher had to use almost all his free time in school to distribute the Oreos. This led him to think about a machine that would help him with the distribution:

• P.D.M. will have 4 different compartments. (Because of 10, 5, 2 and 1.)
• The volumes of those compartments will be measured with Oreos. They will be 10, 5, 2 and 1 Oreo-sized.
• Oreos will enter the machine from the 10-Oreo-sized compartment. From there, Oreos will move to the other compartments using the connections that will be established.
• Golden Rule: To establish a connection between any two compartments, the size of those compartments must be factors of one another.

Connections of the compartments for 10 problems:

• For 10-Oreo-sized: 5, 2 and 1.
• For 5-Oreo-sized: 10 and 1.
• For 2-Oreo-sized: 10 and 1.
• For 1-Oreo-sized: 10, 5, and 2.

Then, the sketch of the P.D.M. would look like the following:

Is this another graph?!

If you are familiar with graph theory (or if you read the graph section of the blog) you can recognize that the sketch of Serkan the math teacher’s machine is a planar graph:

You should connect the numbers (dots) using lines (connections) according to the golden rule.

One wonders…

What if Serkan the math teacher asks 12 problems?

For 12 problems, the numbers of prizes are going to be: 12, 6, 4, 3, 2 and 1.

In such a situation, can Serkan build his machine? In other words; is it possible to connect the dots for 12-sized P.D.M.?

Hint: First, you should consider where the lines should be. Also, you can arrange the dots in any order you’d like.

M. Serkan Kalaycıoğlu

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:

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

“Can the areas on any map be colored with at most four colors such that no pair of neighboring areas get the same color?”

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

Real MATHEMATICS – Graphs #5

Cruel Traffic Light

I have to drive past the same crossroad almost every single day. Obviously I stop at the longest-lasting traffic light of the crossroad. Within time I started loving these moments because it gave me a chance to think my life over. Though, it doesn’t take too long for me to start thinking about mathematics.

One of those days I found myself questioning the traffic lights and their relationship with mathematics. (After all mathematics is everywhere; isn’t it?) Soon after I realized that there was my beloved graph theory behind traffic lights.

Light #1

Let’s assume a one-way street with two traffic lights: One for the vehicles (we’ll call it A), other for the pedestrians (we’ll call it B):

In such situation we have to avoid accidents. This means whenever A has green light, B must have red light and vice versa. We will not take account of the situation when both lights are red. Because even though there won’t be any accident, neither of the sides will be standing still (which is nonsense):

All these can be shown using graph theory: Lights will be represented by dots. Dots in a graph will be connected with lines if they are not in the same color:

Same thing can be shown with maps: If A and B are two neighboring countries, they should be colored in different colors to avoid confusion:

Light #2

This time we will assume a two-way street with three traffic lights: Two for the vehicles from opposite sides (we’ll call them A and B), and one for the pedestrians (we’ll call that C):

In such a situation when C is red, either or both of A and B should be green. When C is green, then both A and B should be red:

We’ll skip the situation where all three of them are red as no one would move in such situation.

We can show these using graph theory and map coloring as follows:

Since we set all the rules graphs make it much easier and clearer to understand the situations.

Light #3

Finally we have a two-way street (A and B), a right turn (C) and two pedestrian lights (D and E) as follows:

This time it is a much complex situation:

Although using graph theory makes it all easier for us to understand:

How Many Colors?

We will color the following graphs using the same rules we just established above: If two dots are connected with a line, then those dots must have different colors.

Chromatic Numbers: Whenever a graph is being colored, ambition is the use the least number of colors. This number is also known as the chromatic number of a graph.

Here we need 3 colors. Hence chromatic number of the graph is 3. Let’s add one more dot and line to the graph:

This time chromatic number of the graph becomes 2. We’ll add another dot and line:

Now chromatic number becomes 3 again. Let’s add a dot and a line for the last time:

Chromatic number is back to 2.

To be continued…

One Wonders…

What did just happen? What did you notice? Why is it happening?

How can you increase the chromatic number?

M. Serkan Kalaycıoğlu

Real MATHEMATICS – Graphs #4

I visited the world famous Hermitage museum in Saint Petersburg (Russia) back in 2014. Hermitage is so huge that it has 1057 rooms and one would have to walk around 22 km to see all the rooms. And numbers of artistic & historical items are not that shallow either: It is believe that it would take a little over 11 years if one would spare 1 minute for each piece of art.

Now you can relate why I had trouble when I wanted to visit Hermitage for a few hours. I didn’t have enough time and I wanted to see important art works such as the Dessert: Harmony in Red by Henri Matisse. Eventually I realized that this is a problem I had faced before.

Actually, each and every one of you must have faced such problems in your daily lives. Most common one: “Which route you should take between home and work during rush hour traffic?”

Postman’s Path

Facing such problem in Saint Petersburg is a pleasing coincidence as this magnificent city once was home to one of the giants of mathematics: Leonhard Euler. If you take a look at the first article of graphs you can see that Euler is the person who initiated the discovery of Graph Theory with his solution to the famous Seven Bridges of Königsberg problem.

In 1960 (almost 230 years after the solution of Königsberg) a Chinese mathematician named Mei-Ko Kwan took a similar problem into his hands:

A postman has to deliver letters to a given neighborhood. He needs to walk through all the streets in the neighborhood and back to the post-office. How can he design his route so that he walks the shortest distance?

This problem is given the name Chinese Postman Problem as an appreciation to Kwan. There are a few things you should know about the postman problem:

• Postman must walk each street once.
• Start and finish point must be at the post-office.
• Postman must fulfill these two conditions in the shortest possible time.

Power of Graphs

Mei-Ko Kwan turned to Euler’s Königsberg solution in order to solve the postman problem. According to Kwan postman problem could have been shown as a graph: Lines represent the streets and letters represent the houses.

Example Graph:

A graph has an Euler circuit if and only if the degree of every vertex is even. In other words, for each vertex (point) count the number of edges (lines) it has. If that number is even for each vertex, then it is safe to say that our graph has an Euler circuit.

Solution

As you can see above, if the degree of every vertex in a graph is even, then we can conclude that the graph has an Euler circuit. Let’s assume that the following is our graph:

First of all we must determine the degree of each vertex:

As seen above all the vertices have even degrees. This is how we can conclude that the graph has an Euler circuit even without trying to find the path itself. Hence the postman can use the existent roads and finish his route in the shortest time:

When a graph has vertices with odd degrees, then we must add new line(s) to the graph in order to create an Euler circuit. These are the steps you can follow:

1. Find the vertices that have odd degrees.
2. Split these vertices into pairs.
3. Find the distance for each pair and compare them. The shortest pair(s) shows where to add new line(s).
4. Add the line(s) to the graph.

Let’s use an example and test Kwan’s algorithm for the solution. Assume that A is the starting point. First we must check the degrees of the vertices:

Unfortunately A and D have odd degrees which is why the postman can’t finish his walk:

Here we have only one pair that is A-D. There are three routes between A-D. If we find the shortest one and add that to our graph, we will have an Euler circuit:

The shortest one is the line between A-D as seen above. If we add that line, we will have the shortest route for the postman:

One wonders…

If the post office is at A, what is the route for the postman to take so that he will finish his day in the shortest way?

M. Serkan Kalaycıoğlu

Real Mathematics – Graphs #3

Do I Know You?

Frank Ramsey was tangling with a mathematics problem back in 1928. In the end he realized that he should invent a whole new mathematics branch in order to find a solution to this specific problem. Unfortunately Frank Ramsey died at the age of 27, even before his findings were published. Although he won immortality as this new mathematics branch was named after him: Ramsey Theory.

One of the fundamental problems in Ramsey theory: Could one find order inside chaos? (Here, chaos is used as “disorder”.)

Ramsey theory has various applications in different mathematics branches including logic and graph theory. In this article I will be talking about how graph theory emerges with Ramsey theory.

What is needed: Randomly chosen six people.

Existing chaos: Among those six people who is friends or not friends (strangers) with whom. (Being a friend is mutual: Just because you know Sean Connery doesn’t mean that you are friends with him.)

Desired order: Set of three people among the group of six who are friends or not friends with each other.

Let’s draw the graph of these six people in which dots will represent the individuals, straight lines will represent friendship and dashed lines represent being strangers (not friends).

You might wonder where chaos is in this graph. There are over 30.000 possibilities for only six people to be or not be friends with each other. This is an enormous numbers for a very small group and the graph above shows only one possibility.

In our graph a triangle with sides that are straight lines means that three people are friends with each other. That means a triangle with sides that are dashed lines shows that three people are not friends with each other. This is why we have to look for any kind of triangles in the graph. Obviously we see multiple examples of both in our graph: For instance Bill-Rasputin-Lewinsky makes a friendship triangle as Alexandra-Lewinsky-Hürrem makes a not-friends triangle.

Now there is another important question: How can we know that all those over 30.000 possibilities possess either one of these triangles?

Yes

As it is almost impossible to try every single possibility, we have to come up with a simple and short proof.

Take Rasputin in hand: If he was friends with everyone that would mean that he had 5 friendships and 0 not friendships. All the possibilities for Rasputin are shown below:

These possibilities show us that for every individual in the group, there are at least 3 possibilities for being friends or being strangers. So, we can choose either one of them. Assume that Rasputin is friends with 3 people in the group.

At this situation in order to avoid a triangle for friendship with Rasputin, Lewinsky-Hürrem-Alexandra should be strangers with each other.

Thus, those three would provide a triangle with dashed lines: A triangle of strangers.

This proves that every one of those over 30.000 possibilities has at least one three-friend set or one three-stranger set.

If Lewinsky is friends with Hürrem, they make a friendship triangle with Rasputin. Same goes for Hürrem&Alexandra and Lewinsky-Alexandra. Thus it is impossible to avoid triangles.

One wonders…

Try to find out what would happen if we had 5 people in our group.

M. Serkan Kalaycıoğlu

Real Mathematics: Graphs #2

You’ve been sent for scouting a forest nearby your village. You are done with your duty and on your way back home you are bringing a wolf, a goat and some cabbage with you. Wolf would like a piece of goat and goat is looking hostile against the cabbage, but they can’t do anything with your presence. Then you come across with a deep river. Luckily for you, there is a small boat on coast.

The Catch: Boat is so small it allows you to take only either one of wolf, goat or cabbage. Is there any way you can take everything to the other side of the river safely?

Solving Puzzles with Graphs

In the previous article I told you how Euler used a brand new approach to a seemingly insignificant puzzle and how his method became the basis of graph theory. Drawing graphs in certain cases really improve the chances of reaching an answer. Graphs also help us understand why there is not a solution, in case problem has no solution. Graphs are so powerful at times they can even show us what kinds of conditions are needed to solve a problem that has no solution.

In the river problem, let’s use Euler’s methods. You are all on the left side of the river and you have to get across the right side of it. Now assume that left side of the river is assigned as position 1, and right side as position 2.

There are wolf, goat and cabbage. In the puzzle, those three stand on the position 1 which might be shown as a point named 111 (wolf-goat-cabbage on the positions 1-1-1). Ultimate goal of the puzzle is to find a way to get them all to the point 222.

There are eight different positions for the wolf, goat and cabbage: 111, 112, 121, 122, 211, 212, 221 and 222. For instance 112 means wolf is at position 1 (left side of the river), goat is at position 1 (left side of the river) and cabbage is at position 2 (right side of the river).

Drawing the Graph

We assumed that all these 3-digit numbers represent a point. To get from one point to another, we could only change exactly one digit of it, as we are allowed to take exactly one of wolf, goat or cabbage into our boat. Then there are limited ways to go from one point to another. Let’s assume that if you can go from one point to another, then there is a line connecting those two points.

For instance 111 and 112 has a connection as there is exactly one digit that differ those numbers. Although 111 and 212 has no connection as there are more than one digit that differ those numbers.

Finally we found our points and lines and how they could be drawn as a graph. I think Euler would be proud of us.

Our starting point 111 has three options: 112, 121, 211. Our graph looks like following when all relationships between points are shown:

As our ambition is to reach point 222 from the point 111, it is easy to see the ways to the solution in the graph. However we can’t move between points as we’d like to. We can only use paths which satisfy puzzle’s rules: If they are left alone, wolf eats goat and goat eats cabbage.

Solution

The point 111 has three options: 112, 121 and 211. If we select 112 (taking cabbage to the right side) wolf and goat would be alone, so this path is not good for us. The point 211 would mean leaving goat with cabbage which is forbidden as well. Hence there is only one way to select from the point 111: The path to the point 121.

The point 121 has three options: 111, 122 and 221. We can’t go back, so the point 111 is out. We should choose either 122 or 221.

Choosing 122

This would mean that we are taking cabbage to the right side of the river, near the goat. There are again three options: 121, 222 or 112. We can’t go backwards, so the point 121 is out.

222: Choosing this path would give us the answer. But, in order to do that we must leave goat and cabbage alone and go get wolf. Until we are back to the right side of the river, goat would be doing its final chewing. Hence, we can’t choose this path.

112: This is the only real option we can choose.

From 112, there are again three options: 122, 212 and 111. We can’t go backwards, so the points 122 and 111 are out. Path to the point 212 is the only choice.

At the point 212, wolf and cabbage are on the right side of the river and goat is on the left side. Here, we can go to the left side, pick goat with us and reach the point 222. This would give us the solution we were looking for.

Choosing 221

Now go back and choose the path to the point 221. There are again three options from 221: 222, 211 and 121. We can’t choose the point 121 as it would mean going backwards. Going to the point 222 would solve all our problems, but if we try to do that, we would have to leave wolf and goat alone at the position 2. This gives us the option 211.

The point 211 also gives us three options: 111, 221 and 212. Choosing 111 and 221 would mean going backwards. Then we must follow the path to 212. From the point 212, we can directly choose the path to the point 222. And we would again find the solution within the lines of the rules of the puzzle.

Check It Out

Add other animals and vegetables to these three and try to draw the graph. Using the graph, see if you can find a solution to your puzzle.

M. Serkan Kalaycıoğlu

Real Mathematics: Graphs #1

Puzzles and mathematics have a deeper relationship than one might assume. When you take a look at history of mathematics, it is not that rare to see a puzzle causing mathematics to change.

Without a doubt, Seven Bridges of Königsberg (1736) is the most famous one of those stories.

Leonhard Euler, one of the most influential mathematicians of all times, was given this puzzle/problem in the 18th century. Euler had a great reputation for solving “unsolvable” questions, and major of Königsberg asked for his help. Euler was not pleased to receive this problem at first as he said “… I don’t believe this question has anything to do with mathematics.” Although after some time he believed that the problem was interesting enough to deal with.

Euler’s solution to Seven Bridges of Königsberg problem culminated a couple brand new mathematics branches to emerge: Topology and graph theory. What fascinates me about this story is that these branches came out almost 150 years after Euler’s solution.

Seven Bridges of Königsberg

Take any book on graph theory. Open first chapter’s first title. You’ll see Euler’s solution for this simple problem:

The old town of Königsberg has seven bridges as shown on the map. Is it possible to take a walk through the town, visiting each part of the town and crossing each bridge once and only once?

I encountered with this problem for the first time in the junior year of my math major. I first thought that the question was dull and I could solve it with ease. After spending a night with full of disappointments and a lot of cursing, I gave up. I knew that it was impossible to take that walk and I knew that it was possible when I removed one bridge. But I didn’t know why.

Soon enough, I realized that I needed fundamentals of the graph theory to understand the answer. Euler’s solution to this simple puzzle is the basis of a whole new mathematics branch: Graph theory.

What Euler Did

First thing Euler did was to imagine that bridges and lands as two different groups. According to him, solution of Königsberg problem didn’t depend on the physical appearances of them. Euler realized that it didn’t matter how long or curvy a bridge is, or if a land is an island or not.

He just thought that bridges could be represented as edges numbered from 1 to 7, and lands could be represented as vertices named A,B,C and D. When all Königsberg problem map is put into a piece of paper with using on edges and vertices, we would end up with a graph.

Degree of a vertex is the number of edges it has.

According to Euler, in order to find a solution for Königsberg problem either of these should be found in the graph:

1. Exactly two vertices should have odd number of degrees. That would mean one of the vertices is the start of the tour as the other is the finish.
2. All of the vertices should have even number of degrees. That would mean one could start the tour from any vertex.

Why?

If a vertex is neither start nor finish of the tour, then in case one edge comes to that vertex another one should leave so that the vertex would be neither the start nor the finish. (Because if an edge comes to a vertex and another doesn’t leave, it means that vertex is the finish of the tour. And if an edge leaves from a vertex but another doesn’t come back to it, then it means that vertex is the start of the tour.) This would mean that the vertex should have even number of degree. Although, if vertex has odd number of edges, in order to keep odd degree we shouldn’t let another edge to leave in case there is an edge coming to that vertex. This would mean that the so called vertex is either start or finish of the tour.

Also, if there are no vertices in the graph with an odd degree, then a chosen vertex could well be both start and finish of the tour.

Eulerian Path: If a path/tour in a graph contains each edge of the graph once and only once, then that path is called Eulerian Path.

I am aware that the paragraph above is a bit confusing. Let me give you a few examples to clear your mind about degree of a vertex.

Examples:

1. One Bridge: Two lands and one bridge graph.
2. Two Bridges: Two lands and two bridges graph.
3. Three Lands: Add land C into the previous graph.

In this case there are two vertices with odd number of degrees. Hence, there is a solution for this graph but vertices B and C should be the start and finish of the path.

Solution to Königsberg

Euler saw the Seven Bridges of Königsberg as this graph.

Numbers of degrees for the vertices are 5, 3, 3 and 3 in order. This means that the Königsberg graph has more than two odd numbers of vertices which is a violation for the rule. This is concludes that there is no such tour/path for the seven bridges of Königsberg.

Topology is the mathematical study of the properties that are preserved through twisting and stretching of objects. (Tearing, however, is not included.) Topologically a circle and an ellipse are equivalent to each other.

Check it out

Which objects are topologically equivalent to each other ?