Exercise 6.15 (Bridges in K¨onigsberg). As can be seen in Fig. 6.1 there were seven bridges, two from point a (the north side of a river) to point b

(an island in the middle of the river), two from point d (on the south side of the river) to point b (on the island). After the island the river branches to the north and the south, and there are three more bridges, one from point c (on the east of the branch) to point

a, one to point b and one to point

d. And the problem is quite simple.

1 Draw a sketch of this graph.

2 Find a Boolean model for this problem.

3 Find all Eulerian paths.

4 Modify the problem such that the bridge from point b to point c is removed. Find a Boolean model for the modified problem.

5 Find all Eulerian paths for the modified problem.