You are here

Leonard Euler's Solution to the Konigsberg Bridge Problem - Euler's Proof and Graph Theory

Teo Paoletti

When reading Euler’s original proof, one discovers a relatively simple and easily understandable work of mathematics; however, it is not the actual proof but the intermediate steps that make this problem famous.  Euler’s great innovation was in viewing the Königsberg bridge problem abstractly, by using lines and letters to represent the larger situation of landmasses and bridges.  He used capital letters to represent landmasses, and lowercase letters to represent bridges.  This was a completely new type of thinking for the time, and in his paper, Euler accidentally sparked a new branch of mathematics called graph theory, where a graph is simply a collection of vertices and edges.  Today a path in a graph, which contains each edge of the graph once and only once, is called an Eulerian path, because of this problem. From the time Euler solved this problem to today, graph theory has become an important branch of mathematics, which guides the basis of our thinking about networks. 

The Königsberg Bridge problem is why Biggs states,

The origins of graph theory are humble, even frivolous…  The problems which     led to the development of graph theory were often little more than puzzles, designed to test the ingenuity rather than the stimulate the imagination.  But despite the apparent triviality of such puzzles, they captured the interest of mathematicians, with the result that graph theory has become a subject rich in theoretical results of a surprising variety and depth [Biggs, 1].

As Biggs' statement would imply, this problem is so important that it is mentioned in the first chapter of every Graph Theory book that was perused in the library.

After Euler’s discovery (or invention, depending on how the reader looks at it), graph theory boomed with major contributions made by great mathematicians like Augustin Cauchy, William Hamilton, Arthur Cayley, Gustav Kirchhoff, and George Polya.  These men all contributed to uncovering “just about everything that is known about large but ordered graphs, such as the lattice formed by atoms in a crystal or the hexagonal lattice made by bees in a beehive [ScienceWeek, 2].”  Other famous graph theory problems include finding a way to escape from a maze or labyrinth, or finding the order of moves with a knight on a chess board such that each square is landed on only once and the knight returns to the space on which he begun [ScienceWeek, 2].  Some other graph theory problems have gone unsolved for centuries [ScienceWeek, 2]. 

Teo Paoletti, "Leonard Euler's Solution to the Konigsberg Bridge Problem - Euler's Proof and Graph Theory," Convergence (May 2011)