Math 510
Introduction to Graph Theory
Spring 2026

Syllabus and Schedule

The textbook is W.T. Tutte, Graph Theory. Details will appear as time flies by.

• 1/21–23
  Friendly introduction to graph theory and graph structure (the first topic, Ch. I-IV).

Read the assignment before the class.
"Due" means the due date for having read that section (or those sections).
Then we can discuss it in class. If you don't understand some (or all) of it, that's why you read it ahead of time. Then we answer questions.
Tutte's way of writing can be opaque, so if you are confused, it's normal. That's why we talk it over.

• 1/26 – 2/4
  Chapter I: Graphs and Subgraphs.
  • Basics.
  • Due 1/26: §§1–2 on basic concepts.
  • Due 1/28: §3 on subgraphs, §4 on attachment.
  • Due 1/30: §4 on attachment, §5 on detachment and connection.
  • Due 1/33 = 2/2: §6 on edge deletion, trees and forests, isthmi and circuits, §7 on enumerating isomorphism types of small size.
  • Due 2/2-4 (corrected ex post facto): §8 on bridges. Here we get truly serious.
  • Due 2/x: §9, historical notes. Read historical notes. They often are interesting.


• 2/6 – 2/23
  Chapter II: Contractions and the Theorem of Menger.
  • More basics; famous theorems.
  • Due 2/6: §1 on contraction.
  • Due 2/9: §2 on edge contraction.
  • Due 2/11: §3, more on attachment vertices.
  • Due 2/13: §4 on counting separation vertices.
  • Due 2/16-18: §5 on vertex and edge versions of Menger's Theorem.
  • Due 2/20: §6, the same for Hall's Theorem.
      In the statement of II.38, read "at most (|S| − n)" instead of "fewer than". (Also, the proof seems to need more detail in page 52, line 3.)
      König's Theorem: In a bipartite graph, the matching number = the vertex cover number.
  • §7, historical notes. Regarding §7.1, Kruskal's Conjecture is now a special case of the famous Robertson–Seymour Graph Minors Theorem, which is part of the Robertson–Seymour graph structure theory.


• 2/23 – 3/6
  Chapter III: Separability and 2-Connection.
  • Basic structure theory.
  • Due 2/23-25: §§1-2 on 2-connected graphs.
  • Due 2/25-3/4: §3 on blocks in a graph.
  • Due 3/4: §4 on arms of a vertex. Also, digression on graph decomposition.
  • Due 3/6: §5 on preservation of 2-connection under deletion and contraction.


• 3/9 – 4/13
  Chapter IV: 3-Connection.
  • Higher structure theory.
  • Due 3/9-11: §1 on higher connection; §2 on constructions and examples of 3-connected graphs.
  • Due 3/13-27: §3 on 3-blocks.
  • Due 3/23-27: §4 on cleavages and the 3-block structure of a graph.
      See statement of rules for 3-block decomposition using cleavages.
  • Due 4/8: §5 on edge deletion and contraction.
      Thought question: Tutte's Figure IV.5.1 bears a remarkable resemblance to Figure 1 in Richard Behr's article "Edges and vertices in a unique signed circle in a signed graph". Is this a coincidence?
  • Due 4/8: §6 on the Wheel Theorem for 3-connected graphs.
  • Due 4/8: §7 for context.


• Interpolation 3/25: The induced-subgraph approach to graph theory.


• Interpolation 4/8-10: Graph duality via planarity.
    See the introduction to Wikipedia "Dual graph" for a quick view of planar duality.
    See the dictionary page for the key points of planar duality.


• 4/13 – 4/24
  Chapter VIII: Algebraic Duality.
  • Algebraic approach to graph structure.
      In this chapter focus on the definitions, statements, and techniques, not the proofs. I am not following the material in the same order as the book; instead, I am emphasizing the graph and regular examples of chain groups.
      Correction: The definition of a primitive chain should say the non-zero coefficients are "regular" (i.e., invertible).
  • Due 4/13: §1 on chain-groups. This will look like linear algebra.
  • Due 4/15: §§2-3 on regular chain-groups. This will look less like linear algebra.
  • Due 4/17-22: §§4-5 on cycles and coboundaries. Chain groups of a graph.
      This will look familiar to those who have studied algebraic topology.
  • Due 4/22: §10 on incidence matrices.
  • Due 4/24: §7 p. 206 and top of 207, for algebraic duality.
      For planar duality see the dictionary page for the key points.


• 4/27 – 5/6
  Chapter IX: Polynomials Associated with Graphs.
  • Algebra of deletion-contraction invariants. Chromatic polynomial and number.
  • Due 4/27: §2: Chromatic polynomial and chromatic number.
  • Due 4/29: §4: Flow polynomial and graph duality.
  • Due 5/1: §6: The famous Tutte polynomial or "dichromate".