| Date | Content of the lecture | Lecture notes | Diestel's book
|
| Fri 2.9.
| Introduction to graph theory (see PDF slides from the first lecture)
| N/A | N/A
|
| Wed 7.9.
| Adjacency & incidence matrix, vertex-degree, walks & paths, connected components
| Chapters 1 & 2 | Chapter 1
|
| Mon 12.9.
| Subgraphs and induced subgraphs, various characterizations of trees | Chapter 3 | Chapter 1
|
| Wed 14.9.
| Number of labelled trees on n vertices (Cayley's formula) – PDF notes | N/A | N/A
|
| Mon 19.9.
| Minimum spanning trees and Kruskal's algorithm | Chapter 4 | N/A
|
| Wed 21.9.
| Shortest paths and Dijkstra's algorithm | Chapter 5 | N/A
|
| Mon 26.9.
| Euler tours and Euler's theorem, Hamilton cycles and Ore's theorem | Chapter 6 | Chapters 1 & 10
|
| Wed 28.9.
| 2-factors, Bipartite graphs and Hall's theorem – PDF notes | Chapters 7 & 8 | Chapters 1 & 2
|
| Mon 3.10.
| König's theorem and 2-factors in 2k-regular graphs | Chapters 8 & 15 | Chapter 2
|
| Wed 5.10.
| Vertex-connectivity of graphs & vertex-cuts, Menger's theorem | Chapter 9 | Chapter 3
|
| Wed 12.10.
| Edge-connectivity, edge-cuts, flows in networks, Ford-Fulkerson's theorem (statement) | Chapters 9 & 10 | Chapters 3 & 6
|
| Mon 17.10.
| Proof of Ford-Fulkerson's theorem | Chapter 10 | Chapter 6
|
| Wed 19.10.
| Ramsey's Theorem & lower-bound on Ramsey numbers | Chapter 12 | Chapters 9 & 11
|
| Mon 24.10.
| Midterm (in-class) – PDF here | N/A | N/A
|
| Wed 26.10.
| Multicolor Ramsey numbers & Shur's theorem, Matching & covering inequalities | Chapters 11 & 12 | Chapter 9
|
| Mon 31.10.
| Matchings in general graphs & Tutte's theorem | Chapter 13 | Chapter 2
|
| Wed 2.11.
| Petersen's theorem, Vertex colorings, Greedy coloring algorithm, Brooks' theorem | Chapter 14 | Chapter 5
|
| Mon 7.11.
| Colorings of d-degenerate graphs, chromatic number of triangle-free graphs | Chapter 14 | Chapter 5
|
| Wed 9.11.
| Exercise session – Connectivity & Hall & Ramsey | N/A | N/A
|
| Mon 14.11.
| Edge-colorings, Vizing's theorem, König's line coloring theorem, Shannon's theorem | Chapter 15 | Chapter 5
|
| Wed 16.11.
| Planar graphs & Euler's formula | Chapter 17 | Chapter 4
|
| Mon 21.11.
| Counting edges in planar graphs, Outer-planar graphs, Kuratowski's Theorem | Chapter 15 | Chapter 4
|
| Wed 23.11.
| Minors in graphs, Duality for planar graphs, 5-Color Theorem | Chapters 18 & 19 | Chapters 4 & 5
|
| Mon 28.11.
| K4-minor free graphs, Extremal graph theory – Mantel's Theorem, Turán's Theorem | Chapter 16 | Chapter 7
|
| Wed 30.11.
| Mock final exam - PDF here | N/A | N/A
|
| Mon 5.12.
| Final Review, Questions & Answers, 42 | N/A | N/A
|