| Date | Content of the lecture | Lecture notes | Diestel's book
|
| Tue 5.9.
| Introduction to graph theory (see PDF slides from the first lecture)
| N/A | N/A
|
| Thu 7.9.
| Adjacency & incidence matrices, vertex-degree, walks, trails & paths
| Chapters 1, 2 | Chapter 1
|
| Tue 12.9.
| Connected components, subgraphs and induced subgraphs, cut-vetices and cut-edges | Chapter 2 | Chapter 1
|
| Thu 14.9.
| Trees – various characterisations and their mutual equivalence | Chapter 3 | Chapter 1
|
| Tue 19.9.
| Number of graphs on n vertices and labelled trees on n vertices (Cayley's formula) | PDF notes | N/A
|
| Thu 21.9.
| Spanning trees, fundamental cycles, Minimum spanning trees and Kruskal's algorithm | Chapter 4 | N/A
|
| Tue 26.9.
| Shortest paths and Dijkstra's algorithm | Chapter 5 | N/A
|
| Thu 28.9.
| Euler tours and Euler's theorem, Hamilton cycles and Ore / Pósa's theorem (statement) | Chapter 6 | Chapters 1, 10
|
| Tue 3.10.
| proof of Ore / Pósa's theorem, Bipartite graphs | Chapters 6, 7 | Chapters 2, 10
|
| Thu 5.10.
| Regular graphs, matchings, 2-factors, König's theorem (statement) | Chapter 8 | Chapter 2
|
| Tue 10.10.
| proof of König's theorem, Hall's theorem and its applications | Chapter 8 | Chapter 2
|
|
| Thu 12.10.
| Matching & covering inequalities, Tutte's theorem (statement), Petersen's theorem | Chapters 11, 13 | Chapter 2
|
| Tue 17.10.
| proof of Tutte's theorem | Chapter 13 | Chapter 2
|
| Thu 19.10.
| Midterm (in-class) | N/A | N/A
|
| Tue 24.10.
| Ramsey numbers R(k), Ramsey's Theorem | Chapter 12 | Chapter 9
|
| Thu 26.10.
| Exponential lower-bound on R(k), Multicolor Ramsey numbers & Shur's theorem | Chapter 12 | Chapters 9, 11
|
| Tue 31.10.
| Vertex/edge k-connectivity, vertex/edge-cuts, Menger's/Ford-Fulkerson's theorem (statement) | Chapter 9 | Chapter 3
|
| Thu 2.11.
| Proof of Menger's theorem | Chapter 9 | Chapter 3
|
| Tue 7.11.
| Flows in networks, Ford-Fulkerson Theorem | Chapter 10 | Chapter 6
|
| Thu 9.11.
| Proof of Ford-Fulkerson's theorem, vertex colorings | Chapters 10, 14 | Chapters 5, 6
|
| Tue 14.11.
| Greedy coloring algorithm, d-degenerate graphs, Brooks' theorem (statement) | Chapter 14 | Chapter 5
|
| Thu 16.11.
| Coloring Δ-free graphs, edge colorings, König's line coloring, Vizing's, and Shannon's theorems | Chapter 15 | Chapter 5
|
| Tue 21.11.
| Planar graphs, drawings of planar graphs, regions, Euler's formula | Chapter 17 | Chapter 4
|
| Thu 23.11
| Counting edges in planar graphs, Kuratowski's theorem, Minors in graphs | Chapters 17, 18 | Chapter 4
|
| Tue 28.11
| Duality of planar graphs, 5-Color theorem, Hadwiger's conjecture, K4-minor free graphs | Chapters 16, 19 | Chapter 5
|
|
| Thu 30.11
| FInal review, Mock final exam and its solution, Questions & Answers, 42 | N/A | N/A
|