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, vertexdegree, 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.
 2factors, Bipartite graphs and Hall's theorem – PDF notes  Chapters 7 & 8  Chapters 1 & 2

Mon 3.10.
 König's theorem and 2factors in 2kregular graphs  Chapters 8 & 15  Chapter 2

Wed 5.10.
 Vertexconnectivity of graphs & vertexcuts, Menger's theorem  Chapter 9  Chapter 3

Wed 12.10.
 Edgeconnectivity, edgecuts, flows in networks, FordFulkerson's theorem (statement)  Chapters 9 & 10  Chapters 3 & 6

Mon 17.10.
 Proof of FordFulkerson's theorem  Chapter 10  Chapter 6

Wed 19.10.
 Ramsey's Theorem & lowerbound on Ramsey numbers  Chapter 12  Chapters 9 & 11

Mon 24.10.
 Midterm (inclass) – 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 ddegenerate graphs, chromatic number of trianglefree graphs  Chapter 14  Chapter 5

Wed 9.11.
 Exercise session – Connectivity & Hall & Ramsey  N/A  N/A

Mon 14.11.
 Edgecolorings, 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, Outerplanar graphs, Kuratowski's Theorem  Chapter 15  Chapter 4

Wed 23.11.
 Minors in graphs, Duality for planar graphs, 5Color Theorem  Chapters 18 & 19  Chapters 4 & 5

Mon 28.11.
 K_{4}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
