Do you know that facebook has its own mathematical problem? It is called the facebook friendship problem. Never heard of it?!
Well, this problem is to prove that if you pick out 6 arbitrary people on facebook, then among these 6 people, you can find 3 people such that they are all mutually friend of each other, or there are no friendships among them at all.
For example, in the figure below, on the left we have 6 people: Amy, Ben, Cindy, Dan, Emma and Francis. If two of them are friend on facebook then we connect them by a purple line, and if they are not friend on facebook then we connect them by a blue line.
We can see that in this example, we can pick out 3 people, which are Amy, Dan and Emma, they are all mutually friend of each other because they are connected by purple lines. The same is true for Francis, Ben and Cindy.
In the example on the right, we have 6 people: Kate, Linda, Matt, Noah, Olivia and Peter. Among them we can pick out 3 people, which are Olivia, Noah and Matt, there are no friendships among them because they are connected by blue lines. The same is for Peter, Noah and Matt.
This facebook friendship problem is an example of a problem in graph theory. A graph has a number of vertices and edges. An edge is used to connect two vertices together. Our facebook graph has 6 vertices representing 6 people, and between any two vertices, there is exactly one edge connecting them which is colored either by purple or blue. Below are some examples of graph.
One of the earliest problems in graph theory is the famous "7 Bridges of Königsberg" problem posed by Euler. The city Königsberg is now in Kaliningrad of Russia. If we use Google Map to search for this city we can see that the bridges in Kaliningrad are now in different locations compared to those in the time of Euler.
 |
| The current view of Kaliningrad |
In Euler's time, 1736, the city Königsberg had 7 bridges as in the following picture
 |
| 7 bridges of Königsberg in Euler's time (colored by purple) |
The problem that Euler posed is to find a walk around the city so that every bridge is crossed once and only once. Euler used graph to show that it was impossible to do that.
To prove this, Euler created a graph that had 4 vertices A, B, C, D representing 4 different areas of the map as in the following figure. These areas are separated by a river and to go from one place to another we need to cross a bridge. Euler then used 7 edges of the graph to represent the 7 bridges, so for example, because there were 2 bridges connecting the two areas A and B, so in the graph, there are two edges connecting the two vertices A and B.
Now, the question becomes asking whether or not there is a path in the graph that goes through every edge exactly once. Such a path is now called Euler path in his honor.
To determine whether an Euler path exists or not, we need to count how many vertices of odd degrees and how many vertices of even degrees. Here we define the degree of a vertex is the number of edges of that vertex. In the graph of the 7 bridges, vertex A has degree 5 (odd), vertex B has degree 3 (odd), vertex C has degree 3 (odd) and vertex D has degree 3 (odd). So the graph has 4 vertices of odd degrees.
In a connected graph, Euler path exists if and only if the graph has no vertices of odd degrees, or the graph has exactly two vertices of odd degrees. The above graph has 4 vertices of odd degrees, and this is why no Euler path exists.
The following graphs have Euler paths. The one on the left has 2 odd degree vertices and the one on the right has no odd degree vertices. It means that we can use pencil to draw each of these graphs on a paper in one stroke without retracing and without picking up the pencil off the paper.
We will use the Pigeonhole Principle to solve this problem. The Pigeonhole Principle is stated roughly as follows, if we put 5 pigeons into two holes then one hole must contain at least 3 pigeons.
Now, going back to our facebook graph, let us pick out a vertex. Suppose we pick out vertex "Amy". From vertex "Amy" we have 5 edges. These 5 edges can be considered as "5 pigeons"! If an edge is colored blue then we put it in the blue hole, and if it is colored purple then we put it in the purple hole.
By Pigeonhole Principle, one of the holes must contain at least 3 pigeons, suppose that it is the purple hole. It means that we have at least 3 purple edges.
Suppose that the edge Amy-Emma, the edge Amy-Dan and the edge Amy-Cindy are purple.
Consider the triangle Emma-Dan-Cindy. If this triangle has at least one purple edge, for instance, if the edge Emma-Dan is purple (as in the figure on the left below), then we have found a purple triangle Amy-Emma-Dan. On the other hand, if none of the edges of the triangle Emma-Dan-Cindy is colored by purple then Emma-Dan-Cindy is a blue triangle (as in the figure on the right below).
In all cases, we always can find a purple triangle or a blue triangle, and the problem is proved.
So today we have used graph to prove the following interesting result
The number 6 is the best optimal number because if we choose 5 people then this property no longer holds as depicted by the following graph.
This facebook problem is actually a special case of a much harder problem -- the Ramsey's problem. A special branch of mathematics, known as the Ramsey's theory, has been developed as the result of studying this problem. We may come back to this problem in our future posts.
Talking about facebook, do you know that we have just launched our own facebook's page! Please connect to us, and if you like what you read here, please "like" and "share" it with your friends.
Hope to see you again in the next post.
To determine whether an Euler path exists or not, we need to count how many vertices of odd degrees and how many vertices of even degrees. Here we define the degree of a vertex is the number of edges of that vertex. In the graph of the 7 bridges, vertex A has degree 5 (odd), vertex B has degree 3 (odd), vertex C has degree 3 (odd) and vertex D has degree 3 (odd). So the graph has 4 vertices of odd degrees.
In a connected graph, Euler path exists if and only if the graph has no vertices of odd degrees, or the graph has exactly two vertices of odd degrees. The above graph has 4 vertices of odd degrees, and this is why no Euler path exists.
The following graphs have Euler paths. The one on the left has 2 odd degree vertices and the one on the right has no odd degree vertices. It means that we can use pencil to draw each of these graphs on a paper in one stroke without retracing and without picking up the pencil off the paper.
Let us now go back to our facebook friendship problem. In the language of graph theory, our problem is stated as follows.
Problem: Given a graph that has 6 vertices, any two vertices are connected by an edge of either color purple or color blue. Prove that in this graph, there exists a triangle whose three edges are all colored by the same color.
We will use the Pigeonhole Principle to solve this problem. The Pigeonhole Principle is stated roughly as follows, if we put 5 pigeons into two holes then one hole must contain at least 3 pigeons.
 |
| Pigeonhole Principle: put 5 pigeons into two holes then one hole must contains at least 3 pigeons |
Now, going back to our facebook graph, let us pick out a vertex. Suppose we pick out vertex "Amy". From vertex "Amy" we have 5 edges. These 5 edges can be considered as "5 pigeons"! If an edge is colored blue then we put it in the blue hole, and if it is colored purple then we put it in the purple hole.
By Pigeonhole Principle, one of the holes must contain at least 3 pigeons, suppose that it is the purple hole. It means that we have at least 3 purple edges.
Suppose that the edge Amy-Emma, the edge Amy-Dan and the edge Amy-Cindy are purple.
Consider the triangle Emma-Dan-Cindy. If this triangle has at least one purple edge, for instance, if the edge Emma-Dan is purple (as in the figure on the left below), then we have found a purple triangle Amy-Emma-Dan. On the other hand, if none of the edges of the triangle Emma-Dan-Cindy is colored by purple then Emma-Dan-Cindy is a blue triangle (as in the figure on the right below).
In all cases, we always can find a purple triangle or a blue triangle, and the problem is proved.
So today we have used graph to prove the following interesting result
If we choose 6 arbitrary people on facebook, then among these 6 people, we can always find 3 people such that they are all mutually facebook friend of each other, or between these 3 people, there is no facebook friendships at all.
The number 6 is the best optimal number because if we choose 5 people then this property no longer holds as depicted by the following graph.
 |
| in this graph of 5 vertices, there is no triangle of the same color |
This facebook problem is actually a special case of a much harder problem -- the Ramsey's problem. A special branch of mathematics, known as the Ramsey's theory, has been developed as the result of studying this problem. We may come back to this problem in our future posts.
Talking about facebook, do you know that we have just launched our own facebook's page! Please connect to us, and if you like what you read here, please "like" and "share" it with your friends.
Hope to see you again in the next post.