Instructor 

Rudiger Urbanke 

Office 
INR 116 
Phone 
+4121 6937692 
Email 
rudiger.urbanke@epfl.ch 
Office Hours 
By appointment 
Teaching Assistant 

Marco Mondelli 

Office 
INR038 
Phone 
+4121 693 7514 
Email 
marco.mondelli@epfl.ch 
Office Hours 
Office Hours 24/24 
Lectures: 

Tuesday 
11:15 – 13:00 
Room: INM203 


Thursday 
16:15 – 18:00 
Room: 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.
Grade
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.
Textbook
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 singlesided 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 



25 Feb 
averaging principle, bipartite graphs, shortest path problem, Dijkstra’s algorithm 

04 Mar 
priority queues, Sperner’s lemma 
11 Mar 
consequence of Sperner’s lemma; Brouwer’s fixed point theorem, topologically equivalent domains, proof of Brouwer’s fixed point theorem in two dimensions 
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 Mar 
Exercise Session 5 
Homework 5 
Solution 5 
25 Mar 
matchings, matchings in bipartite graphs, Hall’s condtion 
01 Apr 
coverings, Koenig’s theorem, maximum matching and optimal matching 
08 Apr 
factors, augmented path search, optimal matching in general graph 
15 Apr 
flows, maximum flow, cut, minimum cut, max flow min cut theorem 
22 Apr 
Easter break – no course 
24 Apr 
Easter break – no course 
29 Apr 
FordFulkerson Algorithm, Menger’s theorem, error correcting codes based on sparse bipartite graphs 
06 May 
notion of expansion, bound on the minimum distance, the flipping algorithm 
15 May 
Course!!!: analysis of flipping algorithm, a bound on the expansion via spectral methods 
20 May 
probabilistic method, expansion of random bipartite graphs, Markov inequality, Chebyshev inequality 
27 May 
subgraph inclusion problem and threshold function 
29 May 
Public holiday – no exercise session 