Programme And Module Handbook
 
Course Details in 2025/26 Session


If you find any data displayed on this website that should be amended, please contact the Curriculum Management Team.

Module Title Graph Theory
SchoolMathematics
Department Mathematics
Module Code 06 19605
Module Lead Deryk Osthur & Allan Lo
Level Masters Level
Credits 20
Semester Semester 1
Pre-requisites LC Algebra & Combinatorics 1 - (06 25659)
Co-requisites
Restrictions Optional for all MSci programmes in Mathematics and all MSci JH programmes including Mathematics
Contact Hours Lecture-46 hours
Tutorial-10 hours
Total: 56 hours
Exclusions
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.
Learning Outcomes By the end of the module the student should be able to:
  • Be familiar with basic graph parameters and their relationships
  • Understand and be able to apply fundamental results on graphs
  • Understand how some problems can be modelled as algorithmic graph problems and should know approaches to solve them
  • Apply the basic techniques introduced in the lectures
  • Explore these topics beyond the taught syllabus
Assessment 19605-07 : Raw Module Mark : Coursework (100%)
Assessment Methods & Exceptions 3 hour Written Unseen Examination (80%); In-course Assessment (20%)
Other
Reading List Diestel, R. 2000. Graph Theory. 2nd ed. Springer Verlag.
Bondy, J A & Murty, U S R. 1976. Graph Theory with Applications. North-Holland.
Electronic Version: http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html
West, D. 2001. Introduction to Graph Theory. Prentice Hall.