In the last post, I have defined a lot of new stuff and now I want to present a super cool example that demonstrates how to use this new stuff. I have seen this example in my graph theory class, and my lecturer told us that the mathematician Noga Alon is the one who showed it to him, so he is the one who probably deserves all the credit for it. Let’s begin:
I’ll say from now on that a rectangle is called perfect if either it’s width or height is an integer.
Here, The rectangle on the right is perfect, and the rectangle on the left is not perfect. Got it? if you do, I can now present the problem.
Suppose we have a big rectangle, which is made of smaller perfect rectangles, the smaller rectangles don’t have to be of the same size or anything like that, the important thing is that they create one big rectangle.
Remember, all the small rectangles are perfect, Let’s add some measures to the illustration in order to understand it better:
My question is that: “Is the big rectangle also perfect?”. As you see in the illustration, the big rectangle turns out to be perfect, indeed, it’s width equals 8. So we would like to prove that this is always true, But how can we do it? Well, I am talking about graphs and graph theory, so we would probably want to create a graph that will help us. The vertices of the graph are going to be all the vertices of the small rectangles:
However, we also want to add some edges to our graph. This is how we are going to do so: We will go over all the small rectangles, since they are perfect, at least two edges are of a length which is an integer. Why not just one? Cause we are talking about a rectangle, where an edge has the same length as the parallel edge to it. Why ‘at least 2’ and not exactly 2? That’s because a rectangle’s width and height can be both integers.
So, for each small rectangle, We are going to pick one pair of parallel edges of an integer length, and consider them as edges in our graph. However, if two rectangles share an edge, which is of an integer length, we add an edge for each one of the rectangles, thus, we may get multiple-edges in our graph.
The marked edge in the illustration is an example of a multiple-edge. The graph we get in illustration looks like that:
Ok, so we have a graph, we can that this specific graph is not even connected, however, if 2 vertices of the big rectangle are in the same component, then there is a path between them, made of edges with an integer length only – and existence of such a path is actually enough in order to prove the statement, make sure that you understand why!
What can we do now? Let’s try to understand the degrees of the vertices. First of all, let’s start with the vertices of the big rectangle, they are actually quite special : They are the only vertices that belong to only one small rectangle, thus, their degree must be 1 (that is because two edges from the small rectangle of the vertices are in the graph). Great, what about the rest of the vertices, as you will see, there are only 2 options for edges to come out from (right now I am not talking about the graph) the other vertices:
Of course this is not exactly all the ways possible, but the other ones are just rotations of the option on the right. Let’s figure out the case on the right, the vertex is a vertex of 2 small rectangles with one common edge (the vertical one). Now there are few options:
- The common edge’s length is an integer: If we added the common edge from both of the rectangles to our graph, then degree of the vertex is 2. If we chose the common edge only from one rectangle, and from the other we choose the horizontal edge (assuming it’s length is an integer), then the degree is again 2.
- The common edge’s length is not an integer: Then the horizontal edges have integer lengths, thus the degree of the vertex is 2.
If summary, no matter what is the case, when a vertex is of the same ‘type’ as the right option, it’s degree is going to be 2.
If you will try to figure out the degree of the vertex from the left option, you will find out, from similar arguments, that it’s degree is always 4.
Ok, we are now ready for the punch line. Let’s pick one of the four vertices of the big rectangle and consider the component of this vertex, also, I will refer this vertex as 
Summary
Well, what do you think of this proof? I find it amazing and brilliant, it uses only the basic defintions and the super simple theorem from the last post in order to prove a really non-trivial result. It also shows us how we can solve thing using graph in such an easy way. I have to be honest with you, if I had to prove it myself without being familiar with graph theory, I have no idea how I would do it. I don’t think that I would come up with a proof which is not involving graph theory, and I there is probably no simpler way to prove it without graph theory.
This proof is only gives us a little clue about how useful graphs can be although, as a structure, they are very simple!
I really hope you liked this proof like I did when I on saw it my first time (that was a pure ‘mind blowning’ moment for me), and don’t worry – proofs like that and even cooler proofs are yet to come! That’s it for this post – in the next one, I will start talking about sub-graphs and trees and prove some cool theorems about them.