Graph Theory


Prof. Rom Pinchasi


Eleonore Bach

Rebeka Raffay

News & Log

Here are the notes for the course: Notes

They are not very detailed, but they contain all the topics, theorems, and examples that we covered in the course. It is also very likely to contain typos and even small errors but nevertheless it is the closest thing for the lecture notes of the course.


The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer science and in practice. Warning: This course is for mathematicians! Strong emphasis is put on formal mathematical proofs.

Learning Prerequisites

Recommended courses

Mandatory for IN/SC: Analyse III, Physique générale I, Physique générale II, Probability and statistics


Lecture: Thursdays 13:15 – 15:00 (GCA330)

Exercises: Thursdays 15:15 – 16:45 (GCA330)


There will be no midterm exam. There will be a written final exam after the end of the semester. 

The exam will be on January 20 in the pavillon PO01. The exam starts at 9:15 AM.  

See the lecture notes: Notes

Homework problems

Exercise_1, Ex1_solutions

Exercise 2, Ex2_solutions

Exercise3, Ex3_solutions

Exercise4, Ex4_solutions

Exercise5, Ex5_solutions

Exercise6, Ex6_solutions

Exercise7, Ex7_solutions

Exercise8, Ex8_solutions

Exercise9, Ex9_solutions

Exercise10, Ex10_solutions

Exercise11, Ex11_solutions

Exercise12, Ex12_solutions

Exercise13, Exercise13_sol

Exercise14, Exercise14_sol



These notes are suggestions. They do not exactly cover the contents of the classes and also contain some content not covered by the classes. They do not replace the classes.

  1. Diestel : Graph Theory (Springer)
  2. Bollobas : Modern Graph Theory (Springer)
  3. Harris, Hirst, Mossinghoff : Combinatorics and Graph Theory (Springer)
  4. Harary : Graph Theory (Addison-Wesley).