Königsberg Bridge Problem ( Trivia # 16 )

The Konigsberg Bridge problem is perhaps the best known example in the graph theory. It was a long-standing problem until solved by Leonhard euler in 1736, by means of a graph. The problem is depicted in the pictures given below.

Fig. 1

Fig. 2

Two islands , C and D, formed by the Pregel River in Konigsberg were connected to each other and to the banks A and B with seven bridges, as shown. The problem was to start at any of the four land areas of the city , A , B , C , or D, walk over each of the seven bridges exactly once, and return to the starting point ( without swimming across the river, of course :D ).

U can now see this situation by means of a graph, as shown in the figure below. The vertices represent the land areas and the edges represent the bridges.

Fig. 3

Before dealing with this problem let us generalize this problem .... as proposed by the Euler Graphs
def : If some closed path in a graph passes through all the vertices , then this path is called an Euler line and the graph an Euler graph . Thus an Euler Graph has no isolated vertex and all vertices form an interconnected network ...
Another important property of an Euler Graph is that all the vertices are of even degree ?? Puzzled ....
Since it is an Euler Graph it contains an Euler line(the closed path). In tracing this line we observe that every time it meets a vertex 'x' two lines are created .. one "entering" that vertex and another "leaving" the vertex . This is not only true for all intermediate vertices but also for the terminal vertex (because we "entered" and "exited" this vertex at the begining and end) . This proves that the degree (no. of lines radiating from a vertex) of every vertex is even .

An Euler Graph

Thus for finding the solution to the Konigsberg bridge we need to check whether its graphical representation is an Euler Graph .... U can check urself that its vertices are not having even degree .Thus it is not possible to walk over each of the seven bridges exactly once and return to the starting point . Hence the Konigsberg Bridge problem possesses no solution .

Another variation of this kind of problem is mentioned below ...... u might have tried it when u were a kid ...
Without lifting the pencil draw this figure without passing through the same line or curve twice ..


I made another version of this Konigsberg Bridge .... try this too ... and post ur solution in comments ...

Mahato Ka Bridge :)