Chapter I
Seven Bridges
The Prussian city of Königsberg was built on both banks of the Pregel river and on two islands, joined by seven bridges. Its citizens liked to ask whether a walk could cross every bridge exactly once. In 1735 Leonhard Euler showed that it could not, and, more importantly, why. The shapes of the islands and the lengths of the bridges were irrelevant. All that mattered was which land masses each bridge joined. Euler called this the "geometry of position", after a phrase of Leibniz. It is now counted as the first theorem of graph theory, and it has the same flavour as his polyhedron formula of 1750, which became part of algebraic topology.
Chapter II
Networks and Molecules
For a century, graphs turned up in unrelated places. In 1847 Gustav Kirchhoff, aged twenty-three, found that the equations of an electrical network are governed by its spanning trees. Arthur Cayley counted trees to count the possible molecules of a chemical formula, and James Joseph Sylvester borrowed the word "graph" from chemists' diagrams in 1878. Puzzles fed in too. Hamilton invented a game in 1857 that asked for a round trip through all twenty vertices of a dodecahedron.
In 1936 Dénes Kőnig, in Budapest, gathered the results into the first textbook, and graph theory became a subject. Hungary produced many of its leading figures over the next half-century.
Chapter III
Four Colours
The most famous problem started with a map of England. In 1852 Francis Guthrie noticed that four colours were enough to give every pair of neighbouring counties different colours, and asked if that was always true. The question passed through Augustus De Morgan to the mathematical world. In 1879 Alfred Kempe published a proof, and it was accepted for eleven years until Percy Heawood found the flaw. Heawood proved that five colours always suffice, and the gap between five and four stayed open for most of a century.
In 1976 Kenneth Appel and Wolfgang Haken closed it. They showed that every map must contain one of nearly two thousand configurations, each of which could be removed and recoloured. The checking took more than a thousand hours of computer time. Many mathematicians were uneasy about a proof no human could read in full. A shorter computer proof in 1997, and a formal verification in 2005, settled its truth. The question of what counts as a proof is discussed in metamathematics.
Chapter IV
A Closer Look: Counting Bridges
Draw Königsberg as a graph. The island Kneiphof is one vertex, the north bank, the south bank and the island of Lomse to the east are the other three, and each of the seven bridges is an edge. Count the edges at each vertex:
| Land mass | Bridges |
|---|---|
| Kneiphof island | 5 |
| North bank | 3 |
| South bank | 3 |
| Lomse island | 3 |
The total is , twice the seven bridges, because each bridge has two ends. That is true of every graph, and it has a consequence: the number of vertices with an odd count must be even.
Now imagine a walk that crosses every bridge once. Every time the walker passes through a land mass, they use two bridges, one in and one out. So a land mass that is neither the start nor the end of the walk must have an even number of bridges. Only the start and the end can be odd. Königsberg has four odd land masses, so no such walk exists, however it is planned.
Euler also saw the converse, proved in full by Carl Hierholzer in 1873: if a connected graph has zero or two odd vertices, such a walk exists. That makes the question easy to answer for any map, however large. Two of the bridges were destroyed in the Second World War and two more were later replaced by a highway. With the five bridges that now stand on the old sites in Kaliningrad, a walk crossing each once is possible.
Chapter V
Structure
After the four colour theorem the field turned to structure. Between 1983 and 2004 Neil Robertson and Paul Seymour proved, in twenty papers, that graphs are well ordered by the minor relation. Their methods explain how graphs that avoid a given pattern are built, and they have led to fast algorithms. Graphs now underlie combinatorial optimisation, the study of large networks and extremal combinatorics. Hadwiger's conjecture, a vast generalisation of the four colour theorem, is still open.