Further Reading: Introduction to Graphs

Annotated pointers for going deeper into graphs — the vocabulary, the handshaking lemma, isomorphism, and the leap from definitions to algorithms. Start with the textbook sections that mirror this chapter, then branch toward the algorithmic side (Chapter 28 and beyond) or the pure graph-theory side as your interest pulls you.

Core textbook treatments

Rosen, Discrete Mathematics and Its Applications (8th ed.), §§10.1–10.3 The market-standard introduction to graphs, graph terminology, and special graph types, with the handshaking lemma stated and proved and a large, well-graded exercise bank. §10.3 covers graph isomorphism and invariants exactly at this chapter's level. If you want more drill than the exercises here provide, start here.

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042J), the "Simple Graphs" chapters Freely available. The most CS-flavored introduction in print: graphs are developed with degree arguments, the handshaking lemma as "the sum of degrees is even," and a careful treatment of isomorphism and connectivity, all aimed at programmers. The companion to read alongside this chapter.

Levin, Discrete Mathematics: An Open Introduction (3rd ed.), "Graph Theory" chapter Freely available. A gentle, example-driven open-source treatment of vertices, edges, degree, and the handshaking lemma, with interactive exercises. Excellent if you want a second explanation in a different voice at no cost.

Epp, Discrete Mathematics with Applications (5th ed.), the graphs chapter A careful, definition-first presentation with especially clear treatment of walks vs. paths vs. circuits — the terminology distinctions that trip people up (§27.2). Good if the walk/path/cycle vocabulary still feels slippery.

Graph theory in depth

West, Introduction to Graph Theory (2nd ed.), Chapter 1 The standard upper-level graph theory text. Chapter 1 formalizes graphs, degree, paths, and isomorphism with full rigor, and proves the handshaking lemma and the even-odd-degree corollary as theorems. Reach for this when you want the mathematician's-eye view behind the CS framing — it is denser, and it rewards the effort.

Trudeau, Introduction to Graph Theory (Dover) A famously readable, inexpensive paperback that builds graph theory from scratch with a conversational tone and lots of pictures. A pleasant supplement for intuition, particularly on isomorphism and "when are two drawings the same graph?"

From definitions to algorithms

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), §§20.1 (Elementary Graph Algorithms — representations) The canonical reference on how a graph is actually stored — the adjacency list vs. adjacency matrix trade-off that the chapter's "What's Next" previews and Chapter 28 formalizes. Read the representations section now; save the BFS/DFS sections for Chapter 28.

Sedgewick & Wayne, Algorithms (4th ed.), "Graphs" section (also the free Algorithms, Part I materials) Companion materials free online. A code-forward treatment that implements the Graph API, adjacency-list storage, and degree computations in a style very close to this book's Toolkit. Useful for seeing the data-structure choices made concrete just before Chapter 28.

On graph isomorphism (the hard problem)

Rosen, Discrete Mathematics and Its Applications (8th ed.), §10.3 (Graph Isomorphism) Reread for the catalog of invariants (degree sequence, edge count, cycles) and worked examples of using one invariant to refute isomorphism — the §27.5 technique with more practice problems.

West, Introduction to Graph Theory (2nd ed.), §1.1 (Isomorphism) The rigorous definition and a proof that the listed invariants are genuinely preserved, plus a careful discussion of why matching invariants are necessary but not sufficient — the subtlety the chapter flags as a Common Pitfall.

Suggested order

  1. Read Rosen §§10.1–10.2 for a second pass on terminology, then do its handshaking-lemma exercises for drill.
  2. Read the MIT 6.042J "Simple Graphs" chapter for the CS framing of degree and isomorphism.
  3. Read CLRS §20.1 representations to see how graphs are stored — this bridges directly into Chapter 28.
  4. For isomorphism, work Rosen §10.3; if you want the proofs that the invariants are preserved, read West §1.1.
  5. Save West Chapter 1 (full) for after Chapter 30 (trees and connectivity), when the graph-theoretic results have more to attach to.