Start Doing Graph Theory


  1. The Beginning Download PDF
    1. Modeling problems with graphs
      • Coloring the cantons of Switzerland
      • The Towers of Hanoi
      • A tiling puzzle
      • Taking photos efficiently
      • Match the cars and drivers
      • Practice problems
    2. Isomorphisms and subgraphs
      • A plethora of Wagners
      • 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
      • Distances
      • 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 and the Kneser graphs
      • 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
      • Counting unlabeled trees
      • Practice problems
  4. Matchings Download PDF
    1. Bipartite graphs
      • Rooks on chessboards
      • 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
    1. Hamilton cycles
    2. Cliques and independent sets
    3. Vertex coloring
    4. Line graphs
  6. Planar Graphs
    1. Planar graphs
    2. Planarity testing
    3. Coloring planar graphs
    4. Polyhedra
  7. Connectivity
    1. Cut vertices
    2. Connectivity
    3. Menger's theorem
    4. Maximum flows
  8. Appendix
    1. Review of proof-writing
    2. Proof by induction
    3. Linear algebra in graph theory
    4. References

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