Single-Course English 5 ECTS

Graph Theory II

Overall Course Objectives

The course includes a number of classical results such as the theorems of Tutte, Ramsey, Turan, Kuratowski, Brooks, Dirac, Smith, and Vizing, respectively, and also the Jordan Curve Theorem. The course also includes more recent themes, for example list-colorings.

Learning Objectives

  • Apply generating functions.
  • Apply counting technique illustrated by Ramsey’s theorem.
  • Apply the foundation for planar graphs: The Jordan Curve Theorem.
  • Apply the Kuratowski Planarity Criterion.
  • Understand and apply the classical theorems by Turan, Brooks, Dirac, Smith, Vizing, Roy-Gallai, Camion and Robbins.
  • Apply list-color method.
  • Apply algebraic methods illustrated by the chromatic polynomial.
  • Understand the probabilistic method illustrated by graphs with large chromatic number and large girth.

Course Content

1.Generating functions, the Catalan numbers.
2.Tutte’s 1-factor theorem. Petersen’s theorem.
3.The theorems of Ramsey og Turan.
4.The Jordan Curve Theorem.
5.Kuratowski’s theorem on planar graphs.
6.Hamilton cycles. Dirac’s theorem and the Grinberg criterion.
7.The number of hamilton cycles (Smith’s theorem) , chromatic number and maximum degree (Brooks’ theorem).
8.Vizing’s theorem on chromatic index.
10.Chromatic polynomial.
11.Directed graphs.
12.Graphs of large chromatic number and large girth.

Recommended prerequisites

Teaching Method

Two hours of lectures followed by two hours of group work


Limited number of seats

Minimum: 6, Maximum: 100.

Please be aware that this course has a minimum requirement for the number of participants needed, in order for it to be held. If these requirements are not met, then the course will not be held. Furthermore, there is a limited number of seats available. If there are too many applicants, a pool will be created for the remainder of the qualified applicants, and they will be selected at random. You will be informed 8 days before the start of the course, whether you have been allocated a spot.

See course in the course database.





13 weeks




DTU Lyngby Campus

Course code 01527
Course type PhD
Semester start Week 35
Semester end Week 48

10.600,00 DKK

Please note that this course has participants limitation. Read more