Graph theory
Networks of points and links have properties that set the best routes and connections.
Mathematics and information · Mathematics · No. 118
- Medieval and early modern
- Science
Euler's solution to a puzzle about seven bridges never mentioned graphs, yet it is widely regarded as graph theory's earliest paper.
Chart: Illustration: Graph theory
Where it comes from
Chart: Map of where it comes from
A puzzle asked whether a walk could cross each of the seven bridges of Königsberg once and only once. Euler presented his answer on 26 August 1735, and it was printed in 1741.
Three things to know
- Euler showed in 1735 that the seven Königsberg bridges cannot all be crossed once and only once.
- Euler's solution made no mention of graphs; graphs of this kind first appeared in the second half of the nineteenth century.
- The four colour problem, posed by Francis Guthrie in 1852, was proved by Appel and Haken in 1976 in the first proof that made essential use of computers.
The journey
- 1 PuzzleCan one walk over each of Königsberg's seven bridges once?
- 2 SolutionEuler presents the answer, 1735: it cannot be done
- 3 GraphsGraphs of this kind appear in the second half of the 19th century
- 4 AlgorithmsDijkstra's note on two graph problems, 1959
- 5 Use todayInternet routing, web search, maps and social networks