Graph Theory Applications

Rudiger Urbanke
OfficeINR 116
Phone+4121 6937692
Office HoursBy appointment

Teaching Assistant
Marco Mondelli
Phone+4121 693 7514
Office HoursOffice Hours 24/24

Lectures: Tuesday11:15 - 13:00Room: INM203
Thursday 16:15 - 18:00Room: INM 201

Language: English Coefficient/Crédits: 4 ECTS

Link to the official course description. CourseInformation.pdf

Course Description

Besides classical notions of graph theory (shortest path, cuts, flows, colouring, independent set, matchings, planarity), we will cover a few more modern concepts. In particular, we will briefly discuss random graphs as well as some basic notions of the spectral theory of graphs.


The grade will have four components - Homeworks (10%), Project (20%), Midterm Exam (30%) and Final Exam (40%)

Tentatively, there will be two homework sets on both sides of the Midterm exam. The precise topic of the project will be discussed in the class during the semester.


We will be using the book Graph Theory with Applications by J.A. Bondy and U.S.R. Murty. You may find the electronic version of the old version of this book here. In addition we recommend that you buy the new version. Other standard references are the book by West as well as the book by Diestel. We will also make use of some material from the following lecture notes lecture notes.

Special Announcements

Information about the final exam: it takes place on Friday, June 27, from 8:15 until 11:00, in room INM 10. Please, be there at 8:00 so that we can assign the seats and start at 8:15 sharp.

Allowed material: four handwritten single-sided A4 pages of notes.

Date Topic Assignment Due Date/Solutions Posted Remarks
18 Feb motivation; basic concepts: adjacency, degrees, graphic degree sequences, walk, trail, paths, some special graphs, raids, diameter, averaging principle, pigeonhole principle
20 Feb Exercise Session 1 Homework 1 Solution 1
25 Febaveraging principle, bipartite graphs, shortest path problem, Dijkstra's algorithm
27 Feb Exercise Session 2 Homework 2 Solution 2
04 Mar priority queues, Sperner's lemma
06 MarExercise Session 3 Homework 3 Solution 3
11 Marconsequence of Sperner's lemma; Brouwer's fixed point theorem, topologically equivalent domains, proof of Brouwer's fixed point theorem in two dimensions
13 MarExercise Session 4 Graded Homework 4 Solution 4
18 Mar spanning trees, minimum weight spanning trees, Kruskal's algorithm, matroids, examples of matroids, general greedy algorithm for a weighted matroid, optimality of this greedy algorithm
20 MarExercise Session 5 Homework 5 Solution 5
25 Marmatchings, matchings in bipartite graphs, Hall's condtion
27 MarExercise Session 6 Homework 6 Solution 6
01 Aprcoverings, Koenig's theorem, maximum matching and optimal matching
03 Apr Exercise Session 7 Graded Homework 7 Solution 7
08 Aprfactors, augmented path search, optimal matching in general graph
10 Apr Exercise Session 8 Homework 8 Solution 8
15 Aprflows, maximum flow, cut, minimum cut, max flow min cut theorem

22 Apr Easter break - no course
24 Apr Easter break - no course

29 AprFord-Fulkerson Algorithm, Menger's theorem, error correcting codes based on sparse bipartite graphs
01 May Exercise Session 9 - Project Project Project - Solution
06 Maynotion of expansion, bound on the minimum distance, the flipping algorithm
08 May Exercise Session 10 Homework 10 Solution 10
13 MayExercise Session 11!!! Homework 11 Solution 11
15 May Course!!!: analysis of flipping algorithm, a bound on the expansion via spectral methods
20 Mayprobabilistic method, expansion of random bipartite graphs, Markov inequality, Chebyshev inequality
22 May*Exercise Session 12 Homework 12 Solution 12
27 Maysubgraph inclusion problem and threshold function
29 May Public holiday - no exercise session

Last modified:: %2014/%06/%27 %14:%Jun