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.