This entry is a continuation of: Königsberg: The problem.
After numerous unsuccessful attempts, the solution to this “fun” combinatorial problem was provided by the Swiss mathematician Leonhard Euler in 1736. Euler not only demonstrated the impossibility of the alleged walk, but also gave a simple general criterion to solve any problem of the same type.
Euler, for greater clarity, replaced each of the pieces of solid land with a point and each bridge with a line, giving rise to a simplified scheme that is represented in the attached figure. Thus, the island is represented by the point at which five lines reach, since there are five bridges that go to it. The resulting figure is a graph (a graph is a set of points called “vertices or nodes” of the graph and a set of lines that join them that are called “edges or sides” of the graph).
The problem is reduced to drawing the figure, starting from a point, from a stroke, that is, without lifting the pencil from the paper and without tracing the same line twice. A route with these characteristics is called an Eulerian path.
We will show that it is impossible to draw our figure in a single stroke. In effect, each nodal point must be reached from one side and exit from a different one; This rule only has two exceptions, which are the departure point, which you do not have to reach, and the arrival point, from which you do not have to leave.
Therefore, if such a path were possible, it is necessary that at all the vertices of the graph, except at most two, two, four… edges converge, that is, an even number of them converge. But in each of the nodes of the graph corresponding to the Königsberg bridges there is an odd number of edges (3, 5, 3, 3).