Switch to English
Cursus: 191520751
Graph Theory
Cursus informatieRooster
Studiepunten (ECTS)5
VoertaalEngels H.J. Broersma
Contactpersoon van de cursus H.J. Broersma
Examinator H.J. Broersma
Examinator P. van 't Hof
AanmeldingsprocedureZelf aanmelden via OSIRIS Student
Inschrijven via OSIRISJa
The main aim of the course is to provide the students with a general introduction and understanding of the basic concepts and central topics in graph theory. The specific learning goals of the course are that at the end of the course, the students:
  • can recall the basic concepts and structural results that are treated in the course;
  • can explain and apply the theorems and the proofs that have been discussed;
  • understand the solutions to the exercises that are listed for the tutorials;
  • are able to apply their knowledge to solve new exercises;
  • are able to develop new proofs for variants of the results that have been explained;
  • are aware of the relevance of the treated topics for applications;
  • can apply their knowledge to model new problems as graph problems.
This course is meant to provide the students with a thorough introduction to graph theory and its applications. Apart from a general introduction to the basic concepts and definitions in Lecture 1, in each of the subsequent seven lectures, one graph theoretical topic will be central and treated in more detail. This will involve new definitions that are relevant for that particular topic, as well as associated structural results and their proofs. Lecture 2 will deal with trees, a special class of graphs that are relevant for many applications. Trees are the basic structures needed to guarantee connectivity, which is the central topic of Lecture 3. In Lecture 4, the focus is on matchings, modelling optimisation problems in which objects have to be paired off. This is generalised in Lecture 5 to edge colourings that are relevant in scheduling problems. The analogous counterpart of vertex colourings is treated in Lecture 6 and in part of Lecture 7. The remaining part of Lecture 7 and the final lecture will focus on the special class of planar graphs, that can be drawn in the plane avoiding crossings.

The lecture slides will be supported by a downloadable book that will also be made available as a reader from the UnionShop.
Participating study
Master Computer Science
Participating study
Master Applied Mathematics
Participating study
Bachelor Applied Mathematics
Module 11
Verplicht materiaal
To be announced by the lecturer
Aanbevolen materiaal


Written exam

Switch to English