All exercises are numbered as in the printed third edition of Diestel's book.
I have additional exercises on a separate page. They are numbered with Roman numerals. Treat them on the same basis as exercises in the book.
| Week of | Topic | Reading sections | Problems to work on [Recommended] | Problems to hand in with due date | ||||
| 1/28 - 2/4 | Basic concepts: Graphs and multigraphs; Degree; Standard examples | 1.1 - 1.4, 1.10 | Ch. 1 (as many as you can) [2, 6, 10, 11, 14, 17] | |||||
| 2/4 - 2/8 | Basic concepts: Connectivity; Trees; Biparticity; Minors; Eulerian tours | 1.4 - 1.8 | (ditto) [20 - 23, 26, 33] | IA. Th 2/7: Ch. 1 ## 3, 4, 6 IB. F 2/8: Ch. 1 ## 8, 15; proof of Cor. 1.5.4 | ||||
| 2/11 - 2/15 | Basic concepts: Cycle and cocycle spaces; Matching | 1.9 - 1.10, 2.1 (omit Gale-Shapley Thm. 2.1.4) | Ch. 1, 2 (as many as you can; low numbers in Ch. 2) [Ch. 2 ## 1, 6] | II. W 2/13: Ch. 1 ## 16, 24, 27, 31 | ||||
| 2/18 - 2/22 | Matching | 2.1 - 2.2, 2.5 (omit Gale-Shapley) | Ch. 2 (as many as you can) [Ch. 1 # 32] [Ch. 2 ## 7, 11, 13, 15, VI(some), VII(1,2)] | III. W 2/20: Ch. 1 ## 25, 29; Ch. 2 ## 2, 5 | ||||
| 2/25 - 2/29 | Packing;
Connectivity: Structure | 2.4 - 2.5, 3.1 | Ch. 2, 3 (as many as you can) [Ch. 2 ## 19, 21, 22, III, IV] [Ch.3 ## 1-3, 6, 8] | IV. F 2/29: Ch. 1 # II; Ch. 2 ## 12, 14, VII(3-4) | ||||
| 3/3 - 3/7 | Connectivity: Structure, Menger's theorem; Planarity | 3.2 - 3.3, 4.1 | Ch. 3 (as many as you can) [Ch. 3 ## 4, 9, 12, 14, 16, II] [Ch. 4 ## 4, 7-9] | V. F 3/7: Ch. 1 # III; Ch. 2 ## 23, 24, VII(5-6); Ch. 3 ## 7, 11 | ||||
| 3/10 - 3/14 | Planarity: Plane graphs, Euler's formula, Equivalent embeddings, Duality | 4.2 - 4.4 | Ch. 4 (omit 21, 25-33) [Ch. 4 ## 3, 8, 17, 18, 23] | VI. F 3/14: Ch. 3 ## 12, 15, 17, I, III; Ch. 4 ## 2, 4, 5 | ||||
| 3/17 - 3/19 | Bridges of a subgraph;
Planarity: Kuratowski's theorem, Duality | 4.4, 4.6 | Ch. 4 (as many as you can from 25-33) [Ch. 4 ## 28-31] | VII. F 3/21 (or sooner): Ch. 4 ## 20, 22, 25, 32, I | ||||
| 3/31 - 4/4 | Circles, hyperplanes, and vectors: Graphs, signed graphs, abstract duality; Vertex coloring: Chromatic polynomial, Chromatic number | 4.5; Lecture; 5.1 | Ch. 5 (as many as you can on vertex coloring) | None | ||||
| 4/7 - 4/11 | Coloring: Chromatic number, Chromatic index, Signed graphs; Perfect graphs, chordal graphs | 5.1-3 (omit constructible graphs); Lecture; 5.5 through the statement of 5.5.4 | Ch. 5 (problems related to vertex and edge coloring) [Ch. 5 ## 1, 3, 6, 10-11, 16, V(b), VI, VII, X(a), XI] | VIII. W 4/16: Ch. 4 # 11; Ch. 5 ## 4, 7, 8, 18, I | ||||
| 4/14 - 4/17 | Graph minors: WQO (well quasi-ordering), Trees under topological minor ordering, Tree decomposition of graphs | Ch. 12 to Lemma 12.3.2 | Ch. 12 (early problems) [Ch. 12 ## 2, 5, 9, 12, I] | IX. Th 4/24 (no later than 5:30 p.m.): Ch. 12 ## 3, 6-8, 11 | ||||
| 4/22 - 4/25 | Graph minors: Tree decomposition, Tree width, Higher Kuratowski theorem; Surfaces | 12.3 from Lemma 12.3.3 to end (Skip forward direction of 12.3.9); 12.4 to top of p. 329 (external connectivity) and mid p. 339 to mid p. 340; Appendix B | [Ch. 12 ## II, 17, 20, 22, 24-25, 32, 33] | X. F 4/25 (3:30): Ch. 5 ## VII, VIII Ch. 12 ## 16, 18, 22 | ||||
| 4/28 - 5/1 | Graph minors: Graph minors theorem; Nowhere-zero group flows (briefly): Circulations, Nowhere-zero flows | 12.5 to statement of 12.5.3 (p. 342) 6.1, 6.3, bits from 6.4-6. | [Ch. 12 ## 12-14, 24-25, III, IV] [Ch. 6 ## I, 5, 9, 15, 18] | None. | ||||
| 5/5 - 5/9 | No classes. If you want to broaden your acquaintance to some major areas, read 7.1 (extremal graphs with excluded subgraphs), 10.1 (Hamiltonian circles). | [Ch. 12 ## 26, V] | XI. Tues 5/13, 2:00 p.m. (no late submissions): Ch. 4 # III; Ch. 5 # X; Ch. 12 ## 21, 29-30, 34, VI |