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


• ? – ?
  Chapter IV: 3-Connection.
  • Higher structure theory.


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


• ? – ?
  Chapter VIII: Algebraic Duality.
  • Algebraic approach to graph structure.


• ? – ?
  Chapter IX: Polynomials Associated with Graphs.
  • Algebra of deletion-contraction invariants. Chromatic polynomial and number.