Graph Theory 2016

Lecturer: Frank de Zeeuw – email – Office: MA C1 557

Assistant: Claudiu Valculescu – email – 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 1 – Solutions

Problem set 2 – Solutions

Problem set 3 – Solutions

Problem set 4 – Solutions

Problem set 5 – Solutions

Problem set 6 – Solutions

Problem set 7 – Solutions

Problem set 8 – Solutions

Problem set 9 – Solutions

Problem set 10 – Solutions

Problem set 11 – Solutions

Problem set 12 – Solutions (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 exam – Solutions

——————————————————————————————————————————————

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.

——————————————————————————————————————————————