Euler's Eyes
2026-10-19
Graphs and maps: the drawing in which only connections matter
The city of Königsberg, in Prussia, was cut through by the river Pregel, which formed two islands, and seven bridges joined the four parts of the city. The inhabitants wondered whether it was possible to take a walk crossing each bridge exactly once. In 1736 Euler proved that it was not. The History book tells the proof in the chapter on the bridges of Königsberg. What matters here is what Euler did with the drawing.
Throwing the map away
A map of the city shows streets, houses, distances, the width of the river, the shape of the islands. Euler realised that none of this mattered for the question. All that mattered was which parts of the city are joined by which bridges. Each part becomes a point; each bridge, a line between two points. The result is what is now called a graph: four points and seven lines.
In this drawing, size, distance and shape no longer mean anything. You can stretch a line, move a point, bend everything: the graph stays the same, as long as the connections do not change. In Peirce’s language, the graph is an icon of a very special kind: it resembles the city only in its connections. It is an icon that chose, rigorously, what to copy.
And it was this impoverished drawing that made the answer visible. On a walk, every time you enter a point by one bridge, you leave by another; so every point in the middle of the route must have an even number of lines. In Königsberg the four points had $5$, $3$, $3$ and $3$ lines: all odd. The walk was impossible.
The map that stopped being a map
In 1931 a technical draughtsman on the London Underground, Harry Beck, proposed a new map. The old maps followed geography: the lines tangled in the centre and spread out in the suburbs, and nobody could read them. Beck realised that the passenger does not need to know where a station is, but in what order the stations come and where to change. He drew only straight lines, horizontal, vertical and at $45°$, with stations at equal distances.
Beck’s map, published in 1933, is a graph, not a map. It completely distorts geography, and that is exactly why it works. Almost every metro in the world, including those of São Paulo, Tokyo and Shanghai, has adopted the same principle. The price is that tourists sometimes take the underground to a station five minutes’ walk away, because on the diagram it looked far.
The same graph, different drawings
Since only the connections matter, the same graph can have very different drawings. A square with both diagonals and a triangular pyramid seen from above are the same graph: four points, all joined to each other. Deciding whether two drawings represent the same graph is a surprisingly hard problem for large drawings, and it has a name: the graph isomorphism problem.
Sometimes the drawing does matter. A graph is planar when it can be drawn with no line crossing another. This decides, for example, whether a printed circuit can be made on a single layer.
Exercise: an eighth bridge
If the inhabitants built an eighth bridge joining the two banks of the river, would the walk become possible?
The banks had $3$ lines each; with the new bridge, they have $4$. The degrees become $5$, $4$, $4$ and $3$: only two odd points. A walk crossing each bridge once now exists, starting at one odd point and ending at the other.
Exercise: why K₃,₃ is not planar
Use Euler’s formula for planar drawings, $V-E+F=2$ (vertices minus edges plus faces), to prove that $K_{3,3}$ is not planar.
$K_{3,3}$ has $V=6$ and $E=9$. If it were planar, it would have $F=2-6+9=5$ faces. In $K_{3,3}$ there are no triangles (each connection goes from a house to a utility), so each face has at least $4$ edges. Since each edge borders at most $2$ faces, $4F\leq2E$, that is, $20\leq18$, which is false. So there is no drawing without crossings.
Chapter index · ← Argand’s plane: the imaginary number that found a place · Proofs without words →