Start Doing Graph Theory


On this page, you can get an overview of the topics covered in each chapter.

You can use the download links below to get individual parts of this book as standalone PDF files, if that's more convenient. You can also click here to download the entire book.


  1. The Beginning Download PDF
    1. Modeling problems with graphs
      • Coloring Switzerland
      • The seven dwarfs
      • The Towers of Hanoi
      • A tiling puzzle
      • Taking photos efficiently
      • Match the cars and drivers
      • Practice problems
    2. Isomorphisms and subgraphs
      • Circulant graphs
      • Are these the same?
      • The isomorphism game
      • Graph invariants
      • Subgraphs and some common graphs
      • Practice problems
    3. Walks, paths, and cycles
      • Walks and paths
      • Connected graphs
      • Equivalence relations
      • Closed walks and cycles
      • Lengths of walks
      • Practice problems
    4. The degree of a vertex
      • Hypercube graphs
      • The handshake lemma
      • Degrees and connectedness
      • Degrees and cycles
      • Average degree
      • Practice problems
  2. Vertex Degrees Download PDF
    1. Regular graphs
      • Degree sequences
      • Regular graphs
      • How many regular graphs are there?
      • The Petersen graph
      • The degree/diameter problem
      • Practice problems
    2. Graphic sequences
      • An unusual party
      • A graphic sequence algorithm
      • Two examples
      • The Havel–Hakimi theorem
      • More on degree sequences
      • Practice problems
    3. Multigraphs and digraphs
      • Multigraphs
      • Degrees in multigraphs
      • Directed graphs
      • Directed walks, paths, and cycles
      • Practice problems
    4. Euler tours
      • Don't lift your pencil!
      • First steps
      • Cycle decompositions
      • Gluing cycles together
      • Variations on Euler tours
      • Practice problems
  3. Trees Download PDF
    1. Trees and spanning trees
      • Spanning trees
      • Bridges
      • Properties of trees
      • Minimum-cost spanning trees
      • Practice problems
    2. Properties of trees
      • A square garden
      • Counting edges in trees
      • From trees to forests
      • Leaves in trees
      • Induction on trees
      • Practice problems
    3. Cayley's formula
      • How to count graphs
      • Trees and deletion sequences
      • Prüfer codes
      • Working with Prüfer codes
      • Unlabeled trees
      • Practice problems
    4. Directed acyclic graphs
      • Directed acyclic graphs
      • Topological orders
      • Strongly connected
      • Condensations
      • Practice problems
  4. Matchings Download PDF
    1. Bipartite graphs
      • Two chess puzzles
      • Bipartite graphs
      • Odd cycles
      • Matching problems
      • Maximum and maximal
      • Vertex covers
      • Practice problems
    2. Kőnig's theorem
      • Kőnig's theorem
      • Augmenting paths
      • The augmenting path algorithm
      • Analyzing the algorithm
      • Using the algorithm
      • Practice problems
    3. Hall's theorem
      • Hall's theorem
      • Regular bipartite graphs
      • A three-card magic trick
      • Generalized tic-tac-toe
      • Incomparable sets
      • Practice problems
    4. Matchings in general graphs
      • Tutte sets
      • Saturated graphs
      • Proof of Tutte's theorem
      • 1-factorizations
      • Increasing walks
      • Practice problems
  5. Hard Problems Download PDF
    1. Hamilton cycles
      • Knight's tours
      • Two examples
      • Tough graphs
      • Sufficient conditions
      • Practice problems
    2. Cliques and independent sets
      • Two problems about queens
      • Redundancies and relationships
      • Greedy algorithms
      • An indecisive algorithm
      • Ramsey numbers
      • Lower bounds
      • Practice problems
    3. Graph coloring
      • Graph coloring and Sudoku
      • Greedy coloring
      • Two lower bounds
      • Coloring interval graphs
      • Mycielski graphs
      • Practice problems
    4. Line graphs
      • Line graphs
      • Euler tours and Hamilton cycles
      • De Bruijn sequences
      • Edge coloring
      • Vizing's theorem
      • Practice problems
  6. Planar Graphs Download PDF
    1. Planar graphs
      • Three utilities
      • Planar graphs
      • Faces
      • Euler's formula
      • Barycentric subdivisions
      • Technical details
      • Practice problems
    2. Planarity testing
      • Counting edges in planar graphs
      • Triangulations
      • Girth and planarity
      • Subdivisions
      • Graph minors
      • Overlap graphs
      • Practice problems
    3. Polyhedra
      • The Platonic solids
      • Classifying the Platonic solids
      • Dual graphs
      • Archimedean solids
      • Practice problems
    4. Coloring maps
      • Coloring maps
      • The four color theorem
      • Greedy coloring
      • Five colors
      • Hamilton cycles
      • Coloring empires
      • Practice problems
  7. Connectivity Download PDF
    1. Cut vertices
      • Counting paths
      • Cut vertices
      • 2-connected graphs
      • Ear decompositions
      • Induction on ears
      • Finding common cycles
      • Practice problems
    2. Connectivity
      • Vertex and edge cuts
      • Some examples
      • Local connectivity
      • Duality
      • Practice problems
    3. Menger's theorem
      • Menger's theorem
      • Kőnig-type graphs
      • Reducing all other cases
      • Extensions
      • Cuts and long cycles
      • Practice problems
    4. Maximum flows
      • Shipping oranges
      • Maximum flow problems
      • Network cuts
      • The Ford–Fulkerson algorithm
      • Counting iterations
      • Consequences
      • Practice problems
  8. Appendix Download PDF
    1. Review of proof-writing
      • Conditional statements
      • Quantifiers
      • Unpacking definitions
      • Optimization problems
      • Algorithms
      • The extremal principle
      • Practice problems
    2. Proof by induction
      • The logic of induction
      • Induction on graphs
      • Inductive definitions
      • Recursive constructions
      • Practice problems

Start Doing Graph Theory © 2025 by Mikhail Lavrov is licensed under CC BY-SA 4.0