Graph Theory and Algorithms (Feb - Jun 2018)

Course information

Basics (handout)

Lecture Notes (Updated 23/05)

Exam information

Schedule

Lecture 1 (6/2/2018): We had a recap on the basic notation and terminology. We began the section on trees, reaching the statement of Thm 1.4 (about three equivalent characterisations of trees). You should be able to do Q 1-4 from the first exercise sheet.

Lecture 2 (13/2/2018): We proved Thm 1.4 and 1.5 about characterising trees. We proved the exchange property for trees. We saw the description of Kruskal's algorithm and applied it to an example. We proved the correctness of Kruskal's algorithm.

Lecture 3 (20/2/2018): We described Dijkstra's algorithm and applied it to an example. We gave the proof of correctness for Dijkstra's algorithm. We started talking about matchings.

Lecture 4 (27/2/2018): We gave several definitions and characterised maximum matchings in terms of augmenting paths. We also stated and proved Hall's Theorem.

Lecture 5 (06/3/2018): 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 (13/3/2018): 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 (20/3/2018): 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.

Lecture 8 (3/4/2018): We started the section of graph connectivity, defining the various notions of connectivity and how they relate to each other. We defined the notion of blocks and stated various properties of blocks.

Lecture 9 (10/4/2018): No lecture

Lecture 10 (17/4/2018): We proved various properties of blocks and defined the block-cutpoint graph. We proved a theorem of Whitney which characterises 2-connected graphs in terms of the existence of internally vertex-disjoint paths. We defined ear decompositions and stated the characterisation of 2-connected graphs in terms of ear decompositions.

Lecture 11 (24/4/2018): We proved the characterisation of 2-conected graphs in terms of ear decompositions. We stated and proved Menger's Theorem.

Lecture 12 (1/5/2018): We started the section of graph colouring. We introduced the greedy algorithm and proved some bounds on the chromatic number. We proved the preliminary lemmas for Brooks' Theorem.

Lecture 13 (8/5/2018): We finished the proof of Brooks Theorem. We described Mycielski's construction and used it to prove the existence of triangle-free graphs with arbitrarily high chromatic number.

Lecture 14 (15/5/2018): We proved the existence of graphs of arbitrarily large girth and chromatic number. We introduced the chromatic polynomial and showed various properties.

Lecture 15 (22/5/2018): We proved Kuratowski's theorem that a graph is planar if and only if it has no subdivision of K_5 or K_{3,3}.

Lecture 16 (29/5/2018): No lecture

Exercise Sheets

Exercises 1 (all solutions due at the beginning of the class on Fri 23rd Feb)

Exercises 2 (all solutions due at the beginning of class on Fri 09 Mar)

Exercises 3 (all solutions due at the beginning of class on Fri 23 Mar)

Exercises 4 (all solutions due at the beginning of class on Thr 19 Apr) Updare: deadline extended to beginning of lecture on Tue 24th April.

Exercises 5 (all solutions due at the beginning of class on Fri 04 May)

Exercises 6 (solutions to the first 6 questions due at the beginning of lecture on Tue 22 May: deadline extended)