Seven Bridges of Königsberg
Question: Is there any route for the following tour such that every bridge is crossed exact once?
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.
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.