In Folha: Lessons from the Königsberg bridges serve the internet.
Cidade de Kalingrado, antiga Königsberg | Foto: Valdis Pilskalns – Wikimedia Commons
Reproduction of Marcelo Viana's column in Folha de S. Paulo.
At the beginning of the 18th century, the Prussian city of Königsberg was divided into four regions separated by branches of the Pregel River: the two banks, the island of Kneiphof, and the Lomse district. Connecting them were seven bridges: Kneiphof had two bridges on each bank, Lomse had one on each bank, and the seventh bridge connected Kneiphof to Lomse.
We don't know how or when the question arose: is it possible to take a tour of the four regions crossing each bridge only once? The great Leonhard Euler solved the problem in 1735 in the following way:
Each time the tour passes through one of the regions, two bridges are crossed: one to enter, the other to exit. Therefore, apart from the starting and ending regions, all the others must be served by an even number of bridges. But in Königsberg, all the regions had an odd number of bridges: 5 in Kneiphof and 3 in each of the others. Therefore, the requested tour could not exist.
Read more: Preliminary list of those qualified for the 2nd phase of OBMEP published
Pi Center's AI project is highlighted at FAPERJ.
'I like equations and complex problems,' says Henrique.
A crucial aspect of Euler's reasoning is abstraction: details are irrelevant; all that matters are the regions, which we can represent as points, and the bridges, which we can represent as lines connecting those points. Such configurations, formed by a certain number of points connected in pairs by lines, are called "graphs".