Switch to English
Cursus: 191520751
Graph Theory
Cursus informatie
Studiepunten (ECTS)5
VoertaalEngels H.J. Broersma
Contactpersoon van de cursus H.J. Broersma
Examinator H.J. Broersma
Examinator P. van 't Hof
OpmerkingThis course is also an elective of B-AM module 11.
AanmeldingsprocedureZelf aanmelden via OSIRIS Student
Inschrijven via OSIRISJa
The main aim of the course is to teach the students how to apply graph theoretical concepts to prove structural properties of graphs related to the topics described in the content of the course. More specifically, after following the course, the student can:
  • explain and apply basic concepts of graph theory;
  • explain and apply known properties of trees;
  • explain and apply the concepts of vertex and edge connectivity;
  • explain and apply the notions of Euler trail, Euler circuit and Hamilton cycle;
  • explain and apply theorems concerning matchings in bipartite and non-bipartite graphs;
  • explain and apply concepts and theorems about edge and vertex colouring;
  • explain and apply theorems about planar graphs;
  • prove new structural graph theoretical statements involving the above topics.
This course provides the students with a general introduction and understanding of central topics in graph theory. 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 is central and treated in more detail. This involves new definitions that are relevant for that particular topic, as well as associated structural results and their proofs. Lecture 2 deals 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, a concept used to model optimisation problems in which objects have to be paired off. This is generalised in Lecture 5 to edge colourings, which 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 focus on the special class of planar graphs.

The lecture slides are supported by a downloadable book that is also 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