Code 19592
Level of study Third/Final year
Credit value 20
Semester Students may study either 1 or both.
Pre-requisite modules 22481
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.