Learn graph theory: the best books in order
This curriculum builds a rigorous, end-to-end mastery of graph theory starting from a solid intermediate base. It moves from core structural theory and proof techniques, through classical topics like paths, trees, matchings, and coloring, into algorithmic graph theory and finally advanced network-focused applications — each stage sharpening both mathematical intuition and practical problem-solving skills.
Core Foundations
IntermediateEstablish a firm grasp of graph theory's fundamental objects — vertices, edges, paths, cycles, trees, connectivity, and planarity — along with the proof style used throughout the field.
▸ Study plan for this stage
Pace: 8–10 weeks, ~25–30 pages/day (Chapters 1–4 of Diestel)
- Graphs as abstract objects: vertices, edges, directed vs. undirected graphs, and multigraphs
- Paths, cycles, and walks: definitions, properties, and their role in characterizing graph structure
- Connectivity and components: vertex and edge connectivity, bridges, cut vertices, and k-connected graphs
- Trees and forests: characterization as acyclic connected graphs, spanning trees, and their minimality properties
- Planarity and the Kuratowski theorem: planar embeddings, Euler's formula, and forbidden minors
- Proof techniques in graph theory: induction on vertices/edges, contradiction, and structural decomposition arguments
- Bipartite graphs and graph coloring: recognition via BFS, chromatic number, and algorithmic implications
- Density and extremal properties: edge counts, degree sequences, and the handshaking lemma
- What is the precise definition of a graph, and how do directed graphs, multigraphs, and simple graphs differ in structure and application?
- How are paths, cycles, and walks formally distinguished, and why does this distinction matter for proving connectivity properties?
- What does it mean for a graph to be k-vertex-connected or k-edge-connected, and how do you verify these properties algorithmically?
- Why is every tree on n vertices characterized by having exactly n−1 edges, and how does this lead to the concept of a spanning tree?
- State Euler's formula for planar graphs and use it to prove that K₅ and K₃,₃ are non-planar.
- What are the key inductive and structural proof techniques Diestel uses, and how do you apply them to establish properties like connectivity or acyclicity?
- Draw and formally describe the vertex and edge sets for 5–6 different graphs (simple, directed, multigraph examples); verify the handshaking lemma for each.
- For a given graph, identify all paths, cycles, and walks between two vertices; explain why some are paths and others are not.
- Compute the vertex and edge connectivity of 4–5 named graphs (e.g., complete graphs, cycles, grids); identify bridges and cut vertices by hand.
- Prove by induction that any tree on n vertices has exactly n−1 edges; then construct and verify spanning trees for 3 non-tree graphs.
- Test planarity for K₄, K₅, K₃,₃, and the Petersen graph using Euler's formula and the Kuratowski forbidden-minor criterion.
- Write formal proofs (following Diestel's style) for 4–5 foundational theorems: e.g., 'a connected graph is a tree iff it is acyclic,' or 'a graph is bipartite iff it contains no odd cycles.'
Next up: Mastery of these foundational objects and proof techniques equips you to tackle more advanced topics—such as matching theory, network flows, and graph algorithms—where these core structures serve as the building blocks for optimization and algorithmic analysis.
The gold-standard modern textbook: rigorous yet readable, it covers paths, trees, connectivity, planarity, and coloring with clean proofs. Starting here gives you the precise language and core theorems every later book assumes.
Classical Theory — Matchings, Coloring & Structure
IntermediateMaster the classical combinatorial results — matching theory, chromatic polynomials, Ramsey theory, and structural decompositions — that form the backbone of advanced graph research.
▸ Study plan for this stage
Pace: 8–10 weeks, ~40–50 pages/day (Harary: 4–5 weeks; Biggs: 4–5 weeks)
- Matching theory: maximum matchings, Hall's theorem, König's theorem, and augmenting paths in bipartite and general graphs
- Graph coloring: chromatic number, chromatic polynomial, greedy coloring algorithms, and bounds (Brooks' theorem, five-color theorem)
- Ramsey theory: Ramsey numbers, existence of monochromatic cliques and independent sets in large graphs
- Structural decomposition: tree decomposition, planar graph structure, Kuratowski's theorem, and forbidden minors
- Algebraic methods: adjacency matrices, eigenvalues, spectral graph theory, and their connection to graph properties
- Bipartite graph characterization: König-Egerváry theorem, perfect matchings, and Hall's marriage theorem applications
- Graph homomorphisms and automorphisms: symmetry groups and their role in graph classification
- Connectivity and flow: vertex/edge connectivity, network flow, and min-cut/max-flow duality
- State Hall's marriage theorem and explain how it characterizes the existence of a perfect matching in a bipartite graph.
- Define the chromatic polynomial P(G, k) and compute it for small graphs (paths, cycles, complete graphs). What does P(G, −1) tell you?
- Prove or explain König's theorem: in a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.
- What is a Ramsey number R(m, n)? Give examples (R(3,3), R(3,4)) and explain why Ramsey numbers grow so rapidly.
- Describe the adjacency matrix spectrum of a graph and explain how eigenvalues relate to graph properties (diameter, bipartiteness, regularity).
- State Kuratowski's theorem and explain what it means for a graph to be planar in terms of forbidden minors.
- What is an augmenting path in matching theory, and how is it used to find maximum matchings?
- Explain the relationship between graph homomorphisms and the chromatic number: why is χ(G) the minimum k such that there exists a homomorphism from G to K_k?
- Work through Harary's matching chapter: compute maximum matchings and minimum vertex covers for 5–10 bipartite graphs by hand using augmenting paths; verify König's theorem in each case.
- Compute chromatic polynomials for 8–10 graphs (trees, cycles, wheels, complete graphs, grid graphs) using deletion-contraction; verify your results by computing P(G, k) for small k values and checking against greedy colorings.
- Prove Hall's marriage theorem from scratch, then apply it to 4–5 concrete problems (e.g., scheduling, system of distinct representatives).
- Calculate Ramsey numbers R(3,3), R(3,4), R(4,3) by exhaustive search on small graphs; construct explicit colorings and monochromatic subgraphs.
- For 6–8 graphs, compute the adjacency matrix, find all eigenvalues, and relate the spectrum to graph properties (bipartiteness, regularity, diameter bounds).
- Identify whether 5–10 given graphs are planar using Kuratowski's theorem; find K₅ or K₃,₃ subdivisions in non-planar examples.
- Implement or simulate augmenting path algorithms (Hungarian algorithm, Hopcroft-Karp) on 3–4 bipartite matching instances; measure performance.
- Construct graph homomorphisms between pairs of graphs and determine the chromatic number by finding the minimum target complete graph.
Next up: By mastering classical structural results and their algebraic foundations, you are now equipped to explore modern algorithmic and probabilistic techniques—such as randomized algorithms for coloring, approximation algorithms for matching, and the probabilistic method in Ramsey theory—that extend and optimize these classical results.
A foundational classic that shaped the field's vocabulary; reading it after Diestel reveals the historical development of structural results and offers a different, more combinatorial perspective on the same theorems.
Introduces the spectral and algebraic tools — adjacency matrices, eigenvalues, automorphisms — that unlock deeper structural understanding and are essential for later work on network algorithms.
Algorithms on Graphs
IntermediateLearn how the theoretical structures translate into efficient algorithms — shortest paths, spanning trees, flows, and matching algorithms — and understand their correctness and complexity.
▸ Study plan for this stage
Pace: 8–10 weeks, ~40–50 pages/day (mix of theory and worked examples)
- Shortest path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall) and their correctness proofs via relaxation and induction
- Minimum spanning trees (Kruskal's and Prim's algorithms) and the cut property and cycle property that justify greedy approaches
- Breadth-first and depth-first search as foundational traversal paradigms for discovering graph structure
- Maximum flow and minimum cut: the max-flow min-cut theorem and Ford-Fulkerson method with augmenting paths
- Bipartite matching and general matching algorithms, including augmenting paths and the relationship to flow networks
- Algorithm design patterns: greedy algorithms, dynamic programming on graphs, and divide-and-conquer for graph problems
- Complexity analysis: time and space bounds for each algorithm and how they scale with |V| and |E|
- Correctness arguments: loop invariants, exchange arguments, and potential functions for proving algorithm termination and optimality
- How does Dijkstra's algorithm maintain a loop invariant to guarantee shortest paths, and why does it fail on negative-weight edges?
- Explain the cut property and cycle property of minimum spanning trees, and how they justify the correctness of Kruskal's and Prim's algorithms.
- What is an augmenting path in the context of maximum flow, and how does the Ford-Fulkerson method use augmenting paths to find an optimal flow?
- How do you model a bipartite matching problem as a maximum flow problem, and what does the max-flow value tell you about the matching?
- Compare the time complexity of Dijkstra's algorithm with a binary heap versus a Fibonacci heap, and explain when each is preferable.
- Describe how depth-first search can be used to detect cycles, find strongly connected components, and compute topological orderings.
- Implement Dijkstra's algorithm with a binary heap and test it on graphs with 100–1000 nodes; measure runtime and verify shortest paths against a reference implementation.
- Implement Kruskal's algorithm using a union-find data structure and Prim's algorithm with a priority queue; compare their performance on dense and sparse graphs.
- Implement the Ford-Fulkerson method with DFS (or BFS for Edmonds-Karp) to find maximum flow; test on small flow networks and verify the max-flow min-cut theorem by computing a minimum cut.
- Model a bipartite matching problem (e.g., job assignment, course scheduling) as a flow network and solve it using your max-flow implementation.
- Implement DFS-based algorithms to find strongly connected components (Kosaraju's or Tarjan's algorithm) and topological sort; apply them to real directed graphs.
- Work through the correctness proofs in Kleinberg's chapters on shortest paths and MSTs by hand; write out the loop invariants and exchange arguments in your own words.
Next up: This stage equips you with the algorithmic toolkit to solve concrete optimization problems on graphs; the next stage will extend these foundations to more specialized domains (e.g., network design, approximation algorithms, or advanced matching theory) and teach you how to recognize which algorithm applies to which real-world problem.
Covers graph algorithms (BFS/DFS, Dijkstra, minimum spanning trees, network flow, bipartite matching) with exceptional clarity on both correctness proofs and complexity, directly connecting graph theory to computer science.
A focused, mathematically careful treatment of graph-specific algorithms — planarity testing, strongly connected components, flows — that goes deeper than general algorithms texts and builds directly on the theory learned so far.
Network Flows & Combinatorial Optimization
ExpertDevelop mastery of flow networks, min-cut/max-flow duality, and combinatorial optimization on graphs, unifying the algebraic, structural, and algorithmic threads into a coherent whole.
▸ Study plan for this stage
Pace: 8–10 weeks, ~40–50 pages/day, with 2–3 days per week dedicated to problem-solving and implementation
- Flow networks: sources, sinks, capacities, and flow conservation constraints as a unifying framework for optimization
- Max-flow/min-cut duality and the Ford-Fulkerson method: proving optimality through the structure of cuts
- Polynomial-time algorithms for network flows (Edmonds-Karp, scaling algorithms) and their complexity analysis
- Reduction of combinatorial problems to flow networks: bipartite matching, circulation, and edge-disjoint paths
- Linear programming duality and its connection to flow problems: understanding optimization through dual perspectives
- Matroid theory and greedy algorithms: structural conditions for optimality in combinatorial problems
- NP-completeness and approximation algorithms: recognizing hard problems and designing practical solutions
- Unified perspective: how algebraic (LP), structural (cuts, matroids), and algorithmic (augmenting paths) viewpoints converge
- Explain the max-flow/min-cut theorem and prove why the value of a maximum flow equals the capacity of a minimum cut.
- How does the Ford-Fulkerson method work, and why does the residual graph formulation ensure correctness? What is the role of augmenting paths?
- Describe how to reduce the bipartite matching problem to a maximum flow problem. What is the relationship between a maximum matching and a maximum flow in your construction?
- What is the difference between a flow problem and a circulation problem? How can you transform one into the other?
- Explain linear programming duality in the context of network flows. What is the dual of a maximum flow LP, and what does it represent?
- What is a matroid, and under what conditions does the greedy algorithm produce an optimal solution? Give an example from graph theory.
- How do you recognize when a combinatorial optimization problem is NP-complete? What strategies exist for solving hard problems in practice?
- Implement the Ford-Fulkerson algorithm using DFS and the Edmonds-Karp algorithm using BFS on a directed graph; compare their running times on graphs of increasing size.
- Solve the maximum bipartite matching problem by constructing a flow network and running your implementation; verify correctness against a greedy baseline.
- Prove that a set of edges in a graph forms a matroid by checking the three matroid axioms; implement the greedy algorithm and verify it produces an optimal solution.
- Reduce the edge-disjoint paths problem to maximum flow; construct a test case and solve it using your flow implementation.
- Write out the LP formulation for a maximum flow problem and its dual; solve both using a linear programming solver and verify strong duality.
- Implement a circulation algorithm by reducing to maximum flow; test on a network with lower and upper bounds on edge capacities.
- Analyze the time complexity of Edmonds-Karp and a scaling algorithm; implement both and measure wall-clock time on dense graphs (n=500–1000 vertices).
- Identify an NP-complete problem from Papadimitriou's text; design a 2-approximation or better algorithm and evaluate its solution quality on random instances.
Next up: Mastery of flow networks and combinatorial optimization provides the algorithmic and structural foundation for advanced topics such as approximation algorithms, hardness of approximation, and applications to real-world network design and resource allocation problems.
Ties together matching, flows, matroids, and NP-completeness in a unified complexity-theoretic framework, giving you the tools to reason about what graph problems are tractable and why.
Advanced Topics & Modern Perspectives
ExpertEngage with cutting-edge and research-level topics — random graphs, graph minors, and spectral graph theory — to reach the frontier of the field.
▸ Study plan for this stage
Pace: 8–10 weeks, ~40–50 pages/day. Spectral graph theory (weeks 1–4, ~200 pages), then Random graphs (weeks 5–10, ~300+ pages). Allocate 2–3 days per chapter for dense theoretical sections and proofs.
- Spectral characterization of graphs via eigenvalues and eigenvectors of adjacency and Laplacian matrices
- Cheeger inequality and its role in bounding graph expansion and connectivity
- Expander graphs and their construction via spectral methods
- Random graph models (G(n,p) and G(n,m)) and their phase transitions
- Threshold phenomena and emergence of giant components in random graphs
- Concentration inequalities and probabilistic methods for analyzing random graph properties
- Spectral properties of random graphs and the relationship between spectrum and structure
- Graph minors, planarity, and structural decomposition in the context of modern graph theory
- How do the eigenvalues of the adjacency matrix and Laplacian matrix encode structural properties of a graph, and what does the spectral gap tell us about connectivity?
- What is the Cheeger inequality and how does it relate graph expansion to the second-smallest eigenvalue of the Laplacian?
- How are expander graphs constructed using spectral methods, and why are they important in computer science and network design?
- What are the main phase transitions in random graphs G(n,p), and at what edge probability does the giant component emerge?
- How do concentration inequalities (e.g., Chernoff, Azuma) apply to random graph analysis, and what properties do they guarantee with high probability?
- What is the relationship between the spectral properties of a random graph and its structural properties (connectivity, diameter, chromatic number)?
- Compute the eigenvalues and eigenvectors of the adjacency matrix for small graphs (4–6 vertices); verify the spectral gap and relate it to graph connectivity
- Prove or verify the Cheeger inequality for specific graph families (cycles, complete bipartite, random regular graphs)
- Construct an expander graph using spectral methods and verify its expansion properties numerically
- Simulate random graphs G(n,p) for varying p and n; identify and plot the phase transition for the emergence of the giant component
- Apply concentration inequalities to bound the number of triangles or the diameter of a random graph G(n,p)
- Analyze the spectrum (eigenvalues) of a random graph G(n,p) and compare it to theoretical predictions (e.g., circular law, Wigner semicircle law)
- Work through proofs of key theorems in Chung's book (e.g., relating spectral gap to expansion) and write summaries in your own words
- Solve selected problems from both books; focus on those combining spectral and probabilistic arguments
Next up: This stage equips you with the mathematical tools and modern perspectives needed to tackle current research problems in network science, algorithm design, and discrete mathematics—preparing you to read research papers, pursue specialized topics (e.g., random matrix theory, network models), or apply these ideas to real-world systems.
A concise, authoritative treatment of eigenvalue methods applied to expanders, random walks, and graph partitioning — essential for modern applications in data science and theoretical CS.
The canonical text on probabilistic graph theory, covering threshold phenomena, connectivity, and chromatic number in random models — the perfect capstone that reveals how classical theory extends into a probabilistic universe.
Discussion
Keep reading
Paths that share books, cover the same subject, or open a related topic.
