Proofs where you need them
Each theorem carries the argument that makes it true — the exchange step, the invariant, the counting — so you can re-derive the algorithm instead of memorising it.
80 pages · 15 chapters · free to read
Graph theory for olympiads and contests
Every idea from a first DFS to centroid decomposition, Hopcroft–Karp and min-cost flow — written from scratch with the proof next to the code, a complexity badge on every technique, and 13 interactive widgets you can step through.
- 80
- pages
- 63,685
- words
- 98
- code snippets
- 13
- interactive demos
- 180
- judge problems
- 39
- figures
Code you can paste under pressure
Complete C++ snippets with the trap list next to them: the emit-then-reverse in Hierholzer, the
inverted priority_queue comparator, the doubled pos array in a lazy segment tree.
Complexity as a decision, not a footnote
Every technique is badged with time and memory, and every multi-method page ends with a table that says which one to write and why.
Chapters
1Graphs and ModelsVocabulary, representations, connectivity and bipartiteness — the ground floor everything else stands on.7 pages · 4,107 words2TreesSix definitions of one object, two traversals, diameter, and the DFS clock that turns subtrees into intervals.7 pages · 5,104 words3Directed GraphsDAGs and topological order, strongly connected components, cycles, tournaments, functional graphs.7 pages · 4,799 words4Proof ToolkitExtremal choice, double counting, contraction: the three moves that crack existence problems.3 pages · 2,045 words5Euler Tours and Hamilton CyclesDegree conditions vs. NP-completeness, Hierholzer, De Bruijn sequences, Held–Karp.6 pages · 4,472 words6Shortest PathsDijkstra, Bellman-Ford, Floyd–Warshall and the small-weight special cases.4 pages · 3,300 words7MatricesAdjacency matrices as machines: walk counts, fast recurrences, and the matrix–tree theorem.4 pages · 2,764 words8Data Structures on TreesHeaps, DSU, Fenwick, segment trees, tries and sparse tables.6 pages · 4,407 words9Hardness and Escape RoutesP, NP, reductions — and what to actually do when the problem is NP-complete.3 pages · 2,248 words10Lowest Common AncestorBinary lifting, RMQ reduction, Tarjan offline, virtual trees.6 pages · 4,578 words11Advanced Tree AlgorithmsMST (Kruskal/Prim/Borůvka), small-to-large, centroid decomposition, HLD, hashing, Huffman.6 pages · 5,298 words12Cuts and FlowsConnectivity theorems, max-flow with Dinic, and min-cut modelling.4 pages · 3,727 words13MatchingAugmenting paths, Kőnig, Hopcroft–Karp, tilings, posets, general graphs.7 pages · 6,048 words14Special TopicsPlanarity, degree sequences, colouring, 2-SAT, random walks, Ramsey.7 pages · 8,037 wordsAAppendixComplexity sheet, contest template, notation, and how this edition is built.3 pages · 2,751 words
Interactive
Graphs and Models. Most graph problems are won or lost at modelling: deciding what the vertices *are*. This chapter builds the vocabulary that the rest of the book assumes, and the two representations you will type in a contest.
Trees. Trees are where graph algorithms become honest: no cycles means every traversal is a proof. Learn the six equivalent definitions, then the two traversals, and you already own a surprising share of olympiad problems.
Directed Graphs. Orientation breaks symmetry — and gives you order. Once you can collapse a digraph to its DAG of strongly connected components, half of “impossible ordering” problems become plain DP on a DAG.
Proof Toolkit. Olympiad graph theory is barely about algorithms; it is about three proof moves used relentlessly. Name them and you can attack a problem with no idea where to start.
Euler Tours and Hamilton Cycles. Traverse every *edge* and the problem is linear; traverse every *vertex* and it is NP-complete. The border between those two is the most instructive line in the subject.
Shortest Paths. Four algorithms, one shared idea: keep a frontier of tentative distances and relax edges until the frontier is honest. What differs is what you are allowed to assume about the weights.
Matrices. A graph written as a matrix is a linear recurrence in disguise. Multiply it by itself log k times and you have counted every walk of length k — or computed the number of spanning trees with a determinant.
Data Structures on Trees. The five structures in this chapter appear in the majority of graph problems that are not purely graph-theoretic. Know them cold: the code below is the code you type in a contest.
Hardness and Escape Routes. Proving hardness is a research field; recognising it in a contest is a 30-second pattern match. The useful skill is knowing which escape route the constraints are hinting at.
Lowest Common Ancestor. LCA is the hinge between trees and queries. Four solutions, four different ideas — DSU, sparse tables, DFS order, and decomposition — which is why it is the best practice topic in the book.
Advanced Tree Algorithms. Two structural ideas carry this whole chapter: sort-and-merge (MST, Kruskal) and split-at-a-good-vertex (centroid, HLD). Everything else is bookkeeping.
Cuts and Flows. Max-flow min-cut is the most reusable theorem in combinatorial optimisation: every problem whose answer is “the smallest set of things blocking the largest number of paths” is a flow problem in disguise.
Matching. Matching is where duality becomes visible: every max matching has a min vertex cover, and the proof of one is an algorithm for the other.
Special Topics. A toolbox of one-off ideas that keep showing up in finals: Euler's formula, greedy colouring bounds, the implication graph, hitting times, and Ramsey's unavoidable order.
Appendix. The pages you want open in the last hour: what runs in time, what the code skeleton looks like, and what every symbol in the book means.