The Seven Bridges of Königsberg

The city of  Königsberg, Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel river.  There were two islands on the river and there were seven bridges connecting them and the main land as shown in Figure 1.

Figure 1

Residents observed that using the bridge at the southern part of the city (Bridge 1 in Figure 2) as starting point, they could not stroll around crossing all the bridges only once. They had to skip one bridge or cross some bridges twice. Some of them conjectured that it was impossible to cross the seven bridges once and only once, but they could not explain why.  » Read more