**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.**Proof:**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.

**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).**