Graph Theory Applications

Rudiger Urbanke
OfficeINR 116
Phone+4121 6937692
Office HoursBy appointment
Teaching Assistants
Lazlo Czap (for first 3 weeks)
Phone+4121 6937516
OfficeBC 048
Office HoursOffice Hours TBD
Siddhartha Brahma
Phone+4121 6936654
Office HoursOffice Hours TBD
Stanko Novakovic
Phone+4121 6937543
Office HoursOffice Hours TBD
Student Assistant
Yannik Messerli

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

This class focuses on graph theory problems arising in Computer Science and Communications and discusses how to use methods and results from graph theory to solve them. The class will cover topics such as:

  1. Introduction to basic concepts in graph theory
  2. Job scheduling and graph coloring
  3. Network routing and graph connectivity
  4. Labyrinths and Eulerian paths
  5. Archeological data and trees
  6. VLSI design and planar graphs
  7. Internet routers and bipartite graphs
  8. Wireless Networks and geometric 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 book here

Special Announcements

For the Final Exam, just like the midterm, you are allowed to bring one A4 sheet with all the information you can write into it! Best of Luck!


Please announce your group by April 25th. The due date of the project is Thursday May 30th.

Project Project.pdf

Detailed Schedule

Date Topic Assignment Due Date/Solutions Posted Remarks
19Feb Introduction; basic concepts, paths, cycles, special graphs, averaging principle
21Feb Exercise Session 1 Ex1.pdf
26Feb Eulerian graphs, Hamiltonian graphs
28Feb Exercise Session 2 Ex2.pdf
05Mar adjacency matrix A, powers of A, eigenvalues of A, incidence matrix B, rank of B
07MarExercise Session 3 Ex3.pdf
12Mar trees, cut edges, cut vertices, spanning trees, Cayley's formula, the connector problem, Kruskal's algorithm
14MarExercise Session 4 Ex4.pdf
19Mar proof of Kruskal's algorithm; matchings and vertex covers; there will be only one hour of lecture and one hour of exercise session
Exercise Session 5 Ex5.pdf
21MarGraded Homework 1 HW1.pdf

02Apr Easter break - no course
04Apr Easter break - no course
11Apr Midterm Exam ( INJ 218); 4:15pm-6pm Midterm.pdf
16Apr Edge Colorings
18Apr Exercise Session 6 Ex6.pdf
23Apr Independent Sets and Ramsey Theory
25AprExercise Session 7 Ex7.pdf
30Apr Chromatic numbers
02May Exercise Session 8 Ex8.pdf
09May Public holiday - no course
14MayGraded Homework 2 Hw2.pdf
16MayNetwork Flows, Max flow Min cut
21MayFeasible Flows
23May Exercise Session 9 Ex9.pdf

Course Notes

Last modified:: %2014/%02/%18 %14:%Feb