Graph theory: Discovery
The story
How the idea was found and came to be accepted
The city of Königsberg had seven bridges, and people asked whether one could set out from one part of the city and cross each bridge once and once only [2][4]. The best mathematicians of the day, including all of the Bernoullis, could not say whether it was possible [4]. Euler saw that everything was irrelevant except the seven bridges and the areas they connect [4]. On 26 August 1735 he presented his solution to his colleagues [1][2]: such a journey is impossible [2]. His paper is dated 1736 but was not printed until 1741 [1]. It made no mention of graphs, which first appeared in the second half of the nineteenth century, yet it is widely regarded as the earliest contribution to graph theory [1]. The first textbook followed in 1936 [5]. Francis Guthrie posed the four colour problem in 1852, and Appel and Haken proved it with computers in 1976 [6].
as of 2026-11-12
People
The people behind it, their years and what each contributed
| Name | Years | Contribution |
|---|---|---|
| Leonhard Euler | 1707 to 1783 | Solved the Königsberg bridge problem in 1735, which is regarded as the start of graph theory [1][4] |
| Francis Guthrie | active in 1852 | Posed the four colour problem in 1852 [6] |
as of 2026-11-12
Milestones
The key moments, year by year
| Year | Event |
|---|---|
| 1735 | Euler presents his solution to the Königsberg bridge problem on 26 August [1][2] |
| 1741 | Euler's paper, dated 1736, is finally printed [1] |
| 1852 | Francis Guthrie poses the four colour problem [6] |
| 1936 | The first textbook on graph theory is published [5] |
| 1959 | Dijkstra publishes 'A Note on Two Problems in Connexion with Graphs' in Numerische Mathematik [7] |
| 1964 | Baran's RAND memorandum studies distributed communications networks of nodes and links [10] |
| 1976 | Appel and Haken prove the four colour theorem, the first proof to make essential use of computers [6] |
| 1998 | OSPF Version 2 is published as RFC 2328: each router builds a tree of shortest paths over a directed graph of the network [8] |
as of 2026-11-12
Sources
- The Truth about Konigsberg The College Mathematics Journal 35(3), 198 to 207 (Brian Hopkins and Robin J. Wilson), 2004
- Leonard Euler's Solution to the Konigsberg Bridge Problem (Teo Paoletti) Mathematical Association of America (Convergence)
- Leonhard Euler - The Linda Hall Linda Hall Library
- Motivation and history AMSI and the University of Melbourne, with the Victorian Curriculum and Assessment Authority, 2015
- Celebrating the Four Color Theorem College of Liberal Arts & Sciences, University of Illinois
- A Note on Two Problems in Connexion with Graphs Numerische Mathematik 1, 269-271 (E. W. Dijkstra), via EuDML, 1959
- OSPF Version 2 (RFC 2328) Internet Engineering Task Force (J. Moy), 1998
- On Distributed Communications: I. Introduction to Distributed Communications Networks RAND Corporation (Paul Baran), 1964