The Genesis of Graphs: From Euler’s Bridges to Modern Network Science

On a mild late summer afternoon in 1736, the citizens of Königsberg, the capital of East Prussia, gathered along the banks of the Pregel River to debate a deceptively simple puzzle that had become the talk of the city’s cafes and market squares. The river split the city into four distinct landmasses: the north and south banks, and two large islands connected by a series of seven bridges. The challenge was to find a walking route that crossed each of the seven bridges exactly once and returned to the starting point, without retracing any step. For months, locals had tried and failed, scribbling routes on scraps of paper, only to find themselves either stuck on an island with no un-crossed bridges left, or forced to backtrack across a span they had already traversed. The problem seemed trivial enough for a leisurely afternoon’s diversion, but no one could crack it—until a letter arrived from the Swiss mathematician Leonhard Euler, who had been asked to weigh in by a colleague in the city’s intellectual circles.

Euler’s solution was as elegant as it was revolutionary. Rather than getting bogged down in the geography of the city, he abstracted the problem to its pure relational core: the four landmasses became four vertices (or nodes), and the seven bridges became seven edges connecting those vertices. He then observed a simple but profound rule: for a closed walk that traverses every edge exactly once (what we now call an Eulerian circuit) to exist, every vertex in the graph must have an even degree (the number of edges connected to it). In Königsberg’s case, all four vertices had an odd degree of three, making such a route mathematically impossible. Euler published his proof in a 1736 paper titled *Solutio problematis ad geometriam situs pertinentis* (Solution of a Problem Relating to the Geometry of Position), a work now universally recognized as the founding document of graph theory. The term “geometry of position” was deliberate: Euler understood he was not dealing with the traditional geometry of distances, angles, and areas, but with a new kind of geometry focused solely on the relationships between discrete objects. What started as a solution to a city’s weekend散步 puzzle would go on to become the foundational language for modeling every system where relationships matter more than absolute positions.

For the next century, graph theory remained a niche branch of combinatorial mathematics, studied mostly by pure mathematicians interested in abstract puzzles. But the Industrial Revolution brought with it a surge of real-world problems that could not be solved with traditional calculus or algebra: how to lay out railway lines to minimize construction cost while maximizing connectivity, how to route telegraph signals across a network to avoid congestion, how to design water and sewage systems that could serve growing urban populations. Engineers and mathematicians quickly realized that all these systems could be modeled as graphs: train stations as vertices, rail lines as edges; telegraph offices as vertices, communication lines as edges; water treatment plants as vertices, pipes as edges. This shift from abstract puzzle to practical tool was cemented in 1857 by the British mathematician Arthur Cayley, who used graph theory to count the number of distinct structural isomers of alkanes, a class of organic hydrocarbons. By modeling alkane molecules as trees (connected graphs with no cycles), with vertices representing carbon atoms and edges representing chemical bonds, Cayley derived a formula for the number of possible alkane structures that matched experimental observations from chemists exactly. It was one of the first times graph theory had solved a tangible problem in the physical sciences, and it opened the door for the field’s expansion into chemistry, operations research, and eventually computer science.

The 19th century also saw the emergence of some of graph theory’s most enduring hard problems, problems that would drive research for centuries to come. In 1838, the Irish mathematician William Rowan Hamilton invented a puzzle called the Icosian Game, which asked players to find a route that visited each of 20 cities (represented as vertices on a dodecahedron) exactly once and returned to the starting point. This “traveling salesman problem” (TSP) would become one of the most famous problems in combinatorial optimization, with applications ranging from logistics routing to microchip design that are still being explored today. A decade later, in 1852, a British university student named Francis Guthrie noticed that he could color any map of England’s counties with only four colors, such that no two adjacent counties shared the same color. When he posed the problem to his professor, the mathematician Augustus De Morgan, it sparked a century-long chase that would not be resolved until 1976, when Kenneth Appel and Wolfgang Haken used a computer to prove the Four Color Theorem, the first major mathematical theorem ever proven with machine assistance. These problems were not just mathematical curiosities: they revealed that graphs could capture the essence of spatial, combinatorial, and structural constraints in ways no other mathematical framework could.

By the early 20th century, graph theory had cemented its place as a core tool in engineering and mathematics, but its true potential as a universal language for relational systems was still unrealized. That potential would be unlocked over the course of the 20th century, as researchers across sociology, biology, physics, and computer science began to recognize that the most interesting systems in the world were not collections of independent objects, but webs of interdependent relationships. The first major breakthrough came in the 1930s, from a field as far removed from pure mathematics as one could imagine: sociology. The Austrian-American psychiatrist Jacob Moreno, working with marginalized youth in New York City, developed a method called sociometry to map social relationships within groups. For the first time, Moreno represented people as vertices and their social interactions (friendships, collaborations, communication) as edges, drawing what he called sociograms to visualize the hidden structure of social groups. In a 1934 study of a New York elementary school classroom, Moreno’s sociograms revealed clear patterns that were invisible to traditional statistical analysis: a small group of popular students sat at the center of the web with dozens of connections, while a handful of isolated students had no connections at all, a finding that directly explained patterns of social exclusion and group cohesion that teachers had observed but could not quantify. Moreno’s work was revolutionary: it was the first time graphs were used not just to model physical infrastructure, but to model the structure of human society itself.

The mid-20th century saw graph theory spread rapidly across the life sciences and information theory. In 1953, when James Watson and Francis Crick discovered the double helix structure of DNA, biologists immediately began using graphs to model molecular structures: atoms as vertices, chemical bonds as edges, to map the shape of proteins and the interactions between molecules. By the 1960s, biologists were using graphs to model entire biological systems: protein-protein interaction networks, metabolic pathways, gene regulatory networks, all represented as large, complex graphs that could be analyzed to understand the fundamental mechanisms of life. In information science, Claude Shannon’s 1948 foundational paper *A Mathematical Theory of Communication* used graphs to model communication networks, deriving the maximum capacity of information channels and laying the groundwork for modern networking. A decade later, in 1959, the Dutch computer scientist Edsger Dijkstra published his famous shortest path algorithm, a graph-based method for finding the fastest route between two poin