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/6?
  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/4: §8 on bridges. Here we get truly serious.
  • Due 2/x: §9, historical notes. Read historical notes. They often are interesting.


• 2/8? – ?
  Chapter II: Contractions and the Theorem of Menger.
  • More basics; famous theorems.
  • Due 2/8: §1 on contraction.
  • Due : §2 on edge contraction.
  • Due : §3, more on attachment vertices.
  • Due : §4 on counting separation vertices.
  • Due : §5 on vertex and edge versions of Menger's Theorem.
  • Due : §6, the same for Hall's Theorem.
      In the statement of II.38, read "whose U-deficiency is less than or equal to n" instead of "less than n". (Also, the proof seems to need more detail in page 52, line 3.)
  • §7, historical notes. Regarding §7.1, Kruskal's Conjecture is now the famous Robertson–Seymour Graph Minors Theorem.


• ? – ?
  Chapter III: 2-Connection.
  • Basic structure theory.


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


• Interpolation on 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.