Graph theory

A graph is the barest possible skeleton of a situation: dots for the things, lines for which things are joined. Königsberg sat on the river Pregel as four landmasses — two islands and two banks — tied together by seven bridges. In his 1736 paper *Solutio problematis ad geometriam situs pertinentis*, Euler threw away the city and kept the skeleton: four points, seven links, and one question about the pattern. Could you trace a walk that used every link exactly once? He proved you could not, and in proving it invented the idea that a shape can be studied purely as a web of connections.

It was the first theorem about pattern rather than magnitude. Every earlier geometry measured — lengths, angles, areas. Euler showed that a whole class of real questions depends on none of that, only on what touches what. This is the seed of two subjects at once: graph theory, the mathematics of networks, and topology, the "geometry of position" that studies properties surviving any stretch or bend. It also modeled a way of thinking: rather than try the routes one by one, Euler found an *invariant* — the parity of each landmass's bridge count — that decided the matter in a single stroke.

Everything defined by connection rather than distance is now a graph: road and rail networks, electrical circuits, the routing tables of the internet, molecules (Cayley and Sylvester drew chemical structures as graphs in the 1870s), family trees, and the link structure of the web. Graph theory gave us shortest-path and network-flow algorithms, the four-color theorem, the modeling of epidemics spreading across contact networks, and the eigenvector-of-a-graph idea behind Google's original PageRank. Whenever a problem reduces to "what is connected to what," it is Euler's Königsberg abstraction at work.