Graph Theory

School of Mathematics

College of Engineering and Physical Sciences


Code 19592

Level of study Third/Final year

Credit value 20

Semester Students may study either 1 or both.

Pre-requisite modules 22481

Module description

The module will give an introduction to fundamental results and concepts in graph theory. Topics are likely to include Hamilton cycles, graph matchings, connectivity, graph colourings, planar graphs and extremal graph problems. For example, a fundamental result in Graph Theory is Dirac's theorem. It gives a condition which ensures that a graph has a Hamilton cycle (ie a cycle which contains all vertices of the graph). Another example is the Four colour theorem. It states that every planar map can be coloured with at most four colours such that adjacent regions have different colours (this can be translated into a graph colouring problem). Some of the ideas will also be applied to algorithmic problems for graphs.

Teaching and learning methods