Graph Theory 2016

Lecturer: Frank de Zeeuwemail – Office: MA C1 557

AssistantClaudiu Valculescuemail – Office: MA C1 585

If you have any questions, feel free to email us, or come see us.

Course details

  • Lectures: Thursday 08:15 – 10:00, MA B1 11
  • Problem sessions: Thursday 10:15 -12:00, MA B1 11
  • The final grade is determined by the exam, with possible bonus points. Each week you can hand in at most one of the starred problems on the problem set. Each problem is worth up to 0.1 bonus points that are added to your exam grade, for a total of at most 1.
  • There is no required textbook, but the following textbooks could be useful: Bondy & Murty – Graph Theory, Bollobas – Modern Graph Theory, Diestel – Graph Theory, West – Introduction to Graph Theory. I also recommend this course and its lecture notes. 

Schedule and lecture notes

Feb 25: Introduction

Mar   3: Trees

Mar 10: Matchings

Mar 17: Covers

Mar 24: Coloring

Apr   7: Hamilton cycles

Apr 14: 2-connected graphs

Apr 21: k-connected graphs

Apr 28: Planar graphs

May 12: Extremal graph theory I

May 19: Extremal graph theory II

May 26: Ramsey theory

June 2: Various proofs

Problem sets

Problem set 1Solutions

Problem set 2Solutions

Problem set 3Solutions

Problem set 4Solutions

Problem set 5Solutions

Problem set 6Solutions

Problem set 7Solutions

Problem set 8Solutions

Problem set 9Solutions

Problem set 10Solutions

Problem set 11Solutions

Problem set 12Solutions (without bonus) (updated solution to problem 3 on June 4)

Exam information


The exam is on Tuesday July 5th, from 12:15 to 15:15 in CE1515.


Office hours:

Claudiu: Wednesday June 15, 12-14 and Wednesday June 22, 12-14, in MA C1 585

Frank: Thursday June 16, 12-14 and Thursday June 23, 12-14, in MA C1 557


Approximately 1/3 of the exam will be based on the lectures notes, 1/3 will be based on the problem sets, and 1/3 will be ”new” problems.

Practice examSolutions


The bonus problems are not on the exam. The following parts of the notes and problems are also NOT on the exam:

– Theorem 4.4.1 on dominating sets (but you should know the definition of dominating sets);

– The proof of Theorem 5.2.2 on edge coloring (but you should know the statement of the theorem);

– Problem 9.7 on intersection points of lines;

– Corollary 10.3.2 on K_2,2-free graphs;

– The “alternative proof of Theorem 2.1” on page 3 of Lecture 10;

– Lemma 11.2.1 and the proof of Corollary 11.2.2 (but you should know the statement of Corollary 11.2.2);

– Problem 11.5 on the extremal number of P_k.