How many new bridges do we need to build in Königsberg to achive an Euler circuit?

Question

We know that an euler circuit in a graph is that the starting point and the ending point is the same and that we need to visit all bridge once how do i solve this problem?

*Note that I am talking about the Königsberg of Eulers time and not the modern Kaliningrad.

Answer 1

If you represent the bridges and islands of Konigsberg by a graph, then the graph has 4 nodes and all 4 nodes have odd degree.

To make an Eulerian circuit possible then you have to add two bridges.

However, to make an Eulerian path possible (where the starting node and the end node do not have to be the same) you only have to add one bridge.

Answer 2

Here's a solution from wikipedia: https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg#Solutions

Answer 3

I guess this should be the answer to the problem.

Notice all the degrees are even.

So This is an Eulerian path.