Intro & Intensions
Hey everyone! I would like to welcome you to my very first post in this site. As you might read before at other locations at this site, I am going to discuss various topics in Mathematics, where one of them is going to be Graph Theory.
For the section of Graph theory, my goal is to bring as many topics as possible about graphs, including: theorems, definitions, examples, special graphs, applications, graph algorithms and so much more!
My intentions are to write in this section about 1 post every week, or maybe even 2 in some weeks. I’ll see how I handle it.
Well, That’s about it with all the technical stuff, let’s dive in! Before starting with definitions, I would like to present a short story, a story that probably every one who is familiar with Graph theory, is familiar with it as well.
Seven Bridges of Königsberg
Until about a century ago, there was a city in Prussia (which is now Kaliningrad and Russia) called Königsberg. The city had a river in it, and is also had 7 bridges that allowed people to walk over the river in order to reach different areas of the city.
There was one question that a lot of people were wondering about, the question was: Can you walk in the city in such way that you go through all 7 bridges, while not visiting the same bridge twice?
That is actually a reasonable question to ask, for example, as a tourist who is short in time, you would want to visit the whole city but you don’t want to spend your time visiting the same bridge twice.
People have tried to find a solution – An ideal path, the most efficient one, however, it seems like they weren’t getting any closer to a solution… mathematicians all over the world also got involved and tried to solve this problem but with no success.
Usually throughout history, when mathematics are stuck on a problem for a long time, it may be a sign that new math should be discovered. New tools or maybe even a new Theory might be the solution for the problem (I’ll discuss another outstanding example of this phenomenon when I’ll talk about Galois Theory, where problem that couldn’t be solved in two thousand of years, were solved with an extremely short proofs)
Well, as you might have guessed, our situation is exactly a case of this phenomenon. The person who came up with the solution was Leonard Euler. He was a brilliant mathematician who solved and developed WAY MORE problems and theorems except this one. He decided to think at different pieces of land as dots and on bridges he thought as lines going from one dot to another. For example, if there is bridge between two land pieces he would draw two dots, and a line between them. Try drawing all the dots and lines yourself (seriously, try it! It’s a nice and easy challenge). If done correctly, what you are going to get is something like this:
Remember this image, that is the First example of a graph presented here on this site! turns out that this wired sketch was a major key to the solution. You may be curious about the solution but unfortunately I won’t to be able to show it now, when we even haven’t seen a definition of a graph! We don’t even know what it is. But I will tell you the result, it might be kind of a bummer to hear that this problem has no solution! Yes, you read it right, after all those efforts, it turns out it can’t be solved at all. That really unfortunate, Isn’t it? Well, yes, however, this problem was the origin of graph theory, that over the years turned out to be one of THE MAJOR theories in mathematics and computer science. The theory is useful also in social sciences, economics, road designing, and much, much more! So, maybe the fact that you can’t travel Königsberg in an efficient way is not so bad after all…
In the next post, I am going to represent the formal definition of a graph, show examples, and I’ll start develop the theory.
That’s is for now! Don’t worry though, we will see why the problem stated above is unsolvable. See you in the next one!