Chapter 9, Problem 1RE

In the Konigsberg Bridge Problem, a tragic fire destroys the bridge from B to C and also one of the bridges from A to D. (See Fig. 9.1.) Draw a graph representing the new situation. Show that it is now possible for someone to start on land mass B and walk over each of the bridges exactly once, returning to B again.

To determine

A graph representing the new situation. And that it is know possible for someone to start on land mass B and walk over each of the bridges exactly once, returning to B again.

Explanation of Solution

Given information:

A graph representing the new situation. And that it is now possible for someone to start on land mass B and walk over each of the bridges exactly once, returning to B again. In the Konigsberg Bridge problem a tragic fire destroys the bridge from B and C and also one of the bridges from A to D.

Explanation:

For the Konigsberg Bridge problem the bridge between B and C and the bridge between B and C have been destroyed by a fire. The graph for the Konigsberg Bridge problem has to be modified to removal of these bridge. We also have to show a person can start from land mass B walk on all the bridges just once and finish his/her journey on land mass B.

The Konigsberg Bridge problem to 4 land masses separated by streams of river. Therefore 7 bridge over the streams to connect the land masses. The physical arrangement of the problem is given by the figure below.

The figure can be represented as a pseudo-graph, with the cities represented by vertices and the edges drawn for the bridges connecting cities, as shown below.

The fire destroyed the bridge between B and C, and one the bridges has been destroyed. The pseudo-graph with the corresponding edges removed becomes:

From B, there are two routes to get to A- via BA or by BDA. It is similar for A and C, there are two edges between them.

Therefore are $2\times 2=4$ ways to do this. One is shown below by adding arrow to the edges of the pseudo graph is

Hence the edges and vertices of the pseudo-graph represent the bridge and cities respectively it is possible for a person to start from land mass B and walk over all the bridges exactly and once returning to B at the end.