Concept
The mathematics of connection — born from a Sunday walk puzzle, now the language of social networks and the brain.
Understand it in one breath
Abstract objects as vertices and relations as edges. Euler's 1736 paper on the Königsberg bridges was an early milestone because it kept only connectivity to decide whether a walk was possible. Social, communication, transport, and biological networks can be modeled as graphs, while real flows, directions, capacities, and time require additional structure.
At a glance
A | B | C | D | |
|---|---|---|---|---|
A | 0 | 1 | 1 | 0 |
B | 1 | 0 | 1 | 1 |
C | 1 | 1 | 0 | 1 |
D | 0 | 1 | 1 | 0 |
Adjacency matrix — A↔B, A↔C, B↔C, B↔D, C↔D. Each vertex’s degree equals its row sum (A:2, B:3, C:3, D:2). Total 10 = 5 edges × 2 ✓ by the Handshaking Lemma.
Key formula
Key moments
Euler — the bridges of Königsberg
Euler proved that no walk could cross each of Königsberg’s seven bridges exactly once, turning a city puzzle into the birth of graph theory.
The four-color conjecture
Could every planar map be colored with only four colors so that neighboring regions differ? The 1852 question was finally proved with computer assistance in 1976.
Dijkstra — the shortest-path algorithm
Edsger Dijkstra devised an efficient method for finding shortest paths in a weighted graph. It became a foundation for routing, navigation, and network optimization.
Brin and Page — PageRank
Google’s founders modeled web pages as nodes and hyperlinks as edges, then used the resulting graph to estimate importance and transform web search.
Modern applications
Google PageRank, social-network recommendations, GPS routing, computer networks, graph neural networks, and contact tracing — graphs appear wherever things connect.
Beyond MathVoyage
Loading…