Part V: Graph Theory

"All problems in computer science can be solved by another level of indirection." — commonly attributed to David Wheeler

Open the app you use most and you are looking at a graph. Your contacts are people joined by who-knows-whom. A maps app is intersections joined by roads. The web is pages joined by links; your codebase is modules joined by imports; a build system is tasks joined by what-depends-on-what. The reason graphs deserve an entire part of this book is not that they are elegant — though they are — but that an astonishing share of the problems a working programmer is paid to solve turn out to be the same problem once you strip away the surface and look only at the dots and the lines. Routing, scheduling, matching, ranking, recommending, detecting fraud, allocating resources: learn graphs once, and you get a discount on all of them.

That is the bargain this part offers, and it is the payoff the earlier parts have been setting up. A graph is, almost exactly, a relation (Chapter 12) promoted from a side-view of how elements pair up into a first-class object with its own theorems and its own algorithms. The vertices are a set; the edges are a set of pairs; the whole apparatus of Chapter 8 — subsets, ordered and unordered pairs, cardinality — is the foundation underneath it. What is new here is motion. A relation just is; a graph is something you traverse, search, and optimize over. To do that well, you will lean on every analytical tool from Part II: the running times you will quote come straight from the Big-O machinery of Chapter 14, and the correctness arguments for trees rest on the structural induction of Chapter 7.

A warning and a promise. Graph theory is where the easy-versus-hard boundary of computer science first becomes visible to the naked eye. Two problems can look like near-twins — find a route that crosses every road exactly once versus every city exactly once — and yet one is solved in a heartbeat while the other has resisted fast solution for a century. Part V will not hide that boundary; it will walk you right up to it, because understanding which problems are tractable is as valuable as knowing how to solve the ones that are. By the end you will not only implement the classic algorithms — you will be able to defend them in a code review, which, as this book keeps insisting, is a different and harder thing than watching them pass a test.

What You Will Learn

Chapter 27 — Introduction to Graphs. The vocabulary chapter, and the place the social-network anchor of this book formally begins. You will define a graph as a pair $G=(V,E)$, name its parts without ambiguity (vertex, edge, degree, neighbor, path, cycle, connectedness), and learn to classify graphs as directed, weighted, bipartite, complete, or simple. You will prove your first graph theorem — the handshaking lemma, $\sum_{v} \deg(v) = 2\lvert E\rvert$ — and use its parity corollary to instantly reject impossible claims, and the Toolkit's graphs.py module is born here as a Graph class built from scratch.

Chapter 28 — Graph Representations, Traversal, and Search. How a graph actually lives in memory, and how to walk it. You will weigh the adjacency matrix against the adjacency list, implement breadth-first and depth-first search, and use them to test connectivity, detect cycles, and find components. The anchor pays off as BFS becomes "degrees of separation" in a social network, and you will re-derive the topological sort of Chapter 13 through DFS — the same result reached by a new road.

Chapter 29 — Weighted Graphs and Shortest Paths. When edges carry unequal costs, "fewest edges" and "cheapest" diverge, and BFS gives the wrong answer. You will implement Dijkstra's algorithm with a priority queue, reconstruct the path itself rather than just its length, and handle negative edges with Bellman–Ford. The deeper prize is a proof technique that recurs through the rest of the part: justifying a greedy algorithm by stating and maintaining a loop invariant, with a careful look at exactly where non-negativity is used.

Chapter 30 — Euler Paths, Hamilton Paths, and the TSP. This is the chapter where the easy/hard boundary becomes vivid. Starting from the eighteenth-century bridges of Königsberg, you will learn the clean theorem characterizing Euler paths (cross every edge once), contrast it with the stubbornly hard Hamilton path (visit every vertex once), and meet the Traveling Salesman Problem. You will get your first honest encounter with the word intractable and with heuristics as the rational response to it — a thread that Chapter 37's complexity theory will later make formal.

Chapter 31 — Trees. The most important special case of a graph, and the structure your data lives in. You will characterize trees by their defining properties (connected, acyclic, exactly $n-1$ edges), work with rooted and binary trees, traverse them in pre-, in-, and post-order, and apply them across CS — binary search trees, heaps, expression trees, tries. The structural induction you learned back in Chapter 7 finally pays its full dividend, and the chapter closes with Huffman coding, which reappears in Part VI.

Chapter 32 — Spanning Trees and Minimum Spanning Trees. Given a weighted graph, find the cheapest set of edges that keeps everything connected — the canonical question of network and infrastructure design. You will compute minimum spanning trees with both Kruskal's algorithm (backed by the union-find data structure) and Prim's, and then prove why these greedy strategies are guaranteed optimal, via the cut property. This is greedy correctness done rigorously, building directly on the spanning-tree idea from Chapter 28 and the shortest-path machinery of Chapter 29.

Chapter 33 — Graph Coloring and Planarity. How few colors suffice to paint a graph so that no two adjacent vertices clash? That single question models exam scheduling, register allocation in a compiler, and frequency assignment. You will work with the chromatic number $\chi(G)$, meet planar graphs and Euler's formula $v - e + f = 2$ (distinct from the Euler's theorem of number theory), survey the famous Four Color Theorem, and confront the limits of greedy coloring. The social-network anchor returns here as community detection and scheduling.

Chapter 34 — Network Flow and Matching. The capstone of the part, where the earlier algorithms converge. You will model flow networks, compute maximum flow with Ford–Fulkerson via augmenting paths, and meet the elegant max-flow min-cut theorem that ties a maximization to a minimization. As a striking application you will solve bipartite matching — assigning workers to jobs, students to projects — and see how problems that look nothing like "flow" dissolve into it once modeled correctly.

How This Part Fits

Part V stands squarely on the four parts before it. Its objects come from Part II — Structures: a graph is a relation (Chapter 12) drawn from sets (Chapter 8), and trees are the recursively defined objects of Chapter 7 made concrete. Its analysis is the Big-O language of Chapter 14 — every "this runs in $O(\lvert V\rvert + \lvert E\rvert)$" claim is cashed out in that machinery — and its proofs are the induction, contradiction, and case analysis drilled in Part I. The greedy-correctness arguments in Chapters 29 and 32 are some of the most satisfying proofs in the book precisely because you now have the tools to follow every step.

Looking forward, this part is a launchpad. The social-network anchor threaded through Chapters 27, 28, 29, and 33 culminates in Track B of the Chapter 39 capstone, a complete social-network analyzer assembled from the graphs.py module you build here piece by piece. The easy-versus-hard boundary you meet informally in Chapter 30 (with its preview of NP-hardness) becomes the formal subject of Chapter 37, where TSP and clique join SAT in the catalog of NP-complete problems. Even the automata of Chapter 35 borrow this part's graph-as-diagram intuition. Part V is, in short, both a destination and a bridge.

Time Investment

Estimated hours per chapter, taken from the master outline. Plan for the higher end on the chapters marked advanced, where the proofs (greedy correctness, max-flow min-cut, the Euler-path characterization) repay slow reading.

Chapter Title Difficulty Estimated time
27 Introduction to Graphs beginner 6 h
28 Graph Representations, Traversal, and Search intermediate 7 h
29 Weighted Graphs and Shortest Paths intermediate 7 h
30 Euler Paths, Hamilton Paths, and the TSP advanced 6–7 h
31 Trees intermediate 7 h
32 Spanning Trees and Minimum Spanning Trees intermediate 6–7 h
33 Graph Coloring and Planarity advanced 6–7 h
34 Network Flow and Matching advanced 7 h
Part total ≈ 51–55 h

Begin with Chapter 27. It is the vocabulary chapter, and its quiet work — pinning down what a graph is with sets, naming every part without ambiguity, and proving the handshaking lemma — is what makes every algorithm that follows expressible at all. Start from the small social network you will meet on its first page, draw it yourself, and you will have the foundation for everything in Part V.

Chapters in This Part