Graphs: degrees, paths, trees, Euler and Hamilton

The Prussian city of Königsberg sat on both banks of the river Pregel and on two islands, joined by seven bridges. Could a walker cross every bridge exactly once? In the mid-1730s Leonhard Euler, working at the St Petersburg Academy, showed that it could not, and his paper, published in 1741, explained why for any arrangement of land and bridges.

His key move was to throw the map away. Only which land masses each bridge joins mattered, not distances or shapes. That abstraction, points and the lines between them, is a graph, and it now models routers, road maps, web links, task dependencies and fraud rings.