This should have been my first post in the Graph Theory series but nevertheless I got time to discuss this now. Every one must have heard the famous problem of Seven Bridges of Königsberg.
If not, then please take some time to read about the problem either on the Wikipedia or right down below:
The city of Konigsberb is located on both the banks of the river Pregel(Kaliningrad, Russia - former Prussia). The city also included two big islands and these islands were connected to each other and the main land by the means of seven bridges. Something like below:
The problem is to devise a path starting from one land mass and travelling on each bridge exactly once and come back to the starting point..
Why is this problem so important?
This problem is important because this marks the origin of Graph Theory. So, let us think what sequences of bridges we can choose to device the required walk?
Leonhard Euler proved that it is impossible to devise such a path for this particular scenario and this was the beginning of Graph Theory. He pointed out that the choice of route inside each land mass is not actually important. The only important thing is the sequence of bridges crossed.
Another version of this problem : Draw a figure without lifting your pencil from the paper and without retracing any of the paths.
These kind of puzzles are all over and can be easily solved by Graph Theory. Such a closed walk running through every edge exactly once, if exists then the graph is called a Euler Graph and the walk is called a Euler path or Euler line.
How to find if a graph is a Euler Graph?
Euler proved that a given graph is a Euler graph if and only if all its vertices are of even degree.
Suppose that a graph G is a Euler Graph, that means it has a closed walk which traces all the edges exactly once. If we closely observe, we find that at any vertex there are at least two edges which we have yet not traversed,"one going in from which we enter and the other coming out from which we leave". The last vertex which also happens to be the starting vertex, will also have one incoming edge apart from the one we traversed in the beginning. Hence, each vertex needs to have a even degree.
The above statement just proves that having even degree is a necessary condition which means that it is the proof for necessity
. We are still to prove if that is a sufficient condition as well. Remember we said "if and only if" which means it has to be a necessary and sufficient condition. :)
Proof for Sufficiency:
Let us assume that there is a graph G with all vertices having even degree. Now let us start our walk from a vertex v
and trace as may edges as possible such that no edge is traced more than once. Because all the vertices are of even degree, we can enter and exit from each vertex. We make sure that we end the walk at v.
Now in the above traversal two cases arise:
- We traversed through each edge, in which case the graph is a Euler Graph.
- We traversed through a subset of edges of G, in this case we can name the traversed graph as G'and remove the edges of G' from G.
- Let us say that we get another graph H.
- Now, H will also have all vertices with even degree because the original graph had all the vertices of even degree and we removed an Euler Line from it.
- We also know that G was a connected graph, so H must be touching G at least once. Let us say that the vertex is u.
- So, we can start from vertex u in H and devise a walk such that it goes through as many edges as possible and traverses each edge just once and ends in u.
- Now we can combine G' and H to create a walk with more edges and that would be a Euler Line.
- If the traversed edges consists of all edges in H, then H is also a Euler Graph.
- Else We can remove the edges and follow the same procedure until we obtain a Euler Line consisting of all the edges.
Here is a diagram to pictorially present this
The graph 1 is a graph with all vertices having even degree.
In graph 2 we start a walk from vertex v, let say the walk is (v, w, u, v) . Now this path does not contain all the edges, so let us call it G' and remove the edges of G'.
Let us name graph 3 as H , now we can see that H and G' meet at vertex u
So start a walk from vertex u (u, e, a, b, d, u). This is another Euler Line but it still doesn't consist of all the edges. Hence, remove the edges in H and repeat the same step in graph 4.
Finally we cover all the edges after traversing the path (d, b, c, d).
Hence we can join all the sub graphs and get a bigger Euler Line (v, w, u, e, a, b, d, c, b, e, d, u, v).
Here we learnt that Euler Graphs and Lines are one of the most important topics and the easiest ones.This is used to solve many basic puzzles. The necessary and sufficient condition for a graph to be a Euler Graph is that all its vertices are of even degree.
In the next post in this series, we will try to understand another such important concept called Hamiltonian Circuits and Graphs. We will also learn that it is still unsolved problem.
Stay Subscribed and Happy Learning.