What is a Graph? · Graphs

Lesson 9

Nikolai Chukhin · Alexander S. Kulikov

This is how such a walk could look like. Starting at the northern part, we visit bridges one by one. By the end of the day, we end up on the eastern part after visiting six out of seven bridges.

We missed one bridge and we cannot traverse it without visiting some other bridge again, thus failing to solve the “Seven Bridges of Königsberg” puzzle. But our failure does not imply that the puzzle has no solution! Indeed, maybe there is a better strategy that results in a walk visiting each bridge exactly once.

It was Leonhard Euler who proved that there is no such walk. To prove this, Euler transformed the map of Königsberg to a graph. Each of four parts corresponds to a node in the graph and each bridge corresponds to an edge connecting two nodes.

Afterwards, we remove the map of the city. What is left is a simple graph. Our goal is to find a walk in this graph that visits every edge exactly once (such walks are called Eulerian).

Euler argued as follows. Consider a walk in the graph, e.g., \[C \to B \to A \to D \to B \to A\] (this is not an Eulerian walk: it does not cover all the edges).

In this walk, \(C\) is the starting node, \(A\) is the end node, and \(B\) and \(D\) are intermediate nodes. A simple, but crucial observation:

for each intermediate node, the number of times the walk enters it is equal to the number of times the walk leaves it.

For example, the walk enters \(B\) two times: \[C \color{mc}\overset{1}{\to}\color{black}B \to A \to D \color{mc}\overset{2}{\to}\color{black}B \to A.\] Clearly, the number of times the walk leaves \(B\) is the same: \[C \to B \color{mc}\overset{1}{\to}\color{black}A \to D \to B \color{mc}\overset{2}{\to}\color{black}A.\]

Thus, if there is a walk that goes through all graph edges, then all the nodes, except for possibly two (the start node and the end node), should have an even number of edges incident to it. In the Seven Bridges graph however each node has an odd number of edges making the puzzle unsolvable.