Database Reference
In-Depth Information
° I will then have to cross another five bridges, leaving and entering
different parts of the city
° Finally, I will end the walk through Königsberg in another part of
the city
Therefore, Euler argues, the casemustbethattheirstandlastpartsofthecityhavean
odd number of bridges that connect them to other parts of the city (because you leave
fromtheirstpartandyouarriveatthelastpartofthecity),buttheothertwoparts
ofthecitymusthaveanevennumberofbridgesconnectingthemtotheirstandlast
parts of the city because you will arrive
and
leave from these parts of the city.
This "number of bridges connecting the parts of the city" has a very special meaning
in the model that Euler created, the graph representation of the model. We call this the
degree of the nodes in the graph. In order for there to be a path through Königsberg
that only crossed every bridge once, Euler proved that all he had to do was to apply a
very simple algorithm that will establish the degree (in other words, count the number
of bridges) of every part of the city. This is shown in the following diagram:
This is how Euler solved the famous "Seven bridges of Königsberg" problem. By
proving that there was no part of the city that had an even number of bridges, he
also proved that the required walk in the city cannot be done. Adding one more
bridge would immediately make it possible, but with the current state of the city,
and its bridges at the time, there was no way one could take such an
Eulerian Walk
ofthecity.Bydoingso,Eulercreatedtheworld'sirstgraph.Theconceptsand
techniques of his research, however, are universally applicable; in order to do such
a walk on any graph, the graph must have zero or two vertices with an odd degree,
and all intermediate vertices must have an even degree.
