Database Reference
In-Depth Information
Graph Theory
The history of graph theory begins with Leonhard Euler (pronounced “oiler”), the Swiss mathematician and physicist.
Euler made many significant contributions to pure and applied mathematics over a more than 50-year academic
career. His solution to the Seven Bridges of Königsberg problem in 1735 is considered to be the first theorem of graph
theory and one of his most important contributions.
1
The Seven Bridges of Königsberg problem was to find a path through the city that would cross each of the seven
bridges connecting two large islands. Figure
1-1
highlights the bridges connecting the mainland and the two islands
with oval markers.
Figure 1-1.
The Seven Bridges of Königsberg
Other conditions of the problem were that the bridges may not be crossed more than once and each bridge must
be crossed completely. Euler's subsequent treatise on the problem was written in 1736 and later published in 1741.
Euler proved that the problem could not be solved but, more importantly, noted that the most relevant aspect of the
problem is the order in which the bridges were crossed. In creating this singular, fundamental approach, Euler could
examine the problem in abstract terms. His more focused methodology considered only the mainland, the islands,
and the bridges that connected them.
1
