Math 510
Introduction to Graph Theory
Spring 2022

• Basics.
  Read the assignment before the class so 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 (surprise?).
• 1/28: §§ 1–3 on basic concepts.
• 1/31: § 4 on attachment.
• 2/2: § 5 on detachment and connection.
• 2/7–9: § 6 on edge deletion, trees and forests, isthmi and circuits.
• 2/7: § 7 on enumerating isomorphism types of small size. (This is simple; I won't discuss it in class unless there are questions.)
• (2/9 and) 2/11: § 8 on bridges. Here we get truly serious.
• 2/11: § 9, historical notes. It's always worth reading historical notes.

• More basics; famous theorems.
• 2/14–16: § 1 on contraction.
• 2/16–18: § 2 on edge contraction.
• 2/21: § 3, more on attachment vertices.
• 2/23: § 4 on counting separation vertices.
• 2/25–28: § 5 on vertex and edge versions of Menger's Theorem.
• 2/28: § 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.

• Basic structure theory.
• 3/4: §§ 1-2 on 2-connected graphs.
• 3/7: § 3 on blocks in a graph.
• 3/9: § 4 on arms of a vertex. Also, digression on graph decomposition.
• 3/11: § 5 on preservation of 2-connection under deletion and contraction.

• Higher structure theory.
• 3/21–23: § 1 on higher connection; § 2 on constructions and examples of 3-connected graphs.
• 3/23–28: § 3 on 3-blocks.
• 3/30: Interpolation on the induced-subgraph approach to graph theory.
• 4/1: § 4 on cleavages and the 3-block structure of a graph.
• 4/4: § 5 on edge deletion and contraction.
• 4/4: § 6 on the Wheel Theorem for 3-connected graphs.
• 4/4: § 7 for context.

I lectured on matroids at the first formal conference on them [...] in 1964. To me that was the year of the Coming of the Matroids. Then and there the theory of matroids was proclaimed to the mathematical world. And outside the halls of lecture there arose the repeated cry: ‘What the hell is a matroid?’
— W.T. Tutte