If you have any questions, feel free to email us, or come see us.
- 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
The exam is on Tuesday July 5th, from 12:15 to 15:15 in CE1515.
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.
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.