Sometime in the 1730s, the citizens of the Prussian city of Königsberg (now Kaliningrad) had a puzzle that bothered them. The city sat on the Pregel River, with two islands and four landmasses connected by seven bridges. The question: could you walk through the city, crossing each of the seven bridges exactly once, ending up where you started?
The puzzle had circulated for years without anyone proving an answer either way. In 1736, the 29-year-old Leonhard Euler decided to settle it. His response, published as Solutio problematis ad geometriam situs pertinentis, did far more than answer the bridge question. It launched a new branch of mathematics — graph theory — that has turned out to describe the structure of the internet, social networks, biological systems, transportation grids, and the brain.
Euler’s answer to the original question, by the way, was no: such a walk is impossible. But the way he proved it changed mathematics. He didn’t draw a map of Königsberg and try to trace paths. He abstracted. He replaced each landmass with a dot and each bridge with a line, throwing away geography, distances, and shape. What remained was a structural diagram — a graph — that captured everything relevant about the problem.
This article is about what graphs are, what they let you do, and where they appear today.
The basic definitions
A graph consists of:
- A set of vertices (or “nodes”) .
- A set of edges (or “links”) , each of which connects two vertices.
That’s the entire formal definition. Concrete examples:
- A city’s road network: intersections are vertices, roads are edges.
- A friendship network: people are vertices, friendships are edges.
- A computer network: machines are vertices, connections are edges.
- A molecule: atoms are vertices, chemical bonds are edges.
Graphs come in many flavors:
- Directed vs. undirected: edges have a direction or not.
- Weighted vs. unweighted: edges carry numerical weights (distances, costs).
- Simple vs. multigraph: multiple edges between the same vertices allowed or not.
- Connected vs. disconnected: all vertices reachable from any other or not.
The degree of a vertex is the number of edges incident to it. In a friendship network, degree is your number of friends. The structure of the degree distribution turns out to encode a lot of important information.
Euler’s bridge solution
Euler proved a clean general theorem: a connected graph has an “Eulerian circuit” (a path that uses every edge exactly once and returns to the start) if and only if every vertex has even degree.
For Königsberg, three of the four landmasses have an odd number of bridge-connections. So no Eulerian circuit exists. The walk the citizens wanted is mathematically impossible.
The theorem generalizes a question with no obvious math content into a clean structural statement. This was the birth of graph theory: replace concrete situations with their abstract structure, then prove theorems about the abstract structure.
Famous problems and theorems
Graph theory has developed an enormous catalog of problems and theorems over the past 290 years. Highlights:
Hamiltonian paths (1857): a path that visits every vertex exactly once (different from Eulerian, which uses every edge). Determining whether a graph has a Hamiltonian path is NP-complete — one of the canonical hard problems of computer science. (See P vs NP for context.)
The Four Color Theorem (1976): every map can be colored with at most four colors such that no two adjacent regions share a color. This is a graph-theoretic statement about planar graphs. The proof was the first major theorem proven by computer-assisted enumeration. (See our Four-Color piece.)
Minimum spanning trees: among all subgraphs that connect every vertex with no cycles, find the one with minimum total edge weight. Solved in polynomial time by Kruskal’s and Prim’s algorithms. Used in network design, clustering, and image segmentation.
Shortest paths: Dijkstra’s algorithm (1956) finds the shortest path from one vertex to all others in time. Used in GPS navigation, internet routing, and many other applications.
Maximum flow / minimum cut: how much “stuff” can you push through a network from a source to a sink, given edge capacities? The Ford-Fulkerson algorithm (1956) solves this. Applications: traffic routing, supply-chain optimization, image segmentation, baseball-elimination problems.
Graph coloring: color vertices so no two adjacent vertices have the same color. The chromatic number — the minimum number of colors needed — is hard to compute in general but solvable by polynomial algorithms in special cases.
Matching problems: pair up vertices (e.g., applicants with jobs, kidneys with patients) according to compatibility. The Hungarian algorithm finds optimal weighted matchings in polynomial time.
Real-world networks
The most consequential modern development of graph theory is the study of real-world networks — graphs that arise from concrete data rather than constructed examples.
The 1990s and 2000s saw an explosion of work on these networks, driven by suddenly-available data:
Small-world networks: most pairs of nodes are connected by short paths, even in huge networks. The “six degrees of separation” experiments by Stanley Milgram (1967) and the Erdős number tradition in mathematics demonstrated this empirically. Watts and Strogatz formalized it in 1998: many real networks combine local clustering (your friends know each other) with occasional long-range links (you have one friend across the country) to produce small average path lengths.
Scale-free networks: degrees follow a power-law distribution. Most vertices have few connections; a few “hubs” have many. The internet, citation networks, and many social networks are scale-free. Albert-László Barabási and Réka Albert in 1999 proposed the “preferential attachment” mechanism — new nodes attach to popular ones — as a generative explanation.
Community structure: networks have communities — densely connected sub-networks loosely connected to other communities. Detecting communities is a major research area; algorithms include Newman-Girvan, modularity-maximization, and stochastic block models.
Robustness and vulnerability: how does a network behave when nodes or edges fail? Scale-free networks are surprisingly robust to random failures (most nodes have low degree, so removing a random one matters little) but fragile against targeted attacks on hubs. This has implications for everything from power grids to disease control.
These structural features show up across very different systems:
- The internet’s router-level topology.
- Social networks like Facebook, Twitter, Instagram.
- Citation networks of academic papers.
- Co-authorship networks of researchers.
- Protein-protein interaction networks in cells.
- Gene regulatory networks.
- Neural connection networks in brains.
- Air traffic networks between airports.
- Power grids.
- Trade networks between countries.
The same statistical patterns appear in all of them — short paths, scale-free degrees, community structure, robustness profiles. This convergence suggests that graph theory captures something fundamental about how complex systems organize themselves.
Algorithms on graphs
Modern computer science depends on efficient graph algorithms.
BFS/DFS (Breadth-First Search / Depth-First Search): traverse a graph systematically. Used for connectivity checks, cycle detection, topological sort, finding strongly connected components.
Dijkstra’s algorithm: shortest paths from one source. Used in GPS, internet routing protocols (OSPF), social network “degrees of separation” calculations.
Bellman-Ford: shortest paths with negative edges. Used in network routing where edge weights can be negative.
Floyd-Warshall: all-pairs shortest paths. Used in network analysis, transitive closure computation.
A* search: heuristic-guided shortest path. Used in robotics, video game AI pathfinding, route planning.
Network flow algorithms (Ford-Fulkerson, Edmonds-Karp, push-relabel): max-flow problems. Used in supply chain optimization, image segmentation, scheduling.
Random walk algorithms: PageRank is a random walk on the web’s link graph. Personalized recommendations on YouTube, Spotify, and Amazon use related random-walk methods.
Spectral methods: study eigenvalues of the graph’s Laplacian matrix. Used for clustering, partitioning, and embedding graphs into lower-dimensional spaces.
Graph neural networks: a recent (2010s+) class of neural networks designed to learn directly on graph-structured data. Used for drug discovery (molecules are graphs), social-network analysis, and many applications where structure matters.
The combinatorial nature of graph problems means that many are computationally hard (NP-hard or worse), but enough natural problems are polynomially solvable that graph algorithms run continuously throughout modern computing infrastructure.
Where graphs appear in mathematics
Beyond applications, graph theory connects to many parts of pure mathematics:
Algebraic graph theory: study of graphs via their adjacency matrices and Laplacian matrices. Eigenvalues encode structural properties. Connects to representation theory and number theory.
Topological graph theory: how graphs embed in surfaces. The classic distinction between planar and non-planar graphs is the entry point. The genus of a graph is a topological invariant.
Random graphs: graphs generated by random processes. The Erdős-Rényi model — independently include each possible edge with probability — has surprisingly rich theory. Random graphs underlie probabilistic methods in combinatorics.
Extremal graph theory: how large can a graph be while avoiding certain substructures? Turán’s theorem (1941) and Ramsey theory are central. Pál Erdős worked on these problems for decades.
Knot theory and graphs: knots are sometimes studied via their associated graphs. (See our knot theory piece.)
Combinatorial game theory: many games can be analyzed via graph-theoretic methods, with positions as vertices and moves as edges.
What graph theory teaches
The deepest lesson of graph theory is the power of structural abstraction. Whatever your concrete problem — bridge crossings, friendship networks, gene regulation, internet routing — if you can extract the structural skeleton (vertices and edges), you can apply 290 years of accumulated theory.
This is the same lesson that runs through abstract algebra (groups, vector spaces) and topology: you don’t have to solve every problem from scratch. You identify the structure, look up what’s known about that structure, and apply it.
Euler’s bridge solution showed how this works for the first time in mathematical history. The Königsberg problem looked geographic; Euler proved it was topological. The map of bridges and landmasses was a distraction; the underlying graph was the substance.
Today, graph theory is one of the most-applied areas of mathematics. Every social-network analysis tool, every routing algorithm, every recommendation system uses graph-theoretic methods. When you check Google Maps, browse LinkedIn, or watch YouTube, you’re touching graph algorithms running on real-world networks.
Three centuries after Euler decoded Königsberg, his abstraction is more relevant than ever. Networks of all kinds — physical, social, biological, virtual — surround us. The mathematics that describes them is, in a real sense, one of the most important inheritances of the Enlightenment.
A 29-year-old in 1736 looked at a puzzle about bridges and saw a new way of doing mathematics. That way of seeing is now everywhere.
Frequently asked
Why did Euler bother with the bridge problem?
It came to him as a recreational puzzle from the citizens of Königsberg, but Euler immediately realized something deeper. He stripped away the geographic details and represented the problem abstractly — vertices for landmasses, edges for bridges. This abstraction is the foundation of graph theory. The puzzle itself was minor; the method of abstraction was revolutionary.
What's the difference between a graph and a network?
Mathematicians use 'graph' for the abstract object: vertices and edges. 'Network' is more often used in applications, often with additional structure like edge weights, capacities, or directions. The two terms are interchangeable in practice, with 'graph' more common in math, 'network' more common in computer science and applied work.
Are social networks like Facebook real graphs?
Yes. Each person is a vertex; each friendship is an edge. Facebook's graph has billions of vertices and trillions of edges. Studying its structure — distance distributions, clustering, community structure — uses graph-theoretic tools. The same applies to LinkedIn, Twitter, citation networks, the World Wide Web, and the brain's neural connections.