Skip to main content

Bridges of Konigsberg

Recommended Week

Year 1 : All Weeks

Originator

James Marshall

Problem 1

'In Konigsberg, Germany, a river ran through the city such that in its center was an island, and after passing the island, the river broke into two parts. Seven bridges were built so that the people of the city could get from one part to another. A crude map of the center of Konigsberg might look like this:

The people wondered whether or not one could walk around the city in a way that would involve crossing each bridge exactly once.' (From Mathforum.org)

Can you find a way to do this?

Version with answers (available for CS staff only)

Problem 2

This is a problem from graph theory. Graph theory is a fundamental field of discrete mathematics, particularly useful in Computer Science (e.g. for describing computer networks, constraints on satisfaction problems, etc.) A graph is composed of vertices, and edges connecting them. A graph of our problem is shown below:

This is a very simple graph... we can also asign weights to the edges, and require that edges can only be traversed in one direction (i.e. they are directed). But for our problem this graph is already quite sufficient, and very interesting. In graph theoretic terms our problem is to try to find an Eulerian path for the graph.

Can you find a general way of deciding whether a graph has an Eulerian path or not (this can be presented by adding or removing vertices from the graph a few times and asking if an Eulerian path exists for each graph)?

A trial-and-error solution might try to draw all possible paths through the network, until one was found that had traversed all the edges. Although it would be difficult to remember which paths we'd tried unaided, a computer program performing a depth-first-search could implement this solution. Does that seem like a good idea? Can we place an upper bound on how many paths possible there are to evaluate, if we consider a fully connected graph? Can we think of a simpler solution?

Version with answers (available for CS staff only)

Problem 3

Do all fully connected graphs have an Eulerian path? Consider the fully connected graph with 10 vertices.

Version with answers (available for CS staff only)