Seven bridges of Königsberg

2021-06-20
1 min read

Seven Bridges of Königsberg

Question: Is there any route for the following tour such that every bridge is crossed exact once?

drawing

Euler’s solution to this tricky problem: reduce the problem to graph by converting landmass to vertices (green) and bridges to edges (red) such that we obtain the following graph.

drawing

Euler observed further, that in order for every bridge/edge to be crossed only once, we can only enter a vertex by one bridge and leave the vertex with another bridge. In other words, each vertex must have an even degree, having an even number of edges.

Note: A graph, for which every vertex has an even degree, is called an Eulerian graph.