Appearance
8.6 — Graph Theory
The city of Königsberg sat on both banks of a river with two islands, connected by seven bridges. A local puzzle asked whether you could walk a route crossing every bridge exactly once.
Nobody could do it, and nobody could show it was impossible. In 1736 Leonhard Euler solved it, and in solving it he threw away almost everything about the problem.
The distances did not matter. The shapes of the islands did not matter. The lengths of the bridges did not matter. All that mattered was which land masses connected to which, and how many times. Euler reduced the map to four dots and seven lines, and a question about geography became a question about a structure that had no name yet.
His argument. Any time you enter a land mass you must also leave it, using two different bridges. So except for your start and finish, every land mass needs an even number of bridges. Königsberg's four land masses had 5, 3, 3 and 3 bridges — all odd. With more than two odd-degree points, no such walk exists.
Not "nobody has found one" — cannot exist. That paper founded graph theory and, arguably, topology.
1. The definitions
A graph G = (V,E) is a set of vertices (nodes) and a set of edges (connections between pairs).
The vocabulary:
Directed or undirected. Edges with a direction (a one-way street, "follows" on social media) or without (a handshake, a road that runs both ways).
Weighted or unweighted. Edges carrying a number — distance, cost, capacity, travel time.
Degree — how many edges touch a vertex. In a directed graph, in-degree and out-degree separately.
Path — a sequence of vertices connected by edges. Cycle — a path returning to its start.
Connected — every vertex is reachable from every other. If not, it splits into components.
Tree — a connected graph with no cycles. It has exactly n-1 edges for n vertices, and there is exactly one path between any two vertices. Trees are graphs with all the redundancy removed.
The handshake lemma. The degrees of all vertices sum to twice the number of edges, because every edge contributes to exactly two vertices. A consequence: the number of odd-degree vertices is always even. In any group of people, the number who have shaken hands an odd number of times is even.
2. Storing a graph
Adjacency matrix — an n\times n grid where entry (i,j) is 1 if there is an edge. Uses n^2 space, tells you instantly whether two vertices are joined, and is wasteful for sparse graphs.
It also has a lovely property from Chapter 4.2: the (i,j) entry of A^k counts the paths of exactly k steps from i to j. Matrix multiplication is doing path counting, and that observation connects graph theory to linear algebra permanently.
Adjacency list — for each vertex, a list of its neighbours. Uses space proportional to the number of edges, which is far better for the sparse graphs that occur in practice. Almost every real graph is sparse — a road network, a social network, a web link graph — so this is the standard choice. Volume I, 4.7 covers the implementation.
3. Traversal
Breadth-first search explores level by level using a queue: all neighbours, then all their neighbours. In an unweighted graph it finds the shortest path, because it reaches every vertex by the fewest possible steps.
Depth-first search goes as deep as possible before backtracking, using a stack or recursion. It is the natural fit for detecting cycles, finding connected components, and topological sorting.
Dijkstra's algorithm finds the shortest path when edges have weights. It repeatedly takes the nearest unvisited vertex and relaxes its neighbours' distances, using a priority queue. It fails with negative edge weights, because it commits to a vertex as soon as it is reached and a negative edge could improve it later; Bellman-Ford handles that case more slowly.
A* adds a heuristic estimate of the remaining distance, so it explores towards the goal rather than in all directions. With straight-line distance as the heuristic it is dramatically faster on maps, and it is what actually runs when your phone plans a route.
Volume I, 4.7 develops all of these properly with code.
4. Famous problems
Eulerian path — cross every edge once. Euler's condition: a connected graph has one exactly when it has zero or two odd-degree vertices. Checkable in linear time.
Hamiltonian path — visit every vertex once. Superficially similar, and NP-complete — no efficient general algorithm is known. This pair is the standard demonstration that a tiny change in a problem statement can move it from trivial to intractable. Volume I, 1.7 covers complexity classes.
The travelling salesman problem — the shortest route visiting every city and returning. NP-hard, and among the most studied problems in computing because it is the shape of every delivery, drilling and scheduling problem. Exact solutions are feasible for tens of thousands of cities with enormous effort; in practice, heuristics that get within a few percent of optimal in seconds are what actually run.
Graph colouring — assign colours so adjacent vertices differ. The four colour theorem of Chapter 3.6 says four suffice for any map. Deciding whether three colours suffice for a general graph is NP-complete.
Its practical form is scheduling: exams that share students cannot be at the same time, so make each exam a vertex, join exams with common students, and the colours are time slots. Same for allocating radio frequencies to transmitters, and for assigning variables to processor registers in a compiler — Volume I, 3.1 mentions register allocation, and it is graph colouring.
Minimum spanning tree — connect all vertices with the least total edge weight. Kruskal's and Prim's algorithms both solve it efficiently, and it is what you want when laying cable, pipe or road to connect a set of locations at minimum cost.
Maximum flow — the most that can be pushed through a network with capacity limits. The max-flow min-cut theorem says the maximum flow exactly equals the capacity of the cheapest set of edges whose removal disconnects source from sink. That equality is one of the elegant results in the subject, and it turns network capacity questions into bottleneck-finding questions.
5. Networks in the real world
Graph theory changed character in the late 1990s when people started measuring real networks and found they do not look like random graphs.
Small-world networks. Stanley Milgram's 1967 experiment asked people in Nebraska to forward a letter towards a target in Boston, passing it only to someone they knew personally. The chains that completed averaged about six steps — the origin of "six degrees of separation".
The mechanism was explained by Watts and Strogatz in 1998: take a network where everyone knows their neighbours, then rewire a small fraction of connections at random. Those few long-range links collapse the distance across the whole network while local clustering is barely affected. A handful of people with distant contacts is enough.
A 2011 study of Facebook's 721 million users found an average separation of 4.74. Adding the internet shortened it.
Scale-free networks. In many real networks the degree distribution follows a power law (Chapter 7.5): most vertices have few connections and a few hubs have enormous numbers.
Barabási and Albert explained it in 1999 with preferential attachment: new nodes prefer to connect to already-well-connected ones. Popularity compounds. The rich get richer, and the result is a hub-dominated structure rather than an even one.
And this has a sharp practical consequence about robustness. Scale-free networks are extremely resistant to random failure — remove random nodes and you almost always remove a low-degree one, and the network barely notices. They are extremely vulnerable to targeted attack — remove the hubs and it shatters.
The same fact, in three different fields. The internet survives random router failures and would be badly damaged by attacks on major exchanges. An ecosystem survives losing rare species and collapses when a keystone species goes. A disease spreads slowly if random people are vaccinated and is stopped efficiently if the highly-connected people are — which is the argument for targeted rather than uniform vaccination strategies.
PageRank, from Chapter 4.5, is the dominant eigenvector of the web's link graph, and it is graph theory and linear algebra doing one job.
6. Planarity and drawing
A graph is planar if it can be drawn without edges crossing.
Kuratowski's theorem gives a complete characterisation: a graph is planar exactly when it does not contain (in a precise sense) either K_5 — five vertices all joined to each other — or K_{3,3} — three vertices each joined to three others.
That second one is the "three utilities" puzzle: connect three houses to gas, water and electricity without any pipes crossing. It is impossible, and now you know it is a theorem rather than a failure of ingenuity.
Euler's formula for planar graphs, V - E + F = 2, is Chapter 3.6's polyhedron formula, because a convex solid's surface can be flattened into a planar graph.
Where planarity matters: circuit board layout, where a non-planar circuit needs a second layer and a via to cross; and graph drawing software, where minimising crossings is what makes a diagram readable.
Every formula above, built from scratch
None of the results in this chapter are worth memorising, because each one can be rebuilt in under a minute from something simpler. What follows is that rebuilding, one result at a time, so the formula and the reason for it sit on the same page as the explanation that needed them.
Graph theory
G = (V,E), \qquad n = |V|, \quad m = |E|
The handshake lemma
\sum_{v\in V}\deg(v) = 2m
Where it comes from. Each edge has two ends, and each end contributes 1 to the degree of the vertex it touches. So adding up all the degrees counts every edge exactly twice.
The immediate consequence: the number of vertices with odd degree is always even. At any party, the number of people who have shaken hands an odd number of times is even.
\text{Maximum edges in a simple graph} = \binom n2 = \frac{n(n-1)}{2}
Trees
A tree is a connected graph with no cycles.
m = n-1
Why. Start with one vertex and no edges. Each new vertex must be joined by exactly one edge — more would create a cycle, fewer would disconnect it. So after n vertices there are n-1 edges.
\text{A tree has exactly one path between any two vertices}
\text{Labelled trees on } n \text{ vertices}: n^{n-2} \qquad \text{(Cayley's formula)}
Euler's formula for planar graphs
V - E + F = 2
Read it. For any graph drawn on a plane with no crossings, vertices minus edges plus faces (counting the outside as one face) is always 2.
Why it holds — by peeling the graph apart. Start with a spanning tree, which has V vertices, V-1 edges and 1 face, giving V-(V-1)+1 = 2 ✓. Now add the remaining edges one at a time. Each added edge closes exactly one new cycle, so it raises E by 1 and F by 1, and the alternating sum is unchanged. Since the quantity starts at 2 and never moves, it is always 2.
The consequence that limits everything planar. In a simple planar graph with n\ge3:
m \le 3n-6
so a planar graph is sparse. This is why K_5 (five vertices all joined) cannot be drawn without crossings: it would need m = 10 edges but 3(5)-6 = 9. It is also why the four-colour theorem is about planar maps and not about arbitrary graphs.
Paths and circuits
| Question | Condition |
|---|---|
| Euler circuit (every edge once, return to start) | connected, all degrees even |
| Euler path (every edge once) | connected, exactly 0 or 2 odd vertices |
| Hamilton path (every vertex once) | no simple test — NP-complete |
Why the Euler condition is what it is. Every time the walk enters a vertex it must leave again, using two edges. So each vertex needs an even count — except the start and end of an open path, which are entered or left one extra time. This is exactly Euler's 1736 answer to the Königsberg bridges, told in 11.1: all four landmasses had odd degree, so no route existed.
The gap between Euler and Hamilton is one of the great surprises of the subject. Edges have a simple local test; vertices have none, and deciding a Hamilton path is among the hardest problems we know.
Colouring
\chi(G) = \text{fewest colours so no two joined vertices match}
\chi(G)\le\Delta(G)+1, \qquad \chi(\text{planar})\le4, \qquad \chi(\text{bipartite}) = 2
The four-colour theorem was proved in 1976 with computer assistance, and it was the first major theorem whose proof no human could check by hand.
Adjacency matrices
\left(A^k\right)_{ij} = \text{the number of walks of length } k \text{ from } i \text{ to } j
Why. (A^2)_{ij} = \sum_k A_{ik}A_{kj}, and each term is 1 exactly when there is an edge i\to k and an edge k\to j — that is, one two-step walk. Summing counts them all. Induction extends it to any k.
The shortest-path algorithms.
| Algorithm | Handles | Cost |
|---|---|---|
| Breadth-first search | unweighted | O(n+m) |
| Dijkstra | non-negative weights | O(m\log n) |
| Bellman–Ford | negative weights | O(nm) |
| Floyd–Warshall | all pairs | O(n^3) |
7. Where this shows up in your life
Every route your phone plans. A* on a weighted graph.
Every social network feature. Mutual friends, suggested connections, community detection.
Every dependency resolution. Package managers, build systems, spreadsheet recalculation order — topological sort on a directed acyclic graph, and a cycle is a circular dependency error.
Every network routing decision. Internet routing protocols are shortest-path algorithms on the graph of routers. Volume I, 5.3.
Every compiler. The control flow graph, the call graph, and register allocation by graph colouring.
Every recommendation. Users and items form a bipartite graph, and recommendations are paths through it.
Every epidemic model beyond the simplest. Contact networks are graphs, and the hub structure of Section 5 is why superspreader events matter so much more than the average case suggests.
Part 8 is finished. The next Part returns to the continuous world with the idea Fourier fought for: that any signal, however complicated, is a sum of pure tones.
More places these turn up
De Morgan's laws are what a database rewrites your search filter into, and what a compiler applies to your if statements. Induction is the reason a recursive function can be trusted. Euler's circuit condition schedules a bin lorry and a postal round. Graph colouring assigns radio frequencies so neighbouring masts do not clash, and allocates exam timetables so no student sits two at once. The handshake lemma is a one-line sanity check on any network dataset. And Binet's formula, or rather the golden ratio inside it, is why a sunflower's seeds are packed the way they are.
Next: 8.P — Worked Problems works through counting arguments, induction proofs, a recurrence solved in full, and graph problems, step by step.