 Na imagem visualizamos o logotipo do projeto 'MatematiZou', escrito com letras de forma na cor verde-azulada. A letra “Z” está na cor branca dentro de um hexágono com pontas arredondadas preenchido na mesma tonalidade de cor do restante das letras.  Na imagem temos um mini caminhão branco de madeira, cuja caçamba é azul escura e está escrito em letras brancas “UFABC”. As rodas do caminhão são vermelhas e quadradas. Cada par de rodas do caminhão está em cima de uma pista com ondulações.  Na imagem, há várias pessoas participando do evento “UFABC para todos” no Ginásio da UFABC campus Santo André. Algumas pessoas estão ao redor de uma mesa com jogos que incluem copos, mapas, tabuleiro de xadrez, entre outros, e outras, estão vendo as exposições espalhadas por todo o ambiente.](https://matematizou.gradmat.ufabc.edu.br/files/LogoMatematizouTeal.png)
The ancient city of Königsberg, Prussia, which is now Kaliningrad, Russia, boasts an intriguing geography: the Pregel River coursing through the city bifurcates, forming two islands, Kneiphof (center of the image below) and Lomse.
Seven bridges connected the islands and the city: four linking Kneiphof to the rest of the city, two connecting Lomse, and one spanning between the two islands. This unique layout posed a question, which eventually became widely renowned: “Which path crosses all the bridges, but only once each?” Can you provide an answer?
Attempt to draw the path in the simulation below. Begin by selecting the starting region, then choose the bridge over which your path will cross.
If you were unable to achieve the task, do not despair! The author of this text also couldn’t. We know the solution thanks to the eminent mathematician Leonhard Euler, who resolved the problem in 1736.
The initial step is to “abstract” the problem: Euler discerned that the size of each island, the city, or even the bridges themselves did not matter; what mattered was merely which of them your path is traversing. Armed with this understanding, we can reconstruct the problem in a more abstract form—albeit one that elucidates the issue—by creating what we call a graph.
Given that dimensions are inconsequential, we can envision each locality as a point: K represents the vertex for the Kneiphof island, L for Lomse, and N and S respectively denote the “north” and “south” parts of the city (see markings in Fig. 2). Furthermore, the lines connecting the vertices symbolize the bridges linking the represented places.
Having achieved this, a simple thought from the mathematician sufficed to solve the problem: to traverse each edge only once, each vertex “in the middle of the path” must be connected to an even number of edges, as for each “incoming” edge, we must have an “outgoing” one. Now, the starting and ending vertices of the path must possess an odd number of edges, as the departing vertex need not have an incoming edge, and conversely, the final vertex need not have an outgoing edge. Euler’s conclusion for Königsberg is that the desired path doesn’t exist, as all vertices possess an odd number of edges!
It’s crucial to note that abstraction is a powerful tool: Euler not only solved the problem of Königsberg’s bridges but also provided us with a method to solve any similar problem concerning the existence of paths, as long as they can be represented in some form of graph!
