How did Leonhard Euler help establish graph theory?
Leonhard Euler is credited with establishing graph theory through his 1735 solution to the Königsberg bridge problem. This recreational puzzle asked whether it was possible to walk through the city of Königsberg by crossing each of its seven bridges exactly once.
Euler proved that such a path was impossible by analyzing the number of bridges connected to each landmass. He determined that for a path to traverse every bridge exactly once, each landmass (except potentially the start and end points) must be an endpoint of an even number of bridges. Because the landmasses in Königsberg had an odd number of bridges, the walk could not be completed.
By focusing on the connections between landmasses rather than their physical geography, Euler essentially created the first theorem in graph theory. He described this approach as geometria situs ("geometry of position"), which laid the foundation for both graph theory and topology. Additionally, his 1750 polyhedral formula, , further advanced these fields by relating the vertices, edges, and faces of a polyhedron.