Syllabus and course information
Basics (handout)
Schedule
Lecture 1 (7/2/2017): We had a recap on the basic notation and terminology. We began the section on trees, reaching the statement of Thm 1.3 (about three equivalent characterisations of trees). You should be able to do Q 1-4 from the first exercise sheet.
Lecture 2 (14/2/2017): We proved Thm 1.3 and gave one other characterisation of trees. We proved the exchange property for trees. We saw the description of Kruskal's algorithm and applied it to an example. We started the proof of correctness of Kruskal's algorithm.
Lecture 3 (21/2/2017): We finished the proof of correctness of Kruskal's algorithm. We saw the description of Dijkstra's algorithm and we applied it to one example. We saw the proof of correctness of Dijkstra's algorithm. Here is a handout on Kruskal's algorithm and Dijkstra's algorithm. You should be able to do Q1-3 from the second exercise sheet.
Lecture 4 (28/2/2017): We started talking about matchings. We gave several definitions and characterised maximum matchings in terms of augmenting paths. We also stated and proved Hall's Theorem.
Lecture 5 (07/3/2017). We proved various results relating the sizes of maximum independent sets / matchings and minimum vertex / edge covers in (bipartite) graphs. In particular we proved the Konig-Egervary Theorem, Gallai's Theorem, and Konig's Theorem.
Lecture 6 (14/3/2017): We saw an algorithm for finding a maximum matching in bipartite graphs and proved its correctness. We also saw the Hungarian algorithm for finding maximum weight perfect matchings in weighted bipartite graphs. Here is the handout for the path finding algorithm.
Lecture 7 (21/3/2017): We saw the proof of correctness for the Hungarian Algorithm. We saw how the various algorithmic problems we studied so far relate to the famous P vs NP problem. We started the section of graph connectivity, defining the various notions of connectivity and how they relate to each other.
Lecture 8 (4/4/2017): We defined the notion of blocks and proved various properties of blocks. In particular we tried to understand the structure of connected graphs in terms of blocks in particular by showing that the block-cutpoint graph is a tree.
Lecture 9 (11/4/2017): We tried to understand the structure of 2-connected graphs. We proved Menger's Theorem for the case of 2-connected graphs and we characterised 2-connected graphs in terms of ear decompositions. We started proving Menger's Theorem in full generality by showing how Theorem 3.10 implies Menger's Theorem.
Lecture 10 (18/4/2017): We proved Theorem 3.10, so proving Menger's Theorem. We recalled various definitions and results related to graph colouring including the greedy colouring algorithm. We saw intelligent greedy colouring, i.e. Szekeres-Wilf Theorem. We stated Brooks' Theorem.
Lecture 11 (25/4/2017): We proved Brooks' Theorem (through a sequence of lemmas). We then gave Mycielski's construction for triangle-free graphs with large chromatic number.
Lecture 12 (2/5/2017): We used the probabilistic method to show the existence of graphs with large girth and chromatic number. We defined the chromatic polynomial and showed it is a polynomial. We stated a recursion for the chromatic polynomial.
Lecture 13 (9/5/2017): We proved the recursion for the Chromatic polynomial. We had a recap on planar graphs, reminding ourselves that K_5 and K_3,3 are not planar graphs. We stated Kuratowski's Theorem that a graph is planar if and only if it does not contain a subdivision of K_5 or K_3,3. We proved the easy direction and half of the hard direction.
Lecture 14 (16/5/2017): We finished the proof of Kuratowski's Theorem.
Exercise Sheets
Exercises 1 (all solutions due beginning of the class on Fri 24th Feb)
Exercises 2 (all solutions except Q6 due at the beginning of class on Fri 10 Mar)
Exercises 3 (I will add two or three more questions to this sheet next week. All solutions due at the beginning of class on Fri 24th Mar. Two more questions have been added.)
Exercises 4 (all solutions due at the beginning of class on Thr 13 Apr).
Exercises 5 (all solutions due at the beginning of class on Thr 4 May).
Exercises 6 (Solutions to Q 1-7 and Q3 of Extra Exercises on Kuratowski's Theorem are due at the beginning of class on Thr 18 May). Typo in problem 5: n/td should say n/(2t).