Discrete mathematics · 03 · Dots, lines, and the modern world · 8 min
Graphs & networks
In 1736, Euler settled a stroll-planning puzzle about seven bridges — and accidentally founded the mathematics of networks. A graph is just dots and connections, and it turns out half the modern world is one.
Build the intuition
Abstraction is the superpower
Königsberg's bridges, a subway map, and a friend network share a skeleton: things (vertices) and connections (edges). Strip away geography and only connectivity remains — which is why one theory simultaneously serves city planners, epidemiologists, and chip designers.
Degrees decide the bridge puzzle
A vertex's degree is its connection count. Euler noticed: to walk every edge exactly once, each pass-through region needs paired entries and exits — even degree — except possibly the two endpoints. Königsberg had four odd-degree regions: impossible, proven without trying a single route. Counting beat exhaustive search; that idea became computer science.
Paths, distance, and six degrees
Distance in a graph is the fewest edges between two vertices. Social networks are shockingly shallow — “six degrees of separation” — because connections multiply outward like a branching tree. Shortest-path algorithms (Dijkstra's, A*) exploit graph distance to route everything from packets to pizzas.
See it move
Euler's original puzzle, live: toggle bridges and watch the odd-degree count decide walkability — no route-trying required.
A worked example
Make Königsberg walkable
The historical graph has degrees 5, 3, 3, 3 — four odd vertices. Euler's rule allows at most two.
Remove one bridge between two odd regions: both their degrees become even. Two odd vertices remain.
Now an every-bridge walk exists, starting and ending at the two odd regions. One edge changed the global answer — networks are sensitive like that.
Out in the world
How your map app routes you
Intersections are vertices; road segments are weighted edges (travel time). Your route is a shortest-path computation over a graph with millions of nodes, re-solved live as traffic reweights the edges. Graph theory, billions of times a day.
Common confusion, cleared
“These “graphs” are the charts with x and y axes.”
Same word, different species: here a graph is a network of dots and connections. (Mathematicians apologize for the collision.)
“Network problems are solved by trying possibilities.”
Euler's whole point: structure (like degree counts) answers questions that brute force can't reach. Modern graph algorithms are clever structure-exploiting, not exhaustive search.
Recap
- Graphs = vertices + edges: pure connectivity, geography removed.
- Degree counting solved the bridges and founded the field.
- Shortest paths and degrees power routing, social, and infrastructure tech.